spoj#TFSETS. Triple-Free Sets
Triple-Free Sets
A set S of positive integers is called strongly triple-free if, for any integer x, the sets {x, 2x} and {x, 3x} are not subsets of S. Let's define F(n) as a number of strongly triple-free subsets of {1, 2, ..., n}, where n is a natural number.
You need to write a program which being given a number n calculates the number F(n) modulo 1 000 000 001.
Input
The first line of input contains integer T (1 ≤ T ≤ 500) - the number of testcases. Then descriptions of T testcases follow.
The description of the testcase consists of one line. The line contains an integer number n (1 ≤ n ≤ 100 000).
Output
For each testcase in the input your program should output one line. This line should contain one integer number which is the number F(n) modulo 1 000 000 001.
Example
Input: 5 3 1 10 20 39 Output: 5 2 198 43776 971827200