Упражнение (Золото)
Фермер Джон (снова) придумал новый режим утренней зарядки для коров!
Как и прежде, n коров фермера Джона выстроились в линию. i - ая корова слева имеет метку i для каждого i (1 ≤ i ≤ n). Он говорит им повторять следующий шаг до тех пор, пока коровы не будут в том же порядке, что и при старте.
Дана перестановка A длины n, коровы меняют свой порядок так, что i-ая корова слева до изменения становится A[i]-ой слева после изменения.
Например, если A = (1, 2, 3, 4, 5) то коровы совершают один шаг. Если A = (2, 3, 1, 5, 4), то коровы совершат шесть шагов. Порядок коров слева направо после каждого шага будет следующим:
0 шаг: (1, 2, 3, 4, 5)
1 шаг: (3, 1, 2, 5, 4)
2 шаг: (2, 3, 1, 4, 5)
3 шаг: (1, 2, 3, 5, 4)
4 шаг: (3, 1, 2, 4, 5)
5 шаг: (2, 3, 1, 5, 4)
6 шаг: (1, 2, 3, 4, 5)
Найдите сумму всех положительных целых чисел k таких, что существует перестановка длины n которая требует от коров сделать ровно k шагов.
Поскольку это число может быть очень большим, выведите ответ по модулю m.
Входные данные
В одной строке заданы числа n (1 ≤ n ≤ 10^4) и m (10^8 ≤ m ≤ 10^9 + 7, m простое).
Выходные данные
Выведите одно число.
Example
Существуют перестановки, требующие от коров совершить 1, 2, 3, 4, 5 и 6 шагов. Ответ равен 1 + 2 + 3 + 4 + 5 + 6 = 21.