← 返回题目列表

Codeforces · 822/D

D. 我的漂亮女孩诺拉

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

Noora就读的巴甫洛波利斯大学决定举办选美比赛“帕夫洛波利斯大学小姐”。让我们更详细地描述一下选择大学最美丽女孩的过程。

比赛分几个阶段进行。假设最初有 n 个女孩参加比赛。所有参与者被分成相等的组,每组有x个参与者。此外,数字 x 是任意选择的,i。 e.每个阶段的数字 x 可以不同。在每个组中,比赛的评委会以“逐个”的形式对女孩们的美貌进行比较。这样,如果组由 x 个女孩组成,则发生 $$\frac{x \cdot (x-1)}{2}$$ 比较。然后,从每组中选出最美丽的参与者。被选中的女孩进入下一阶段的比赛。因此,如果将 n 个女孩分成几组,每组有 x 个参与者,那么恰好 $$\frac{\pi}{\tau}$$ 参与者将进入下一阶段。比赛将继续进行,直到只剩下一名女孩将成为“帕夫洛波利斯大学小姐”

但对于评审团来说,这场比赛是一项非常繁琐的任务。他们希望在每个阶段将女孩们分组,以便女孩们成对比较的总数尽可能少。如果我们在第一阶段录取 n 个女孩,则令 f(n) 为选择最美丽参与者所需进行的最小比较次数。

比赛组织者疯了。他们给了 Noora 三个整数 t、l 和 r,并要求这个可怜的女孩计算以下表达式的值:t0·f(l) + t1·f(l + 1) + ... + tr - l·f(r)。然而,由于这个表达式的值可能相当大,组织者要求她以 109 + 7 为模来计算。如果 Noora 能计算出这个表达式的值,组织者承诺她在选美比赛期间提供帮助。但这个可怜的女孩数学并不强,所以她向莱哈寻求帮助,而他则向你求助。

输入

第一行包含三个整数 t、l 和 r (1 ≤ t < 109 + 7, 2 ≤ l ≤ r ≤ 5·106)。

输出

在第一行中打印单个整数 — 表达式模 109 + 7 的值。

示例

输入 #1

2 2 4

输出 #1

19

注意

考虑示例。

需要找到 $$( 2 ^ { 0 } \cdot f ( 2 ) + 2 ^ { 1 } \cdot f ( 3 ) + 2 ^ { 2 } \cdot f ( 4 ) ) \bmod ( 1 0 ^ { 9 } + 7 )$$ 的值。

f(2) = 1。两个女孩只能组成一组,每组两人,其中会有一次比较。

f(3) = 3。三个女孩只能组成一组,每组三个人,其中将进行 3 次比较。

f(4) = 3。您可以从四个女孩中组成两组,每组两个女孩。然后第一阶段会有两次比较,两组各一次。第二阶段会有两个女孩,她们之间会有一场比较。总计 2 + 1 = 3 次比较。您也可以在第一阶段将所有女孩留在同一组。然后就会发生 $$\frac{4 \cdot 3}{2} = 6$$ 比较。显然,还是采用第一种方式将女生分组比较好。

那么表达式的值为 $$( 2 ^ { 0 } \cdot 1 + 2 ^ { 1 } \cdot 3 + 2 ^ { 2 } \cdot 3 ) \mod ( 1 0 ^ { 9 } + 7 ) = 1 9$$。