SPOJ Brasil

Coach has n players. A team is a subset of players and has at least two players - a captain and a keeper. How many ways can a coach form a team from n players?

Input

Each line of input contains one random integer number 2 ≤ n ≤ 10⁶ (1 000 000). Input terminates with 0 (zero).

Output

For each n print your answer modulo 1 000 000 007 on new line.

Example

Input:
2
3
0

Output:
2
12

22/06/2019 - Time limit increased.