Dany jest dodatnia liczba całkowita $N$ oraz liczba pierwsza $P$. Dla permutacji $(a_1, a_2, \dots, a_N)$ zbioru $1, 2, \dots, N$, definiujemy jej wynik $f(a)$ w następujący sposób:

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

Znajdź resztę z dzielenia sumy wyników wszystkich permutacji przez $P$.

Wejście

W pierwszej linii znajdują się liczby $N, P$ w tej kolejności, oddzielone spacjami ($1 \le N \le 10^4$, $10^8 \le P < 10^9$, $P$ jest liczbą pierwszą).

Wyjście

Wypisz resztę z dzielenia sumy wyników wszystkich permutacji przez $P$.

Przykład

Wejście 1

10 100000007

Wyjście 1

77379290

Wejście 2

1000 998244353

Wyjście 2

168695631

Uwagi

Dla pierwszego przykładu, przykładowo $f(3, 9, 4, 10, 8, 2, 7, 5, 6, 1) = 54$. Suma wyników dla wszystkich $10!$ permutacji wynosi $277379304$, a reszta z dzielenia tej sumy przez liczbę pierwszą $P = 10^8 + 7$ wynosi $77379290$, zatem należy wypisać $77379290$. Zauważ, że dla tego wejścia liczba pierwsza $P$ jest 9-cyfrową liczbą całkowitą $10^8 + 7$.