Возрастание столбца j в матрице возникает, если во всех рядах значение столбца j меньше, чем значение столбца j+1.

Пусть P(k, r, n) будет количеством матриц r × n со следующими свойствами:

• Ряды являются перестановками множества {1, 2, 3, ... , n}.
• Первый столбец имеет номер 1, возрастание столбца возникает на столбце j<n тогда и только тогда, если j не делится на k.

Например, P(1, 2, 3) = 19, P(2, 4, 6) = 65508751 и P(7, 5, 30) mod 1000000123 = 161858102.

Пусть Q(n) =$\, \displaystyle \sum_{k=1}^n\,$ P(k, n, n).
Например, Q(5) = 21879393751 и Q(50) mod 1000000123 = 819573537.

Найдите Q(50000) mod 1000000123.