E Combinatorics PTSD
测试数据来自 nnu_contest/1249
E Combinatorics PTSD
时间限制:2s
空间限制:64MB
题目描述
从无序的集合\(\{1,2,3,...,n\}\)中任取一个子集,问:有多少个子集满足:
不存在两个元素\(x,y\)使得\(y-x=1\)?
例如:若\(n\ge10\),\(\{1,3,7,10\}\)是符合条件的集合,\(\{1\}\)也是符合条件的集合。但\(\{1,3,4\}\)不是,因为\(4-3=1\)。
由于答案可能过大,对\(10^9+7\)取模。
输入格式
一个正整数\(n\)
输出格式
子集的个数,请对\(10^9+7\)取模
样例输入1
3
样例输出1
5
样例1解释
\(\varnothing,\{1\},\{2\},\{3\},\{1,3\}\)
样例输入2
15
样例输出2
1597
样例输入3
19937
样例输出3
741958915
数据范围及限制
\(1\le n\le 10^6\)
信息
- ID
- 2299
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者