|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||4||4||2||100.000%|
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 109 + 7.
Ways of giving out the tasks in which at least one programmer is happy are: