Counting spanning tree
Time Limit : 1 Second
Memory Limit : 64 MB
Submission: 95
Solved: 24
- Description
- There are n distinct points on a line, only neighboring points have an edge between them. There are also two points outside the line, both of the two points have an edge with every point on the line, but there is no edge between the two points.
You are asked to count the number of the spanning trees among the N + 2 points. - Input
- There are multi test cases.
Each case contains a line with an integer n, 1 <= n <= 100000000. - Output
- For each test case, output one line containing the result. As the result may be very large, please mudule it with 1000000007.
- sample input
-
1 2
- sample output
-
1 8
- hint
- source
- Du Peng