1043  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