# Unique paths

### Osnovne informacije

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

### Pošlji rešitev

Source: (Auto) text C C++ Pascal Java Python 2 Python 3 Perl C# Prolog (SWI) Ruby

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$1$ through N$N$, and with the property that there is a unique shortest path from vertex 1$1$ to every other vertex.

## Input

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

### Input limits

• 2 \leq N \leq 300$2 \leq N \leq 300$

## Output

Since the answer can be a very large number, output the answer modulo 1\,000\,000\,007$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$3$ vertices.