Farmer John has come up with a new morning exercise routine for the cows (again)!

As before, Farmer John's N cows (1\le N\le 10^4) are standing in a line. The i-th cow from the left has label i for each 1\le i\le N. He tells them to repeat the following step until the cows are in the same order as when they started.

Given a permutation A of length N, the cows change their order such that the i-th cow from the left before the change is A_i-th from the left after the change.

For example, if A=(1,2,3,4,5) then the cows perform one step. If 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 step: (3,1,2,5,4)
2 steps: (2,3,1,4,5)
3 steps: (1,2,3,5,4)
4 steps: (3,1,2,4,5)
5 steps: (2,3,1,5,4)
6 steps: (1,2,3,4,5)

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

As this number may be very large, output the answer modulo M (10^8\le M\le 10^9+7, M is prime).

SCORING:

Test cases 2-5 satisfy N\le 10^2.
Test cases 6-10 satisfy no additional constraints.

Problem credits: Benjamin Qi

#4170 upload 5 done 3 how_to_reg 3

Exercise timer 1s memory 128MB

#4170

Exercise 1s 128MB