A homework problem in the "Set Theory and Graph Theory" course asks students to find all subsets of $\{1, 2, 3, 4, 5\}$ that satisfy the following condition: if $x$ is in the subset, then $2x$ and $3x$ cannot be in the subset. Students do not like such problems that require enumeration, so they have transformed it into the following problem: for any positive integer $n \le 100000$, how to find the number of subsets of $\{1, 2, \dots, n\}$ that satisfy the above constraint (only the result modulo $1,000,000,001$ needs to be output). Now, this problem is handed to you.

Input

The input contains a single line with a positive integer $n$, where $30\%$ of the data satisfies $n \le 20$.

Output

The output contains a single positive integer representing the number of subsets of $\{1, 2, \dots, n\}$ that satisfy the above constraint.

Examples

Input 1

4

Output 1

8

Note

There are 8 subsets that satisfy the requirements: the empty set, $\{1\}$, $\{1, 4\}$, $\{2\}$, $\{2, 3\}$, $\{3\}$, $\{3, 4\}$, and $\{4\}$.