CF717A Festival Organization

Prodiggers 是一支非常酷的乐队，因此，在过去的 80 年里，他们一直是 ENTER 音乐节的神秘嘉宾。在职业生涯初期，他们并不成功，因此不得不挖沟赚钱，这也是他们名字的由来。不管怎样，他们非常喜欢巡演，并且有着惊人的精力能够完成极其漫长的巡演。然而，他们讨厌连续两天没有举办演唱会，所以他们希望能够避免这种情况。 一次巡演由一系列演唱会和休息日组成。你需要统计有多少种方式，Prodiggers 可以选择 $k$ 个长度相同且在 $l$ 到 $r$ 之间的不同巡演计划。 例如，若 $k=2$，$l=1$ 且 $r=2$，将演唱会日定义为 {1}，休息日定义为 {0}，所有可能的巡演计划为：{0}，{1}，{00}，{01}，{10}，{11}。但含有连续两个休息日的巡演（如 00）是不可选的。现在，需要统计有多少种方式，可以选择 $k=2$ 个相同长度（范围 $[1,2]$ 内）的巡演计划。具体为：{0,1}；{01,10}；{01,11}；{10,11}。 由于他们的日程非常繁忙，Prodiggers 希望你能帮他们计算有多少种方式可以做到这一点，答案对 $1000000007$（$10^9+7$）取模。

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

输出一个整数：在给定条件下，选择 $k$ 个不同巡演的方案数，对 $1000000007$ 取模。

由 ChatGPT 5 翻译