《集合论与图论》这门课程有一道作业题，要求同学们求出 $\{1, 2, 3, 4, 5\}$ 的所有满足以 下条件的子集：若 $x$ 在该子集中，则 $2x$ 和 $3x$ 不能在该子集中。同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 $n≤100000$，如何求出 $\{1, 2,..., n\}$ 的满足上述约束条件的子集的个数（只需输出对 $1,000,000,001$ 取模的结果），现在这个问题就交给你了。
只有一行，其中有一个正整数 $n$，$30\%$ 的数据满足 $n≤20$。
仅包含一个正整数，表示 $\{1, 2,..., n\}$ 有多少个满足上述约束条件的子集。
4
8
有 $8$ 个集合满足要求，分别是：空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。
Comet OJ