Problem Background

Let me tell you a ghost story

One stormy night, Xiao K was working on an endless stream of information problems assigned by his teacher in his small study. It was stuffy with the doors and windows closed. Xiao K got up and opened the window in front of his desk just a crack, small enough that no raindrops could get through.

Today was the fifteenth day of the seventh lunar month, known as the Ghost Festival. Xiao K had never stayed up so late on such a day because he was superstitious and feared that ghosts and monsters would appear after midnight. Yet today, he had no choice.

Xiao K checked the time: $23:54$. Seeing the number $4$, he frowned. The number $4$ sounds like "death" and is particularly inauspicious. Seeing such a number on this day often portends bad luck.

Xiao K's eyelids were fighting. He had never done difficult problems. He decided to rest on his desk, his eyes gradually blurring.

"There's a notebook there," he thought. Somehow, a wet notebook had appeared on the corner of his desk near the window, as if it had just been rained on. "How did it get in?" Xiao K murmured. He instinctively opened the notebook and saw some writing inside. For some reason, the words on the yellowed pages looked red.

The left page read:

$$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 right page seemed longer:

$$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 was a small line: Do not turn to the last page, or something terrible will happen. But by this time, Xiao K had already closed his eyes, his snoring mixing with the distant thunder.

A gentle breeze came, unnoticed. The corner of the notebook was lifted by the wind, sliding over an elegant arc to the other side. The wind continued, flipping through the yellowed pages. Gradually, the right pages decreased, and the left pages increased. The wind stopped, and the second-to-last page of the notebook hung in the air. For a moment, everything seemed to freeze. Then, it gently fell on top of the other pages.

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

You've been dragging this problem for a month! Finish it by tomorrow!

At this moment, you predict Xiao K's misfortune by observing the night sky. The time is $23:59:59:400$, and if it is not completed within $1000-400=600$ milliseconds, Xiao K's inspection will be doomed. As Xiao 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$$

The answer should be modulo $10^9 + 7$.
Where $\{ a\}$ is the Fibonacci sequence.

Input and Output Format

Input Format

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

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

4 1 3

Sample Output #1

276

Sample Input #2

3 2 3

Sample Output #2

36

Notes

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

There are 20 data points, each worth 5 points, totaling 100 points. The properties of each data point are as follows:

(Note that the data ranges in the problem statement are just rough descriptions; please refer to the specific ranges above)

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

见题面 Input 部分

见题面 Output 部分