N friends are going to market. The shops of the market are located alongside a one-way road. There are N shops. Each shop has a parking space in front of it.
Now, each friend has shop preference. If somebody prefers shop number x, obviously he would like to park in front of x. So, for N friends, we have a preference list: [a_1, a_2, a_3.... a_N]. This indicates who prefers which parking spot.
Now, these N people will arrive with a car of their own and enter the one-way road one by one. They are very optimistic and hope to find their preferred parking spot empty. So they immediately travel to their preferred parking slot and try to park there. If the parking spot is empty, then great, they park there. But, if unfortunately, the parking slot is already occupied by someone else, they simply park at the next empty slot (they can't backtrack as its a one-way road). If they can't park at all, they leave.
A preference list of length N is said to be valid if everyone is able to park somewhere. If anybody is forced to leave due to not finding any free parking slots, then the preference list is invalid.
For example, for N = 5, the following preference list: [2, 4, 4, 1, 1], is valid. How? The first person arrives and parks at position 2. The second person arrives and parks at position 4. Third person arrives and finds position 4 booked, so parks at position 5 instead (parking at position 3 is not possible since he is already in front of parking spot 4 and the road is one way that allows moving forward only). Fourth person arrives and parks at position 1. The fifth person arrives and finds position 1 booked, so parks at position 3. Everyone manages to park somewhere, so this preference list is valid.
For N = 5, the following preference list is not valid: [1,2,3,5,5]. Why? First person arrives and parks at position 1. Second person arrives and parks at position 2. Third person arrives and parks at position 3. Fourth person arrives and parks at position 5. Fifth person arrives and finds position 5 booked. There is no empty parking spot after position 5. So he is forced to leave. Since fifth person can't park, this list is not valid.
Now, given the value of N, you have to find how many valid preference lists are there whose length is N.
Input
The first line contains a single integer T (T <= 100). Next, T lines follow, with a single integer on each line denoting the value of N (1 <= N <= 100).
Output
For each test case, print the case number and number of valid preference list of length N. Since the output can be huge, print it modulo 10^9 + 7. See sample input/output for more details.
Sample
| Input | Output |
|---|---|
3 1 2 3 | Case 1: 1 Case 2: 3 Case 3: 16 |
