Background

On November 17, 2018, Hong Kong, China will host an XM war, where ENLIGHTENED and RESISTANCE from all over the world will fight. An ENLIGHTENED headquarters in some place also wants to send Agents to join this XM war, fighting side by side with ENLIGHTENED from other places.

Problem Description

An ENLIGHTENED headquarters in some place has $N$ Agents, and each Agent has a different ability value. Now the ENLIGHTENED operation commander wants to send two teams of Agents, Team $A$ and Team $B$, to take part in the XM war. However, the two teams must satisfy two requirements:

1. The ability value of the strongest Agent in Team $A$ must be less than the ability value of the weakest Agent in Team $B$.
2. Both Team $A$ and Team $B$ must have at least one person.

Not all Agents must go to the XM war. The impatient ENLIGHTENED operation commander wants to know how many different ways there are to arrange Agents to join the war. Since the answer may be very large, you only need to output the value of the answer modulo $(10^9+7)$.

Input Format

The input contains only one line, an integer $N$.

Output Format

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

3

5

6

129

Hint

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

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

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

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

Translated by ChatGPT 5