MMFBTEAM - Big team formation

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 ≤ 1030. 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

Added by:julkas
Date:2018-07-09
Time limit:2.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.