← 返回题目列表

Codeforces · 717/A

A. 节日组织

中文机器翻译题面 查看原题

Prodiggers 是一支非常酷的乐队,因此,他们在过去 80 年里一直是 ENTER 音乐节上的惊喜嘉宾。事业之初,他们并没有那么成功,所以不得不花时间挖掘渠道来赚钱;因此得名。不管怎样,他们非常喜欢旅行,并且有惊人的精力来进行超长的旅行。然而,他们讨厌连续两天没有音乐会,所以他们想避免这种情况。

巡演是由一系列音乐会和休息日定义的。您需要计算 Prodiggers 有多少种方式可以在 l 和 r 之间选择 k 个相同长度的不同旅行。

例如,如果 k = 2、l = 1 且 r = 2,如果我们将音乐会日定义为 {1},将休息日定义为 {0},则以下是所有可能的巡演:{0}、{1}、{00}、{01}、{10}、{11}。但00号巡演不能选择,因为它连续有2天休息。现在,我们需要计算有多少种方式可以在 [1;2] 范围内选择 k = 2 个相同长度的旅行。它们是:{0,1}; {01,10}; {01,11}; {10,11}。

由于他们的日程安排非常繁忙,他们希望您告诉他们有多少种方法可以做到这一点,模 1 000 000 007 (109 + 7)。

输入

输入的第一行包含三个整数 k、l 和 r (1 ≤ k ≤ 200, 1 ≤ l ≤ r ≤ 1018)。

输出

输出单个数字:选择 k 个相同长度的不同游览的方式数,以 1 000 000 007 为模。

示例

输入 #1

1 1 2

输出 #1

5