Фермер Джон (снова) придумал новый режим утренней зарядки для коров!

Как и прежде, n коров фермера Джона выстроились в линию. i - ая корова слева имеет метку i для каждого i (1 ≤ i ≤ n). Он говорит им повторять следующий шаг до тех пор, пока коровы не будут в том же порядке, что и при старте.

Дана перестановка A длины n, коровы меняют свой порядок так, что i-ая корова слева до изменения становится Ai-ой слева после изменения.

Например, если 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 ≤ 104) и m (108 ≤ m ≤ 109 + 7, m простое).

Выходные данные

Выведите одно число.

Example

Существуют перестановки, требующие от коров совершить 1, 2, 3, 4, 5 и 6 шагов. Ответ равен 1 + 2 + 3 + 4 + 5 + 6 = 21.