1043 - Counting spanning tree

Time Limit: 1s Memory Limit: 64MB

Submissions: 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