集合选数 ### 题目描述 《集合论与图论》这门课程有一道作业题，要求同学们求出 $\{1, 2, 3, 4, 5\}$的所有满足以 下条件的子集：若 $x$ 在该子集中，则 $2x$ 和 $3x$ 不能在该子集中。 同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数 $n \leq 10^5$，如何求出 $\{1, 2,\cdots, n\}$ 的满足上述约束条件的子集的个数（只需输出对 $1000000001$ 取模的结果），现在这个问题就交给你了。 ### 输入描述 只有一行，其中有一个正整数 $n$。 其中，$n \leq 10^5$。 ### 输出描述 仅包含一个正整数，表示 $\{1, 2,\cdots, n\}$ 有多少个满足上述约束条件 的子集。 ### 输入输出样例 #### 示例 1 >输入 ```txt 4 ``` >输出 ```txt 8 ```