背景

打表是一种将答案记录下来的方法。一般打表将答案直接放入数组。

ZY 在 21 年掌握了打表，企图暴力讨分。

题目描述

可以定义斐波那契数列第一项为 $0$，第二项为 $1$，接下来的第 $i$ 项 $=$ 第 $i-1$ 项 $+$ 第 $i-2$ 项，求斐波那契数列的第 $n$ 项，结果对 $10^9+7$ 取模。

这本事一件简单的事。但是小X要整活，贪污掉了大量的时间资源拿来打元，导致评测时间只有 50ms 。小X本来只想留10ms。

输入格式

一个正整数 $n$

输出格式

一个整数表示答案，对 $10^9+7$ 取模

样例

114514

871930766

数据范围

对于$100\%$的数据，$1\le n\le 2\times 10^8$

提示

严格的时间限制使得你只能一次性处理$10^7$的数据。

关于数组的某些赋值方法：

本地控制台转文件输出：

freopen函数可以用于将程序运行所有输出数据放入文件。这个函数一般放在主函数开头。

eg.

#include<bits/stdc++.h>
using namespace std;

int main(){
    freopen("test.txt","w",stdout);
    cout<<"Hello world";
    return 0;
}

这个程序运行后会在程序的位置生成一个文件test.txt，文件内容是Hello world

后记

ZY没看见文件规定，代码长度不能超过100KB，否则评测机会直接跳过，不计分。