In 2021, Atomic Energy Highschool is going to have a Diploma Ceremony. During the ceremony, there are going to be some consulting sessions and during each session, two students will meet the counselor together. Bob is going to arrange these meetings during this ceremony. The school told Bob that each student should meet the counselor at least once and he should not send any group to the meeting twice (means that each pair of students should meet the counselor no more than once). Bob loves combinatorics very much so he wants to know that in how many ways he can set the arrangements but remember that the order is not important to him. In another way, two different arrangement means that in one arrangement there exists at least one pair of students A and B who meets the counselor together in exactly one of them.

Bob has solved this problem easily and now he wants to check his answers with yours, can you help him?

Input format

The first line contains an integer \(n\) denoting the number of students in the ceremony

Output format

You are required to print the number of different arrangements modulo 1000000007.

Constraints

\(2\leq n \leq 100000\)