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<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)mod1000000123=161858102$.

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

Find $Q(50000)mod1000000123$.