Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
111 - ZOJ Monthly, October 2011 - J
How Many Sets III

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Given a set S = {1, 2, ..., n}, your job is to count how many set T satisfies the following condition:

Input

There are multiple cases, each contains only one integer n ( 1 ≤ n ≤ 109 ) in one line, process to the end of file.

Output

For each case, output an integer in a single line: the total number of set T that meets the requirmentin the description above, for the answer may be too large, just output it mod 100000007.

Sample Input

2
3

Sample Output

1
4

Author: LI, Dinghua
Submit    Status