文理学院程序设计在线练习


The long journey

Time Limit: 1 Second(s)    Memory Limit: 128 MB

Total Submission(s): 20   Accepted Submission(s): 10
Problem Description

Don is planning for a long journey. There are n cities in the map. The cities are connected with each other. Don wants to go from city 1 to city 2. However, Don is not satisfied with direct arrival. Don's initial position is city 1, and his destination is city 2. He wants to calculate the number of different nice ways he can go from city 1 to city 2.A way is nice means there is no such a city appears more than once on the way. For example, when the number of cities is 3, 1 - > 2 is a good way, 1 - > 3 - > 2 is another good way, but 1 - > 3 - > 1 - > 2 is not good for 1 appears twice, so we have two ways in total. Given the answer maybe too large, please output the answer module 10 ^ 9 + 7 (100000007).

Input

The first row contains an integer T indicating the number of tests.
Each test contains an integer n, n is the number of cities.
We ensure that T <= 10000 and 2<= n <= 10,000,000.

Output

Output each answer in one line.

Sample Input
2
2
4
Sample Output
1
5
Hint

When the number of cities is 4:

There are
1 - > 2

1 - > 3 > 2

1 - > 4 - > 2

1 - > 3 - > 4 - > 2

1 - > 4 - > 3 - > 2

Five ways. So the answer is 5.

Source

2019绍兴市计算机技能竞赛