
111  ZOJ Monthly, October 2011  J
Given a set S = {1, 2, ..., n}, your job is to count how many set T satisfies the following condition:
InputThere are multiple cases, each contains only one integer n ( 1 ≤ n ≤ 10^{9} ) in one line, process to the end of file. OutputFor 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 Input2 3 Sample Output1 4 Author: LI, Dinghua 