选数

题目描述

给定一个正整数 n，从数字 1 到 n 中选择若干个数字（所选集合不能为空），且任意两个被选中的数字在数轴上不能相邻。求符合条件的方案数，结果对 1000000007 取模。

输入格式

第一行：单个整数 n。

输出格式

输出一个整数，表示方案数模 1000000007 的结果。

输入样例

3

输出样例

4

说明提示

· 对于 30% 的数据，n≤20；

· 对于 60% 的数据，n≤10,000；

· 对于 100% 的数据，1≤n≤100,000。

限制

时间限制：1000ms

内存限制：512MiB