题目描述

给定 $n$，定义集合 $S$ 是好的集合当且仅当：

$$\forall \;x\in S,1\le x\le n\;\land 2x\not\in S\land 3x\not\in S$$

求 $\{1,2,3,\cdots,n\}$ 的子集有多少是好的集合，答案对 $10^9+1$ 取模。

Provided by 飞丞。

输入格式

一行一个整数 $n$，如题意所示。

输出格式

一行一个整数表示答案。

数据范围

对于 $30\%$ 的数据，$1\le n\le20$

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

## 题目描述

给定 $n$，定义集合 $S$ 是好的集合当且仅当：

$$
\forall \;x\in S,1\le x\le n\;\land 2x\not\in S\land 3x\not\in S
$$

求 $\{1,2,3,\cdots,n\}$ 的子集有多少是好的集合，答案对 $10^9+1$ 取模。

Provided by 飞丞。

## 输入格式

一行一个整数 $n$，如题意所示。

## 输出格式

一行一个整数表示答案。

## 数据范围

对于 $30\%$ 的数据，$1\le n\le20$

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

@Sserxhs