eolymp
bolt
Try our new interface for solving problems
Problems

Random Walks

Random Walks

Time limit 1 second
Memory limit 64 MiB

"Thorfun Company Limited" aka "thorfun.com", a social network for blogger, writer and reader, founded by four new graduated. One of them is passion in computational problems. One day he found something very interesting because, it is a solution of various problems and “Random Walks” is one of them. Given a one dimensional line and you stand at the original point (position 0). At each step you can walk either left or right for unit length.

First, let us have a look at a basic version of the problem. You can walk whatever you want for 2N steps but, you must end at the original point. How many different paths that you can walk? The solution is very simple. You start and end at the same point, it means that you must take the same number of left and right step. Choosing N for the right and the other N for the left from 2N steps is equal to .

"Random Walks" problem is similar to the basic problem. However, during the walks you must not walk into negative integers. For example, if N = 1 you can walk on the path 010 but you can’t walk on path 0-10. You task is to write a program to compute the number of path that follow the above rules. In addition, the result may be very large. So, print the result modulo by 1000000007 (Prime number).

Input data

First line of input is a number of test cases T1000.

Each test case is a line contain an integers N (1N1000000).

Output data

For each test case, display an integer indicating the number of paths that you can walk modulo by 1000000007.

Examples

Input example #1
3
1
3
6
Output example #1
1
5
132
Source ACM ICPC Asia Thailand National programming Contest 2013