#5129. 鲜为人知的斐波那契数列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: long_hao

题目描述

众所周知,大帅非常喜欢计算,尤其是 int128 的运算。不过这道题跟 int128 爆零没关系,但是和计算有关系。

身为斐波那契数列系列的第二弹,自然要起到承前启后的作用,故按照以往大帅的风格和水平,这又是一道水题。

大帅会给出你一个数字 k ,这个数字非常神奇,不过这次大帅不打算问你第 k 项的斐波那契了,他打算问你一个 longhao 数,我们规定 longhao 数为 (f_2+f_4+f_6+\cdots+f_{k,or,k-1})-(f_3+f_5+f_7+\cdots+f_{k,or,k-1}) ,你肯定懒得回答这个问题,不过你决定还是给出一个答案。

答案对 100000007 ,也就是 10^8+7 取模。

感觉这次又会被各种打脸。

Update:发现我出题的时候重新整理的思路比前两天想的要复杂得多,另外更新公式表达。

输入格式

一行表示数字 k

输出格式

一行表示你的答案。

样例

自己手算

样例输入

10

样例输出

34

数据范围与提示

对于 100\% 的数据 2\leq k \leq 10^{17}

出题人很恶心的要求使用 long long