INS14G - Kill them All

no tags 

For his training, Digo is asked to solve the following challenge.

There is a mock terrorist situation. There are N terrorists and Digo is teamed up with his friend Sharry. They have to kill all the terrorists. Since this was too easy a task for this dynamic duo, Digo decided to have some fun with this challenge. At any given instant, Digo wants that the number of terrorists killed by him should be more than those killed by Sharry. The terrorists come in a fixed order. Any terrorist can be killed by either Digo or Sharry. Give the total number of ways in which the terrorists can be killed by them such that at every instant terrorists killed by Digo is more than the number of terrorists killed by Sharry.

Give your answer modulo 10^9+7.

Input

The first line consists of a single integer T, denoting the number of test cases.

T lines follow each consisting of an integer N denoting the total number of terrorists.

Output

For each test case print the total number of possible ways modulo 10^9 + 7.

Constraints

1 <= t <= 100000
1 <= n <= 1000000

Sample

Input:
2
1
3

Output:
1
2

hide comments
PARTH SHARMA: 2016-08-31 01:00:10

All hail mother of Robb Stark ;)

Piyush Kumar: 2016-06-22 21:10:45

The time limit is insane!!! Nothing passes! No wonder there are no solutions in Python. I don't get the point of keeping such strict time limits!

Edit: Ah! Finally AC! Faith in algorithms restored:)! The time limit is fine.

Last edit: 2016-07-13 20:14:05
Ankit Sultana: 2015-03-01 06:01:44

Phew!!!

devil: 2015-01-07 21:13:12

is an O(n+t) solution without fast I/O sufficient to beat the time limit....???

[Lakshman]: 2014-04-06 17:16:50

ridiculous time limit at least time should be 2s.
--ans(Francky)--> No, it is possible with very straight forward method (nothing hard-coded), just try to ovoid heaviest computation.

Lakshman-->Accepted. this was helpful(try to ovoid heaviest computation)

Last edit: 2014-04-07 14:39:58

Added by:Surya Kiran
Date:2014-03-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Insomnia 2014