Background

Let me tell you a ghost story

One night, a heavy rainstorm was pouring down. Little K was doing the endless informatics problems assigned by his teacher in his tiny study. With the door and windows closed, it inevitably felt a bit hot and stuffy. Little K stood up and opened the window beside his desk by a tiny crack, so small that no raindrops could drift in through it.

Today happened to be the 15th day of the 7th lunar month, the Zhongyuan Festival, also known as the Ghost Festival. Little K had never stayed up so late on such a day, because Little K was superstitious and afraid that after midnight, ghosts and monsters would appear. However, today, Little K had no choice.

Little K looked at the time: $23:54$. Seeing the $4$, Little K frowned. $4$ sounds like “death” in Chinese, which is especially unlucky. Seeing such a number on a day like this is often a bad omen.

Little K’s eyelids were fighting. He never did “toxic” problems. He simply lay down on the desk, and his eyes gradually became blurry.

“There is a notebook over there,” he thought. At some point, on the corner of his desk near the window, a soaked notebook lay quietly, as if it had just been rained on. “How did it get in?” Little K murmured. Subconsciously, he flipped it open and saw that some words were written inside. For some reason, those words looked so red on the yellowing paper.

The page on the left said:

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

The page on the right seemed longer than the left:

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

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

In the corner there was also a line of small text: Do not flip to the last page, or something terrifying will happen. But at this moment, Little K had already closed his eyes, and his snoring blended together with the distant thunder.

A breeze came, softly, and no one noticed. One corner of the notebook was lifted by the wind, slid through a graceful arc, and fell onto the other side of the notebook. The wind blew in gusts, brushing over the notebook’s yellowed pages. Gradually, there were fewer pages on the right and more pages on the left. The wind stopped, and the second-to-last page hung in midair. In an instant, it seemed that everything froze. Then, it gently fell on top of the other pages.

On the last page, in bright red crooked large letters, it read:

You have been procrastinating on this problem for a whole month! Finish it before tomorrow!

At this time, by observing the sky, you predicted Little K’s coming disaster. The time was already $23:59:59:400$. If it was not finished within these $1000-400=600$ milliseconds, Little K’s self-criticism (jiǎntǎo) would be unavoidable. As Little K’s good friend, can you help him solve this problem?

Problem 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