Description

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

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

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

Input Format

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

Output Format

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

4 1 3

276

3 2 3

36

Hint

$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)}$