P4936 Agent1

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.

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)$.

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

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

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