A simple graph problem

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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.

Sample Input

3 1 2 3

Sample Output

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

Hint

hujie

Source

2015 ACM/ICPC Asia Regional Shanghai Online

提交代码