测试数据来自 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$