Consider a meeting of n businessmen sitting around a circular table. To start the meeting, they must shake hands. We say that the shake is perfect if no arms cross each other and each businessman shakes the hand of exactly one other businessman. All handshakes happen simultaneously.

Input

First line contains an integer T(less than 5000) denoting the total number of test cases.

Each test case consists of a single integer n(1 <= n <= 5000) in one line.

Output

For each tese case, print the number of perfect shakes that exist for n businessmen modulo 1000000007.

Example

Input:
1

6

Output:

5