Farmer John has come up with a new morning exercise routine for the cows (again)!As before, Farmer John's NN cows (1≤N≤1041≤N≤104) are standing in a line. The ii-th cow from the left has label ii for each 1≤i≤N1≤i≤N. He tells them to repeat the following step until the cows are in the same order as when they started.

• Given a permutation AA of length NN, the cows change their order such that the ii-th cow from the left before the change is AiAi-th from the left after the change.

For example, if A=**(1,2,3,4,5)A=(1,2,3,4,5) then the cows perform one step. If A=(2,3,1,5,4)**A=(2,3,1,5,4), then the cows perform six steps. The order of the cows from left to right after each step is as follows:

• 0 steps: (1,2,3,4,5)(1,2,3,4,5)
• 1 step: (3,1,2,5,4)(3,1,2,5,4)
• 2 steps: (2,3,1,4,5)(2,3,1,4,5)
• 3 steps: (1,2,3,5,4)(1,2,3,5,4)
• 4 steps: (3,1,2,4,5)(3,1,2,4,5)
• 5 steps: (2,3,1,5,4)(2,3,1,5,4)
• 6 steps: (1,2,3,4,5)(1,2,3,4,5)

Find the sum of all positive integers KK such that there exists a permutation of length NN that requires the cows to take exactly KK steps.

As this number may be very large, output the answer modulo MM (108≤M≤109+7108≤M≤109+7, MM is prime).

INPUT FORMAT (file exercise.in):

The first line contains NN and MM.

OUTPUT FORMAT (file exercise.out):

A single integer.

SAMPLE INPUT:

5 1000000007

SAMPLE OUTPUT:

21

There exist permutations that cause the cows to take 11, 22, 33, 44, 55, and 66 steps. Thus, the answer is 1+2+3+4+5+6=211+2+3+4+5+6=21.

SCORING:

• Test cases 2-5 satisfy N≤102N≤102.
• Test cases 6-10 satisfy no additional constraints.