As we all know due to the corona outbreak maintaining social distance is very important. To implement such a thing you came up with an idea. A class consists of N boys and N girls, you have to select N students and form a queue K such that there are no three boys standing consecutively next to each other without a girl in between. Furthermore, two queues K is considered to be different if there is a position in K1 at which there is a boy but in the same position in K2, there is a girl or vice versa.
Print the total number of ways in which such distinct queues can be formed modulo 10^9 + 7.
Input format:
- First line : T denoting test cases
- Next T lines: N denoting the number of boys and girls in the classroom.
Output format:
For each test case print the number of valid queues modulo 10^9+7.
Constraints:
1 <= T <= 1000000
1 <= N <= 1000000
No editorial available for this problem.