Вам даны натуральное число $N$ и простое число $P$. Для перестановки $(a_1, a_2, \dots, a_N)$ чисел $1, 2, \dots, N$ определим её оценку $f(a)$ следующим образом:

$$f(a) = \max\{i \cdot a_i \mid i = 1, 2, \dots, N\}$$

Найдите остаток от деления суммы оценок по всем перестановкам на $P$.

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

В первой строке содержатся $N$ и $P$ в указанном порядке, разделенные пробелами ($1 \le N \le 10^4$, $10^8 \le P < 10^9$, $P$ — простое число).

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

Выведите остаток от деления суммы оценок по всем перестановкам на $P$.

Примеры

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

10 100000007

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

77379290

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

1000 998244353

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

168695631

Примечание

Для первого примера, например, $f(3, 9, 4, 10, 8, 2, 7, 5, 6, 1) = 54$. Сумма оценок по всем $10!$ перестановкам равна $277379304$, а остаток от деления этой суммы на простое число $P = 10^8 + 7$ равен $77379290$, поэтому выведите $77379290$. Обратите внимание, что для этих входных данных простое число $P$ является 9-значным целым числом $10^8 + 7$.