SPOJ in Gyumri

  “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 0→1→0 but you can’t walk on path 0→-1→0. 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 1 000 000 007 (Prime number).

Input

   First line of input is a number of test cases T ≤ 1 000.

   Each test case is a line contain an integers N (1 ≤ N ≤ 1 000 000)

Output

   For each test case, display an integer indicating the number of paths that you can walk modulo by 1 000 000 007

Examples