Problem Archive

An ascent of a column $j$ in a matrix occurs if the value of column $j$ is smaller than the value of column $j + 1$ in all rows.

Let $P(k, r, n)$ be the number of $r \times n$ matrices with the following properties:

• The rows are permutations of $\{1, 2, 3, \dots, n\}$.
• Numbering the first column as $1$, a column ascent occurs at column $j \lt n$ if and only if $j$ is not a multiple of $k$.

For example, $P(1, 2, 3) = 19$, $P(2, 4, 6) = 65508751$ and $P(7, 5, 30) \bmod 1000000123 = 161858102$.

Let $Q(n) = \displaystyle \sum_{k=1}^n P(k, n, n)$.
For example, $Q(5) = 21879393751$ and $Q(50) \bmod 1000000123 = 819573537$.

Find $Q(50000) \bmod 1000000123$.