Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3558
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
Contest: ZOJ Monthly, October 2011
Submit    Status