Zapina

문제

There is a total of N young programmers which are preparing for the second part of competitive season during a winter camp in Krapina Zagreb. Mr. Malnar, a big promoter of order, discipline and hard work, told the programmers to form a line and gave each of them a certain number (possibly zero) tasks. He gave away a total of N different tasks and he knows that the i-th programmer in line will be happy if they got exactly i tasks.

In how many different ways could Mr. Malnar give out the tasks in such a way that at least one programmer was happy? Two ways of giving out the tasks are considered different if there exists a programmer and a task such that in one way that programmer received that task while in the other one they didn’t.

입력

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

출력

Output the sought number of ways modulo 10⁹ + 7.