F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:替用户ir1d发布如下信息,希望大家能够积极支持。 OI Wiki 致力于成为一个开放自由的 OI 知识整合站点,欢迎感兴趣的同学参与贡献 https://oi-wiki.org
Problem 2734. -- [HNOI2012]集合选数

2734: [HNOI2012]集合选数

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1900  Solved: 1125
[Submit][Status][Discuss]

Description

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

Input

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

Output


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

Sample Input


4

Sample Output

8

【样例解释】

有8 个集合满足要求,分别是空集,{1},{1,4},{2},{2,3},{3},{3,4},{4}。

HINT

Source

day2

[Submit][Status][Discuss]

HOME Back