Problem Background

On November 17, 2018, Hong Kong, China, will host a major battle known as the "XM War," where ENLIGHTENED and RESISTANCE factions from around the world will clash. The ENLIGHTENED Headquarters in a certain location also plans to dispatch Agents to join this XM War and fight alongside ENLIGHTENED forces from other regions.

Problem Description

The ENLIGHTENED Headquarters has $N$ Agents, each with unique ability values. The ENLIGHTENED Operations Commander wants to send two teams, $A$ and $B$, of Agents to participate in the XM War. However, the two teams must meet the following requirements:

1. The highest ability value in team $A$ must be less than the lowest ability value in team $B$.
2. Both teams must have at least one member.

Not all Agents need to participate in the XM War. The impatient ENLIGHTENED Operations Commander wants to know how many ways there are to arrange the Agents for the war. Since the answer could be very large, you only need to output the result modulo $(10^9 + 7)$.

Input Format

The input consists of a single integer $N$.

Output Format

Output the result modulo $(10^9 + 7)$.

Sample Input and Output

Sample Input #1

3

Sample Output #1

5

Sample Input #2

6

Sample Output #2

129

Notes/Hints

For $20\%$ of the test cases, $N \leq 10$.

For $40\%$ of the test cases, $N \leq 10^3$.

For $60\%$ of the test cases, $N \leq 10^5$.

For $100\%$ of the test cases, $N \leq 10^9$.

见题面 Input 部分

见题面 Output 部分