#P100087. 水题

水题

题目背景

众所周知,斐波那契(Fibonacci)数列是一种 很快 增长很快的数列。

勤学好问的 CC 在学完 Fibnacci 数列后提出了一个问题。

他想知道,斐波那契数列的前 nn 个质数(素数)项之和是多少?

题目描述

给定一个数 nn,求斐波那契的前 nn 个质数项之和是多少,由于可能很大,请将答案 mod1000000007\mod 1000000007 后输出。

举个例子,若 n=4n=4,设斐波那契数列的第 xx 项为 f(x)f(x),则答案为 $\left(f(2) + f(3) + f(5) + f(7)\right) \mod 1000000007 = 21$

输入格式

输入一个数 nn,如题目中描述。

输出格式

输出题目中描述的答案

样例

4
21

提示

对于 20%20\% 的数据 0n500 \leq n \leq 50

对于 50%50 \% 的数据 0n1020 \leq n \leq 10^2

对于 100%100 \% 的数据 0n1060 \leq n \leq 10^6