CF717A.Festival Organization

The Prodiggers are quite a cool band and for this reason, they have been the surprise guest at the ENTER festival for the past 80 years. At the beginning of their careers, they weren’t so successful, so they had to spend time digging channels to earn money; hence the name. Anyway, they like to tour a lot and have surprising amounts of energy to do extremely long tours. However, they hate spending two consecutive days without having a concert, so they would like to avoid it.

A tour is defined by a sequence of concerts and days-off. You need to count in how many ways The Prodiggers can select k different tours of the same length between l and r.

For example if k = 2, l = 1 and r = 2, if we define concert day as {1} and day-off as {0}, here are all possible tours: {0}, {1}, {00}, {01}, {10}, {11}. But tour 00 can not be selected because it has 2 days-off in a row. Now, we need to count in how many ways we can select k = 2 tours of the same length in range [1;2]. Here they are: {0,1}; {01,10}; {01,11}; {10,11}.

Since their schedule is quite busy, they want you to tell them in how many ways can do that, modulo 1 000 000 007 (109 + 7).

Prodiggers 是一支非常酷的乐队，因此在过去 80 年里，他们一直是 ENTER 音乐节的惊喜嘉宾。在职业生涯初期，他们并不太成功，不得不靠挖掘沟渠来赚钱谋生；乐队名称“Prodiggers”（意为“掘沟者”）便由此而来。无论如何，他们非常喜欢巡演，并且拥有惊人的精力来完成极长的巡演。然而，他们极其讨厌连续两天都不开演唱会，因此希望避免这种情况。

一场巡演被定义为一场由“演出日”和“休息日”组成的序列。你需要计算：Prodiggers 能够从长度在区间 $[l, r]$ 内的所有合法巡演中，选出 $k$ 个互不相同且长度相同的巡演，共有多少种选法。

例如，当 $k = 2$、$l = 1$、$r = 2$ 时，若用 $\{1\}$ 表示演出日、$\{0\}$ 表示休息日，则所有可能的序列有：$\{0\}, \{1\}, \{00\}, \{01\}, \{10\}, \{11\}$。但序列 $00$ 是非法的，因为它包含两个连续的休息日。现在我们需要统计：在长度属于区间 $[1, 2]$ 的所有合法巡演中，选出 $k = 2$ 个互不相同且长度相同的巡演，共有多少种方案。这些方案如下：$\{0,1\}$；$\{01,10\}$；$\{01,11\}$；$\{10,11\}$。

由于他们的日程安排十分紧张，他们希望你计算出该方案数对 $1\,000\,000\,007$（即 $10^9 + 7$）取模的结果。

The first line of the input contains three integers k, l and r (1 ≤ k ≤ 200, 1 ≤ l ≤ r ≤ 1018).

输入的第一行包含三个整数 $k$、$l$ 和 $r$（$1 ≤ k ≤ 200$，$1 ≤ l ≤ r ≤ 10^{18}$）。

Output a single number: the number of ways to select k different tours of the same length, modulo 1 000 000 007.

输出一个整数：选择 $k$ 个长度相同的互不相同游览路线的方案数，对 $1\,000\,000\,007$ 取模。