| 问题描述 |
|---|
有函数$$f(x)$$，当$$x=1$$时，$$f(x)=1$$。 当$$x>1$$时，$$f(x) = K- \sum_{y=1 ~\wedge~ y \mid x}^{x-1} f(y)$$ 给出$$L,\ R,\ K$$，令：$$ans = \sum_{i=L}^{R} f(i)$$ 请你输出$$ans \bmod (10^9+7)$$的结果。 |
| 输入描述 |
第一行是一个正整数 T 表示测试案例的数量。 每组案例包含三个整数 L，R，K。 |
| 输出描述 |
针对每组样例，在一行中输出答案。 |
| 样例输入复制样例 |
3 1 2 123 1 1000 123 1 123 123 |
| 样例输出 |
123 999999886 245 |
| 提示说明 |
对于 20% 的样例，1 ≤ L ≤ R ≤ 100，且 T 组样例的 K 值都相同。 对于 40% 的样例，1 ≤ L ≤ R ≤ 1000，且 T 组样例的 K 值都相同。 对于 60% 的样例，1 ≤ L ≤ R ≤ 20000，且 T 组样例的 K 值都相同。 对于 80% 的样例，1 ≤ L ≤ R ≤ 1e6，且 T 组样例的 K 值都相同。 对于 100% 的样例，1 ≤ L ≤ R ≤ 1e6，1 ≤ T ≤ 1000，1 ≤ k ≤ 1e9。 |
| 相关 |