#À. 斐波那契数列Plus

    Type: Default 1000ms 256MiB

斐波那契数列Plus

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

大家都知道,斐波那契数列是满足如下性质的一个数列:

$$F_n = \begin{cases} 0& \text{if }n\text{== \ 0} \\ 1, & \text{if }n\text{<= \ 2} \\ F_{n-1} + F_{n-2}, & \text{if }n\text{ > \ 2} \end{cases} $$

请你求出 Fnmod109+7F_n \bmod 10^9 + 7 的值。

Description

一行一个整数 n

Format

Input

输出一行一个整数表示答案。

Output

One integer, the sum of x and y.

Samples

5
5

Limitation

【数据范围】 对于 60%60\% 的数据,0n920\le n \le 92; 对于 100%100\%的数据,1n<2631\le n < 2^{63}

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45