T1

题目描述

\(Mr.Hu\) 最近偶得一函数：

\(f(n) = (\displaystyle\sum_{d \mid n} \varphi(d))^m (\sum_{d \mid n} \sigma_0(d) \mu(\frac nd) \frac nd)\)

其中 \(\sigma_0(n)\) 表示 \(n\) 的正约数个数，比如 \(\sigma_0(12) = 6\)，因为 \(12\) 有 \(1, 2, 3, 4, 6, 12\) 共 \(6\) 个正约数。

其中 \(\varphi(n)\) 是欧拉函数，\(\mu(n)\) 是莫比乌斯函数。

又有：\(F(n) = \displaystyle\sum_{i=1}^nf(i)\)。

\(Mr.Hu\) 希望你计算 \(F(n) \bmod 10^9 + 7\) 的值。

输入格式

第一行包含两个整数：\(n, m\)。

输出格式

输出一行包含一个数，表示答案。

输入样例

3 1

输出样例

1000000005

样例解释

\(f(1) = 1, f(2) = 0, f(3) = −3\)，故 \(F(3) = f(1) + f(2) + f(3) = −2\)，在模意义下，这个数为：\(1000000005\)。

数据规模

对于 \(20\%\) 数据，\(1 \leq n \leq 5000\)。

对于 \(50\%\) 数据，\(1 \leq n \leq 10^5\)。

对于 \(100\%\) 数据，\(1 \leq n \leq 10^7，1 \leq m \leq 10\)。

T2

题目描述

\(Mr.Hu\) 最近在研究等比数列，即形如：\(a, a^2, a^3, \dots, a^n, \dots\)

现在，\(Mr.Hu\) 想知道，对于给定的非负整数 \(a\)，上面这个无穷数列在摸 \(mod\) 意义下有多少项是本质不同
的。(保证 \(\gcd(a, mod) = 1\))。

输入格式

第 \(1\) 行一个整数：\(T\)，表示数据组数。

接下来 \(T\) 行，每行两个整数：\(a, mod\)。

输出格式

对于每组数据，输出一行，包含一个整数，表示模意义下本质不同的数有多少个。

输入样例

2
1 3
2 5

输出样例

1
4

样例解释

对于第一组数据，数列是：\(1, 1, 1, \dots, 1, \dots\)。

对于第二组数据，数列（取模以后）是：\(2, 4, 3, 1, 2, 4, 3, 1, \dots\)，总共有 \(4\) 个本质不同的数。

数据规模

对于 \(30\%\) 数据，\(0 \leq a \leq 10^3, 1 \leq mod \leq 10^3\)。

对于 \(100\%\) 数据，\(0 \leq a \leq 2 \times 10^9, 1 \leq mod \leq 2 \times 10^9\)，且保证 \(\gcd(a, mod) = 1, 1 \leq T \leq 100\)。

T3

题目描述

\(Mr.Hu\) 最近在学习组合数，他觉得这些数非常美丽。
于是，他写下了这样一个数：

\(\displaystyle\binom nl, \binom{n}{l + 1}, \binom{n}{l + 2}, \dots, \binom{n}{r - 1}, \binom nr\)

\(Mr.Hu\) 想知道，这些数里面，有多少个数是 \(5\) 的倍数。

输入格式

第 \(1\) 行一个整数：\(T\)，表示数据组数。

接下来 \(T\) 行，每行三个整数：\(l, r, n\)。

输出格式

对于每组数据，输出一行，包含一个整数，表示答案。

输入样例

2
1 3 4
1 4 5

输出样例

0
4

样例解释

对于第一组数据，数列是：\(4, 6, 4\)，没有 \(5\) 的倍数，故答案为 \(0\)。

对于第二组数据，数列是：\(5, 10, 10, 5\)，有 \(4\) 个数是 \(5\) 的倍数，故答案为 \(4\)。

数据规模

对于 \(20\%\) 的数据，\(1 \leq n \leq 5000\)。

对于 \(40\%\) 的数据，\(1 \leq n \leq 10^9, 1 \leq r − l + 1 \leq 5000\)。

对于 \(100\%\) 的数据，\(1 \leq n \leq 10^{18}，0 \leq l \leq r \leq n, 1 \leq T \leq 100\)。