#H0011. Jiang学长的WF之路(九)

Jiang学长的WF之路(九)

题目背景

由于评测机出现了罕见的 Bug,本场 XCPC 的罚时计算方式变成了斐波那契数列。

题目描述

通过第 ii 道题产生的“基础罚时”恰好是斐波那契数列的第 iiFiF_i。 已知 F1=1F_1 = 1, F2=1F_2 = 1, 且对于 i>2i > 2Fi=Fi1+Fi2F_i = F_{i-1} + F_{i-2}。 Jiangrc 艰难地通过了第 LL 道题到第 RR 道题(包含两端)。请计算这段时间内产生的“基础罚时”总和,结果对 1000000007 取模。

输入格式

一行包含两个正整数 LLRR (1LR1051 \le L \le R \le 10^5)。

输出格式

输出一个整数,表示基础罚时总和对 1000000007 取模后的结果。

样例

3 5
10

样例解释

斐波那契数列的前几项为:F1=1,F2=1,F3=2,F4=3,F5=5F_1=1, F_2=1, F_3=2, F_4=3, F_5=5。 Jiangrc 通过了第 3 道到第 5 道题,产生的罚时总和为 F3+F4+F5=2+3+5=10F_3 + F_4 + F_5 = 2 + 3 + 5 = 10。 10 对 1000000007 取模的结果仍为 10。