Description

【题意】
有 N 个小朋友排成一排 , 每个小朋友有两种可能的状态 : 吃零食和没吃零食
要求 :
1. 吃零食的小朋友旁边至少要有 1 个没吃零食的小朋友
2. 没吃零食的小朋友旁边一定都是吃零食的小朋友
求可能的方案数。

【输入】
一个数 N
对于前50%的数据(3<=N<=5*10^7)
对于所有数据 3<=N<=10^18(还没完成)

【输出】
最终的方案数对 (1e9+7) 取模

【样例输入】
15

【样例输出】
12