Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 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
Submit