CountSpanningTree

Given an un-directed, complete graph with n vertexes. Count the number of spanning tree in this graph. Since the answer can be large, return the answer modulo 1000000007(1e9+7) 

Example: 

• If n=3, the answer is 3.3 Spanning trees are: {1-2,1-3},{1-2,2-3}, {1-3,2-3}

Input/Output

• [execution time limit] 1 second

• [input] integer n

  Guaranteed constraints:
  1 ≤ n ≤ 10000.

• [output] integer

  • the answer to the problem, modulo 1e9+7

Note

A complete graph is a graph in which each pair of graph vertices is connected by an edge

A spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges.