PROGPROG - Progressive progressions
An arithmetic progression is a sequence of numbers a1, a2,... an such that ai+1-ai is equal for all 0≤i Now consider a sequence of arithmetic progressions A1 = (a1,1, a1,2,... a1,n1), A2 = (a2,1, a2,2,... a2,n2),... Ak = (ak,1, ak,2,... ak,nk) A progressive progression is such a sequence with the additional properties that: Find the number of progressive progressions such that a1,1=1 and ak,nk = N. As this number can be quite large, output it modulo 100000007. The first line of input contains T (≤ 100), the number of testcases. This is followed by the description of the testcases. The description of each testcase consists of a single integer N (1 < N ≤ 1000000). For each testcase, output modulo 100000007 the number of progressive progressions such that a1,1=1 and ak,nk = N
Input
Output
Example
Input:
2
5
10
Output:
1
6
Added by: | Raziman T V |
Date: | 2011-02-13 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | IOPC2011 |