Вправа (Золото)
Фермер Джон знову придумав новий режим ранкової зарядки для своїх корів!
Як і раніше, 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 просте).
Вихідні дані
Виведіть одне число.
Приклад
Існують перестановки, які вимагають від корів здійснити 1, 2, 3, 4, 5 і 6 кроків. Відповідь дорівнює 1 + 2 + 3 + 4 + 5 + 6 = 21.