题目描述

《集合论与图论》这门课程有一道作业题，要求同学们求出 $\{1, 2, 3, 4, 5\}$ 的所有满足以下条件的子集：若 $x$ 在该子集中，则 $2x$ 和 $3x$ 不能在该子集中。

同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 $n\,(1\leq n\leq 10^5)$，如何求出 $\{1,2,\dots,n\}$ 的满足上述约束条件的子集的个数（只需输出对 $10^9+1$ 取模的结果），现在这个问题就交给你了。

输入格式

只有一行，其中有一个正整数 $n$。

输出格式

仅包含一个正整数，表示 $\{1,2,\dots,n\}$ 有多少个满足上述约束条件的子集。

4

8
 

提示

【样例解释】

有 $8$ 个集合满足要求，分别是 $\varnothing$、$\{1\}$、$\{1,4\}$、$\{2\}$、$\{2,3\}$、$\{3\}$、$\{3,4\}$ 和 $\{4\}$。

【数据范围】

对于 $30\%$ 的数据，$1\le n\le 20$。
对于 $100\%$ 的数据，$1\le n\le 10^5$。