如果所有行中 $j$ 列的值都小于 $j+1$ 列的值，则矩阵中 $j$ 列的上升会发生。

令 $P(k,r,n)$ 为 $r\times 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)mod1000000123=161858102$。

设 $Q(n)={\displaystyle \sum _{k=1}^{n}P(k,n,n)}$。
例如，$Q(5)=21879393751$ 和 $Q(50)mod1000000123=819573537$。

查找 $Q(50000)mod1000000123$。