Zapina

Time limit1sMemory limit512 MB

Summary

Count the ways to assign N distinct tasks to N programmers so that at least one programmer i receives exactly i tasks, modulo 1e9+7.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Math, Number theory
Solved: No attempts yet

Problem

A total of N young programmers are preparing for the second part of the competitive season at a winter camp in Krapina, near Zagreb. Mr. Malnar, a strong advocate of order, discipline, and hard work, told the programmers to form a line and gave each of them some number of tasks (possibly zero). He gave away a total of N distinct tasks, and he knows that the i-th programmer in line will be happy if they received exactly i tasks.

Find the number of different ways Mr. Malnar could give out the tasks such that at least one programmer is happy. Two ways of giving out the tasks are different if there is a programmer and a task such that in one way the programmer received that task and in the other they did not.

Input

The first line contains an integer N (1 ≤ N ≤ 350) from the task description.

Output

Output the number of ways sought, modulo 109 + 7.

Examples3

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
2
```
Expected output
```
3
```
Example 3
Input
```
314
```
Expected output
```
192940893
```