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 \le N \le 350)~ from task description.
Output the sought number of ways modulo ~10^9 + 7~.
|~1~||~22~||~1 \le N \le 7~|
|~2~||~33~||~1 \le N \le 20~|
|~3~||~55~||No additional constraints.|
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Explanation for Sample Output 2
Ways of giving out the tasks in which at least one programmer is happy are:
- First task to first programmer, second task to the second one.
- Second task to the first programmer, first task to the second one.
- Both tasks to the second programmer.
Sample Input 3
Sample Output 3