[HNOI2012] 集合选数

题目描述

《集合论与图论》这门课程有一道作业题,要求同学们求出 $\{ 1, 2, 3, 4, 5 \}$ 的所有满足以下条件的子集:若 $x$ 在该子集中,则 $2x$ 和 $3x$ 不能在该子集中。 同学们不喜欢这种具有枚举性质的题目,于是把它变成了以下问题:对于任意一个正整数 $n \le 10^5$,如何求出 $\{1,2,\ldots ,n\}$ 的满足上述约束条件的子集的个数(只需输出对 $10^9+1$ 取模的结果),现在这个问题就交给你了。

输入输出格式

输入格式


只有一行,其中有一个正整数 $n$。$30 \%$ 的数据满足 $n \le 20$。

输出格式


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

输入输出样例

输入样例 #1

4

输出样例 #1

8
 

说明

**【样例解释】** 有 $8$ 个集合满足要求,分别是空集,${1}$,$\{1,4\}$,$\{2\}$,$\{2,3\}$,$\{3\}$,$\{3,4\}$,$\{4\}$。 **【数据范围】** 对于 $30 \%$ 的数据,$n \le 20$。 对于 $100 \%$ 的数据,$1 \le n \le 10^5$。