# Homework of Politics

Homework of Politics

After the Politics class, the teacher gives the student a homework.But Nobita and Takeshi don't like this homework at all.So they decide to play a game, and the person who lost will do the homework of them.This game is like this.At first Nobita chose one or more numbers from [1,n], he can chose all numbers,but each number can be chosed at most once.We think that Nobita choses m numbers, which are a1,a2,...,am.And then they will find m heap of stones, for the ith heap of stone, there are ai stones.And then Nobita and Takeshi will play the game in turn, Nobita plays the first turn.On each turn, the person should chose one heap of stones, and take one or more stones from this heap.And if the number of stones in this heap before is N, the number of stones in this heap after is M, N%M=0 and M!=0 are needed (% means the mod operation). The person who can't do anything will lost the game.Now Nobita wants to know how many ways Nobita can chose from [1,n], that will make sure Nobita wins the game.
Input
The first line contains an integer n.
(1<=n<=10^6).
Output
Output the answer % 1000000007.

Sample Input

8
Sample Output

192