题目背景

给大家讲个鬼故事

有一天晚上，下着大暴雨。小 K 正在他那小小的书房里做着老师给他布置的、数也数不完的信息题目。关着门，关着窗难免有些闷热。小 K 起身，将书桌前的窗子打开一个小小的细缝，小到没有雨点能透过缝隙飘进来。

今天正是农历七月十五日，中元节，俗称鬼节。小 K 从来都没有在这种日子这么晚睡过，因为小 K 迷信，害怕午夜之后，便有鬼怪出没。然而今天，小 K 无可奈何。

小 K 看了看时间：$23:54$。看到 $4$，小 K 皱了皱眉眉头。$4$，谐音是“死”，特别不吉利。在这种日子看到这样的字眼，往往都是不祥之兆。

小 K 的眼皮在打架。他从来都不会做毒瘤题。他索性趴到了书桌上面，两只眼睛渐渐朦胧了起来。

“那儿有一个本子。”他想着。不知道何时，他的书桌靠窗的一角上，静静地躺着一个湿漉漉的本子，好像是刚刚淋过雨。“它是怎么进来的？”小 K 喃喃道。他下意识地翻开那本本子，看到里面有写了一些字。不知道为什么，那些字在发黄的纸页上看起来也那么红。

左边的那一页写着：

$$4^{4-4}\le M\le N\le 4^{4^{(4+4-\frac{4}{4})}},\sqrt{4}\le K\le 4^{\sqrt{4}}\times(4-\frac{4}{4})+\sqrt{4} $$

右边的那一页写着的似乎比左边的要长：

$$a_{\frac{4}{4}}=a_{\sqrt{4}}=\frac{4}{4},a_n=\frac{\sqrt{4}}{\sqrt{4}}\times a_{n-\frac{4}{4}}+4^{4-4}\times a_{n-\sqrt{4}}(n\ge \sqrt{4}+\frac{4}{4}) $$$$b_n=\prod^{n+K-\frac{4}{4}}_{i=n}a_i$$

求 $\sum\limits_{i=m}^n b_i$

角落里还有一行小字：_ 不要翻到最后一页，不然会有可怕的事情发生 _。但是在这个时候，小 K 早已经闭上了双眼，鼾声和远处的雷声混成一片。

一阵微风吹来，轻轻地，谁也没有意识到。本子的一角被风扬起，滑过一个优美的弧线，落在了本子的另一边。风一阵一阵的吹来，拂过本子发黄的书页。渐渐地，右边的书页少了，左边的书页多了。风停了，本子的倒数第二页停在半空中。在一刹那，似乎一切都静止了。然后，它轻轻地落在了其它书页的最上面。

最后一页上，赫然用鲜红色的歪歪扭扭的大字写着：

这道题你已经拖了一个月了！限明天之前做完！

这时候，你夜观天象，预测到了小 K 的这场劫难。时间已是 $23:59:59:400$，如果在这 $1000-400=600$ 毫秒内没有做完，小 K 的检讨将在劫难逃。身为小 K 的好朋友，你能帮他解决这个问题吗？

题目描述

给定 $k,m,n$，求：

$$\sum_{i=m}^n \prod_{j=i}^{i+k-1} a_j$$

答案对 $10^9 + 7$ 取模。
其中 $\{ a\}$ 为 fibonacci 数列。

输入格式

三个正整数，分别表示 $k,m,n$。

输出格式

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

4 1 3

276

3 2 3

36

提示

$a_1=1,a_2=1,a_3=2,a_4=3,a_5=5,a_6=8$。

对于样例1：

$$K=4$$ $$b_1=1\times1\times2\times3=6,b_2=1\times2\times3\times5=30,b_3=2\times3\times5\times8=240 $$$$\sum_{i=1}^{3}b_i=276$$

对于样例2：

$$K=3$$ $$b_2=1\times2\times3=6,b_3=2\times3\times5=30$$ $$\sum_{i=2}^{3}b_i=36$$

本题共有 $20$ 个数据点，每个数据点的分数均为 $5$ 分，总分为 $100$ 分。每个数据点的性质如下：

(出题人不想再用 $4$ 表示任何数了！真香)

编号	$K,M,N$范围	特殊性质
$1$	$1\le m\le n\le 10^6,k=4$	无
$2$	$1\le m\le n\le 10^{18},k=4$	$n-m\le 10^6$
$3\sim 4$		无
$5\sim 6$	$1\le m\le n\le 4^{4^4},k=4$	$n-m\le 10^6$
$7\sim 10$	$1\le m\le n\le 4^{4^7},k=4$	无
$11\sim 12$	$1\le m\le n\le 4^{6000},2\le k\le 10$
$13\sim 14$	$1\le m\le n\le 10^{41},2\le k\le 10$
$15\sim 20$	$1\le m\le n\le 10^{41},2\le k\le 50$

（注意，题面中的数据范围只是大致描述，请以以上具体范围为准）

$a^{b^c}=a^{(b^c)}$