559 : 並び替え行列

行列の全ての行で $j$ 列目の要素が $j+1$ 列目の要素より小さいとき、 $j$ 列目は上昇しているという。

次の条件を満たす $r×n$ 行列の個数を $P(k,r,n)$ とする。

• どの行も $\{1,2,3,\dots,n\}$ の並び替えである

• 最初の列を 1 列目として、列 $j < n$ は $j$ が $k$ の倍数でないときかつそのときに限り上昇している

例えば $P(1,2,3)=19, P(2,4,6)=65508751, P(7,5,30) \bmod (10^9+123) = 161858102$ である。

$\displaystyle Q(n)=\sum_{k=1}^n P(k,n,n)$ とする。

例えば $Q(5)=21879393751, Q(50) \bmod (10^9+123) = 819573537$ である。

$Q(50000) \bmod (10^9+123)$ を求めよ。