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