Unique paths

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 128 MB
Avtor:
  • Tomaž Hočevar
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Write a program that will determine the total number of all connected graphs (undirected and unweighted) with vertices labelled 1 through N, and with the property that there is a unique shortest path from vertex 1 to every other vertex.

Input

The first lines contains the integer N, i.e. the number of vertices of the graph.

Input limits

  • 2 \leq N \leq 300

Output

Since the answer can be a very large number, output the answer modulo 1\,000\,000\,007.

Examples

Input

3

Output

4

Input

4

Output

32

Comment

In the figure below there are all four such graphs on 3 vertices.

N=3

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task