题目描述

$n$ 个女生，进行若干论选美。选美的方式如下：

• 设当前人数为 $m$，选择一个正整数 $x\ (m\ge x>1, x\ |\ m)$，划分为 $\frac{m}{x}$ 组，每组 $x$ 个人。

• 每一组中的女生两两比较，共进行 $\frac{x\times(x-1)}{2}$ 次比较。最终每一组只会有 $1$ 名女生晋级。

• 所有晋级的女生继续进行选美，直到只剩下一名女生。

设初始为 $n$ 名女生时最少的总比较次数为 $f(n)$，求 $\sum_{i=l}^r t^{i-l}\times f(i) \mod (10^9+7)$。

输入格式

一行三个整数 $t,l,r$，$1\le t<10^{9}+7,\ 2\le l\le r\le 5\times 10^{6}$。

输出格式

一个整数表示答案。

2 2 4

19