TFSETS  TripleFree Sets
A set S of positive integers is called strongly triplefree 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 triplefree 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
hide comments
wolfris:
20180107 08:28:09
anyone give me some hints? i tried to solve it in some ways but none of them work. help!

Added by:  Ivan Metelsky 
Date:  20060119 
Time limit:  1.559s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  Based on a problem from www.testthebest.by 