1013 - Grid

Time Limit: 1s Memory Limit: 128MB

Submissions: 86 Solved: 33
Description
There is a grid size of 1*N. The spanning tree of the grid connects all the vertices of the grid only with the edges of the grid, and every vertex has only one path to any other vertex. Your task is to find out how many different spanning trees in a given grid.
Input
Every line there is a single integer N(0 < N <= 1000000000), a line of 0 represents the end of the input.
Output
Every line you should only print the result, as the result may be very large, please module it with 1000000007.
Sample Input
1
2
0
Sample Output
4
15
Hint
When N=1, the spanning trees are an follows: _ |_ , |_| , _ _| , _ | | . There are four ways to construct the spanning tree.
Source
ASCII & ACman