1013 - Grid
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