When Bruce learned set theory, he assigned a homework question to his students.

Given a positive integer $N$, find the number of subsets of the whole set $\{1,2,\dots ,N\}$ that satisfies the following constraint: if an integer $x$ is in the subset, then the integers $2x$ and $3x$ are not in the subset. For example, given $N=4$, the whole set is $\{1,2,3,4\}$. The number of subsets satisfying the constraint is $8$, including the empty set: $\mathrm{\varnothing }$, $\{1\}$, $\{1,4\}$, $\{2\}$, $\{2,3\}$, $\{3\}$, $\{3,4\}$, and $\{4\}$.

Input Specification

The input will consist of one integer $N$ $(1\le N\le 100000)$.

Output Specification

Output the number of subsets that satisfy the above constraints mod $1000000001$ $(={10}^9+1)$.

Sample Input

4

Sample Output

8