소의 아침 운동

Farmer John이 소들을 위해 새로운 아침 운동 루틴을 만들었다(또 또!).

이전과 마찬가지로 Farmer John의 $N$마리 소($1\le N\le 10^4$)가 한 줄로 서 있다. 왼쪽에서 $i$번째 소의 이름표는 $1\le i\le N$인 각 $i$에 대해 $i$이다. 그는 소들에게 처음 순서와 같아질 때까지 다음 단계를 반복하라고 말한다.

• 길이 $N$의 순열 $A$가 주어질 때, 소들은 순서를 바꾸어, 바꾸기 전 왼쪽에서 $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$으로 나눈 나머지를 출력하라($10^8\le M\le 10^9+7$, $M$은 소수).

첫째 줄에 $N$과 $M$이 주어진다.

정수 하나를 출력한다.

소들이 $1$, $2$, $3$, $4$, $5$, $6$단계를 수행하게 하는 순열이 존재한다. 따라서 답은 $1+2+3+4+5+6=21$이다.