### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

**Basic Observations:** Let **f(N, k)** be the number of the integers no more than **N** which have exactly **k** divisors. For each **k, f(N, k)** balls can be put into **f(N, k)** boxes freely. The number of these patterns is **f(N, k)**! (factorial number). Therefore the answer is (**g(N)**-1) mod **M**, where **g(N)** = **f(N**, 1)! * **f(N**, 2)! * …, and **M** = 500009. Note that subtracting of one corresponds to the fact that initial state is not valid.

**Some Tricks:** By the definition, if **N** has **k** divisors, **f(N, k)** - **f(N**-1, **k**) = 1, otherwise **f(N**, **k**) - **f(N**-1, **k**) = 0. Therefore, we obtain **g(N)** = **g(N**-1) * **f(N, k)**, where **k** is the number of the divisors of **N**. And, we can check the fact that **g(N**_{MAX}) mod **M** = 0, where **N**_{MAX} = 2229283, since **f(N**_{MAX}, 8) = **M**. Thus, **g(k)** mod **M** = 0 for **k** ≥ **N**_{MAX}.

To wrap up, now, our task is calculating the number of the divisors of **N**, for **N** < **N**_{MAX}. The following is a pseudo code.

div[k] := the number of the divisors of k (this part is considered in the following)

sum[k] := 0

res[0] := 1

for(k = 1; k < **N**_{MAX}; k++)

sum[div[k]] := sum[div[k]] + 1

res[k] := res[k-1] * sum[div[k]] mod **M**

foreach **N** in test cases

if **N** ≥ **N**_{MAX}, print -1 mod **M**

else print res**[N]** - 1 mod **M**

**First Approach:** For each integer, calculate the number of the divisors of the integer independently. However, this approach is terrible slow. This approach should get Time Limit Exceeded.

**Second Approach:** This approach is, for each integer i, to increment the number of the divisors of the integers multiple of i. This approach run in O (N_{MAX} log **N**_{MAX}) time, but this approach is a bit slow for this problem. (This approach can get Accepted for the first version of this problem. However, the tester suggested this problem should be solved more faster!)

div[k] := 0

for(i = 1; i < **N**_{MAX}; i++)

for(j = i; j < **N**_{MAX}; j += i)

div[j] := div[j] + 1

**Modified Second Approach:** The fact “if **k** is a divisor of **N**, then **N/k** is also a divisor of **N**” can make Second Approach about twice faster. This approach can be Accepted if some optimizations are used, but this approach may get Time Limit Exceeded if implemented naively. For example, use unsigned char or short arrays instead of int arrays for optimizations.

div[k] := 0

for(i = 1; i*i < N_{MAX}; i++)*i+i; j <

div[i*i] := div[i*i] + 1

for(j = i

**N**

_{MAX}; j += i)

div[j] := div[j] + 2

**Third Approach:** Let the factorization of **k** be 2^{P 2 } * 3

^{p 3 } * 5

^{p[5]} * …, then the number of the divisors of **k** is (p2+1) * (p3+1) * … This approach also can be Accepted if some optimizations are used, but sometimes get Time Limit Exceeded.

div[k] := 1

rest[k] := k

foreach prime number p such that p*p < **N**_{MAX}

for(i = p; i < **N**_{MAX}; i += p)

power := 0

while(p divides rest[i])

power := power + 1

rest[i] := rest[i] / p

div[k] := div[k] * (power + 1)

foreach k such that rest[k] > 1

div[k] := div[k] * 2

**Fourth Approach (Model Solution):** Let m[k] be the minimum prime divisor of **k**, and let the factorization of **k** be m[**k**]^{deg[k]} * … Then the following recursion formula is hold:

Let i be **k** / m[**k**], then

If m[i] = m[**k**], then deg[**k**] = deg[**i**] + 1, and div[**k**] = div[**i**] * (deg [**k**]+1) / (deg[**i**]+1),

otherwise, deg[k] = 1, and div[k] = div[i] * 2.

This recursion formula can be proved by using the fact that the number of the divisors is (p 2 +1) * (p 3 +1) * … This approach run in about 1.5 sec if implemented naively in C/C++. Here, the following naive way is enough for calculating m[**k**].

m[k] := k

foreach prime number p such that p*p < **N**_{MAX}

for(i = p; i < **N**_{MAX}; i += p)

if m[k] > p, then m[k] = p

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.