TFSETS - 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

Added by:Ivan Metelsky
Date:2006-01-19
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.test-the-best.by

hide comments
2018-01-07 08:28:09
anyone give me some hints? i tried to solve it in some ways but none of them work. help!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.