提示: 欢迎访问OurACM平台。
Problem 1559 Count Zeros

Accept: 215    Submit: 552
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

As is known to us all, any positive decimal integer can be expressed into a unique binary digit. For example the decimal number 13 can be expressed in the form of binary digit as 1101, your task is to count the total number of 0s in the binary digit of 1..2n. For example, if n = 2, then 2n = 4. Binary digits of 1,2,3,4 are 1,10,11,100. So the number of 0s is 3.

Input

There are multiple test cases. Each test case contains a non-negative integer n (n<=5000)

Output

For each test case, print the number of 0s which the binary digits of 1..2n contains. The result may be vary large, so output it mod 2007.

Sample Input

2 3

Sample Output

3 8

Source

FOJ月赛-2007年12月

Submit  Back  Status  Discuss