Description

The course "Set Theory and Graph Theory" has a homework problem asking 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 enumeration-style problems, so they turned it into the following question: for any positive integer $n\,(1\leq n\leq 10^5)$, how many subsets of $\{1,2,\dots,n\}$ satisfy the above constraint (you only need to output the result modulo $10^9+1$). Now this task is handed to you.

Input Format

A single line containing a positive integer $n$.

Output Format

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

4

8

Hint

Sample explanation:
There are $8$ sets that meet the requirement, namely $\varnothing$, $\{1\}$, $\{1,4\}$, $\{2\}$, $\{2,3\}$, $\{3\}$, $\{3,4\}$, and $\{4\}$.

Constraints:
For $30\%$ of the testdata, $1 \le n \le 20$.
For $100\%$ of the testdata, $1 \le n \le 10^5$.

Translated by ChatGPT 5