> For the complete documentation index, see [llms.txt](https://project-euler-ja.gitbook.io/project-euler-ja/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://project-euler-ja.gitbook.io/project-euler-ja/501-600/551-560/p559.md).

# 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)$$ を求めよ。