CF822D My pretty girl Noora

在 Noora 就读的 Pavlopolis 大学里，决定举办一次“Pavlopolis 大学小姐”选美大赛。下面让我们更详细地描述一下选择全校最美丽女生的过程。 比赛分为若干轮进行。假设最初有 $n$ 名女生参赛。所有参赛者被分成若干个小组，每组有 $x$ 人。分组人数 $x$ 可以任意选择，也就是说每一轮 $x$ 的值都可以不同。在每个组内，评委会以“两两比较”的方式比较女生的美丽。这样，如果一个小组有 $x$ 名女生，则将会有 $\frac{x(x-1)}{2}$ 次比较。然后，从每个小组中选出最美丽的一位参加下一轮。这样，如果有 $n$ 名女生，每组 $x$ 人，则下一轮会有 $\lceil \frac{n}{x} \rceil$ 位女生参赛。比赛一直持续到只剩下一名女生，这名女生将成为“Pavlopolis 大学小姐”。 对于评委来说，这个比赛非常繁琐。他们希望每一轮都合理分组，让总的两两比较次数尽可能少。定义 $f(n)$ 表示对于初始有 $n$ 名女生，最终选出最美丽者所需的最小总比较次数。 组织者非常疯狂。他们给了 Noora 三个整数 $t$、$l$ 和 $r$，要求她计算如下表达式的值：$t^{0}·f(l)+t^{1}·f(l+1)+\cdots+t^{r-l}·f(r)$。由于表达式的结果可能很大，要求对 $10^{9}+7$ 取模。只要 Noora 能顺利计算出这个表达式，组织者就会帮助她在选美比赛中表现得更好。但 Noora 数学不好，所以她找到了 Leha，而 Leha 又找到了你。

输入一行，包含三个整数 $t$、$l$ 和 $r$，满足 $1 \leq t < 10^{9} + 7,\, 2 \leq l \leq r \leq 5 \cdot 10^{6}$。

输出一行，一个整数，表示表达式值对 $10^{9} + 7$ 取模后的结果。

考虑样例： 需要计算：$t^{0} \cdot f(2) + t^{1} \cdot f(3) + t^{2} \cdot f(4)$。 $f(2)=1$。两位女生只能组成一个包含 2 人的小组，只需一场比较。 $f(3)=3$。三位女生只能组成一个包含 3 人的小组，需要 3 场比较。 $f(4)=3$。可以分成两个小组，每组各有 2 位女生。第一轮每组比较一次，共 2 次，第二轮剩下两名女生，再比较一次，总共 $2+1=3$ 次。你也可以将所有女生分成一个 4 人小组，需 6 次比较，明显不如前一种分法。 因此表达式的值为 $t^{0} \cdot 1 + t^{1} \cdot 3 + t^{2} \cdot 3$。 由 ChatGPT 5 翻译