CF2020F.Count Leaves

有正整数 $n$ 和 $d$。我们按如下规则建一棵 $T_{n,d}$ 的约数树：

• 树的根节点上的数为 $n$。这是树的第 $0$ 层。
• 对于第 $i$ 层（$i=0,1,...,d-1$）的每个结点，执行如下操作：若当前节点上的数为 $x$，则 $x$ 的所有可能的不同约数为其儿子节点上的数。这些儿子节点位于第 $i+1$ 层。
• 第 $d$ 层上的点为叶子节点。

例如，$T_{6,2}$（$n=6,d=2$ 的约数树）如下图所示：

定义 $f(n,d)$ 为 $T(n,d)$ 的叶子节点数。

给定 $n,k,d$ ，计算 $\sum\limits_{i=1}^nf(i^k,d)$ 模 $10^9+7$ 后的答案。

注：在这个问题中，我们说 $y$ 为 $x$ 的约数当且仅当 $y\geq1$ 且存在整数 $z$ 使得 $x=y\cdot z$。

每个测试有多组测试数据。第一行 $t\ (1\leq t\leq10^4)$ 为测试数据数。

每个测试数据包含一行三个数 $n,k,d\ (1\leq n\leq 10^9,1\leq k,d\leq 10^5)$。

保证所有测试数据中 $n$ 的和不超过 $10^9$。

对于每个测试数据，输出一行一个整数，表示 $\sum\limits_{i=1}^nf(i^k,d)\ mod\ 10^9+7$ 后的结果。

样例解释

在第一个测试样例中，$n=6,k=1,d=1$。因此，我们要算出 $T_{1,1},T_{2,1},T_{3,1},T_{4,1},T_{5,1},T_{6,1}$ 的叶子数的和。

• $T_{1,1}$ 只有一个叶子，该叶子上的数为 $1$。
• $T_{2,1}$ 有两个叶子，叶子上的数为 $1,2$。
• $T_{3,1}$ 有两个叶子，叶子上的数为 $1,3$。
• $T_{4,1}$ 有三个叶子，叶子上的数为 $1,2,4$。
• $T_{5,1}$ 有两个叶子，叶子上的数为 $1,5$。
• $T_{6,1}$ 有四个叶子，叶子上的数为 $1,2,3,6$。

叶子的总数为 $1+2+2+3+2+4=14$。

在第二个测试样例中，$n=1,k=3,d=3$，所以我们要求出 $T_{1^3,3}$ 的叶子数。因为 $1^3=1$，所以这棵树只有一片叶子，答案为 $1$。