鬼故事

### _给大家讲个鬼故事_ 有一天晚上，下着大暴雨。小 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$ | $1\le m\le n\le 10^{18},k=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)}$