Description

Given $k,m,n$, find:

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

Take the answer modulo $10^9 + 7$.
Here $\{ a\}$ is the Fibonacci sequence.

Input Format

Three positive integers, representing $k,m,n$ respectively.

Output Format

Output one line with one integer, representing the answer.

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$.

For Sample 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$$

For Sample 2:

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

This problem has $20$ test points. Each test point is worth $5$ points, for a total of $100$ points. The properties of each test point are as follows:

(The problem setter does not want to use $4$ to represent any number anymore! so true)

ID	Constraints on $K,M,N$	Special Property
$1$	$1\le m\le n\le 10^6,k=4$	None
$2$	$1\le m\le n\le 10^{18},k=4$	$n-m\le 10^6$
$3\sim 4$		None
$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$	None
$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$

(Note: the Constraints described in the statement are only approximate. Please refer to the specific ranges above.)

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

Input Format

Three positive integers, representing $k,m,n$ respectively.

Output Format

Output one line with one integer, representing the answer.

Hint

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

For Sample 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$$

For Sample 2:

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

This problem has $20$ test points. Each test point is worth $5$ points, for a total of $100$ points. The properties of each test point are as follows:

(The problem setter does not want to use $4$ to represent any number anymore! so true)

ID	Constraints on $K,M,N$	Special Property
$1$	$1\le m\le n\le 10^6,k=4$	None
$2$	$1\le m\le n\le 10^{18},k=4$	$n-m\le 10^6$
$3\sim 4$		None
$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$	None
$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$

(Note: the Constraints described in the statement are only approximate. Please refer to the specific ranges above.)

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

Translated by ChatGPT 5