Problem Description

Suppose you have a graph with only n vertices and no edges. Now for every vertex you will select a vertex randomly and equiprobability, and then add an undirected edge between them (multiple edges and self-loop is allowed). At last you will have a graph with n vertices and n edges. So would you mind telling me what is the expected number of the cut vertices. (If you delete a cut vertex in a graph, the number of connected block in this graph will increase)

Input

The first line contains a number T, indicating the number of test cases.($1 \leq T \leq 50$)
For each case, there are only one number n ($1 \leq n \leq 10^5$), as described previously.

Output

For each case, first please output "Case #k: ", k is the number of test case. See sample output for more detail. And then, output the answer multiply $n^n$(mod $10^9 + 7$), to make sure the answer will always be an integer.

3
1
2
3

Case #1: 0
Case #2: 0
Case #3: 15