카드 정렬

Bajtazar는 브리지를 즐기지만 손에 든 카드를 빠르게 정리하는 데 어려움을 겪는다. 그래서 동료들과 다음 게임을 하기 전에 카드 정리를 연습하려 한다.

그는 1부터 $n$까지 번호가 매겨진 연습용 카드 덱을 $n$장 준비했다. 연습은 카드를 섞는 것으로 시작하며, 그 결과 손에 든 카드가 하나의 순열이 된다. 그다음 카드를 번호의 오름차순으로 정렬한다.

카드가 정렬되어 있지 않은 동안, Bajtazar는 다음 연산을 반복한다. 손에 든 첫 번째 카드의 번호를 $k$라고 하고, 손에서 번호가 $k-1$인 카드를 찾는다($k = 1$이면 번호가 $n$인 카드를 찾는다). 그 카드를 맨 앞으로 옮긴다. 이 연산의 소요 시간은 찾은 카드가 맨 앞에서 떨어진 거리에 비례한다. 정렬 시간은 수행한 모든 연산 시간의 합이다.

예를 들어 순열 5 6 3 7 1 4 2의 정렬 시간은 $5 + 3 + 6 + 6 = 20$이다. 연산의 순서는 다음과 같다.

5 6 3 7 1 4 2 → 4 5 6 3 7 1 2 → 3 4 5 6 7 1 2 → 2 3 4 5 6 7 1 → 1 2 3 4 5 6 7

Bajtazar는 가능한 $n!$개의 모든 순열에 대해 정렬을 연습하고 싶어 한다. 그가 이 생각을 단념하도록, 모든 순열의 정렬 시간 합을 구하는 프로그램을 작성하라. 지금은 그 합을 $m$으로 나눈 나머지만 구하면 된다.

첫 번째이자 유일한 줄에 두 정수 $n$과 $m$이 주어진다($2 \le n \le 1\,000\,000$, $2 \le m \le 1\,000\,000\,000$).

모든 $n!$개의 순열에 대한 정렬 시간의 합을 $m$으로 나눈 나머지를 한 줄에 출력한다.