P3226 [HNOI2012] Set Selection

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.

A single line containing a positive integer $n$.

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

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