题目描述

“其实我也带了一些材料过来，一会还会安排我发言呢”Marvolo忽然对身旁的Mike说。”那你现在怎么不去准备？”Mike觉得这件事没那么简单。”我的确带了材料，可是放到了我的一个微型保险箱中，重要的是我忘了保险箱的密码……””我什么都不说，这是最吼的”

Marvolo虽然忘了密码，但是因为知道自己的记性不好，所以他提前给自己留了一个提示。短短的只有一行”集合$\{1,2,\dots,n\}$中所有不包含相邻正整数的子集个数。”

输入格式

一行一个正整数$N$。

输出格式

Marvolo的密码，答案对$10^{9}+7$取模。

样例输入

ex_answer1.in

3

样例输出

ex_answer1.ans

5

满足条件的所有子集为$\{1\},\{2\},\{3\},\{1,3\},\{空集\}$，共$5$个。

数据范围

对于$30\%$的数据，$N \leq 10^{3}$

对于另外$20\%$的数据，$N \leq 10^{5}$

对于另外$30\%$的数据，$N \leq 10^{7}$

对于剩下的$20\%$的数据，$N \leq 10^{9}$

时间限制：1s

空间限制：256M

样例数据下载