Given a natural number n, in how many ways can you split the number into sum of two or more natural numbers ? For eg, 4 can be split in 4 ways :

• 1 + 1 + 1 + 1
• 1 + 2 + 1
• 2 + 2
• 1 + 3

Input

First line consists of t, the number of test cases.

Each of the t lines consists of n (1<=n<=1000)

Output

Output t lines each containing the corresponding number of ways the number can be split. Since this answer can be large, print the answer modulo 1000000007.

Example

Input:
2
3
4

Output:
2
4