Alexey Yurievich and Mikhail Leonidovich — Chebarkul American football team coach. Today they have to fill out a very important form for the World Championship, in which they must indicate all the members of the team in ascending order of their strength.
To solve this difficult task, all the players of the national team were gathered, and each of the athletes said several (possibly zero) phrases like: "I am stronger than player k" (k may differ from statement to statement, no athlete said the same phrases). When the survey was over, the coaches realized that now they can unambiguously sort the athletes by strength, corresponding to all the statements.
Immediately after Alexey Yuryevich and Mikhail Leonidovich wrote a response to the organizers of the Olympiad, they thought, what would happen if the players answered differently? After all, not in all cases it is possible to restore the only possible order of the players.
Now they are wondering how many sets of athlete responses uniquely define their order? Since this number may be too large, they ask to find only its modulo 10
9+7.
Input
The input contains a single number n — number of athletes in the team (1 <= n <= 10
5) .
Imprint
Print a single number — the number of sets of athletes' answers that uniquely allow them to be sorted by strength.
Examples
Remark
In this test, there are only 2 answer options: the first one said that he is stronger than the second, the second did not say anything, or the first did not say anything and the second said that he was stronger than the first.