《集合论与图论》这门课程有一道作业题，要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集：若 x 在该子集中，则 2x 和 3x 不能在该子集中。同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数 n≤100000，如何求出{1, 2,..., n} 的满足上述约束条件的子集的个数（只需输出对 1,000,000,001 取模的结果），现在这个问题就 交给你了。
[HNOI2012]集合选数
| 成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
| 折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
| 允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
| 输入文件 | bzoj_2734.in | 输出文件 | bzoj_2734.out |
【题目描述】
【输入格式】
只有一行，其中有一个正整数 n，30%的数据满足 n≤20。
【输出格式】
仅包含一个正整数，表示{1, 2,..., n}有多少个满足上述约束条件 的子集。
【样例输入】
4
【样例输出】
8
【样例解释】
有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。
【提示】