F. 统计叶子节点

时间限制：4 秒 内存限制：256 兆字节

给定正整数 $n$ 和 $d$。我们按照如下规则构造除数树 $T_{n,d}$：

• 树的根节点标记为数字 $n$，位于第 $0$ 层。
• 对于每个 $i$（从 $0$ 到 $d-1$），对第 $i$ 层的每个节点执行以下操作：若当前节点标记为 $x$，则为它创建所有不同的正除数 $y$ 作为子节点，这些子节点位于第 $i+1$ 层。
• 第 $d$ 层的所有节点就是这棵树的叶子节点。

例如，$T_{6,2}$（$n=6,\;d=2$ 的除数树）结构如下：

根为 6 → 第 1 层是 6 的所有除数 → 第 2 层是每个节点的所有除数，即为叶子

定义 $f(n,d)$ 为除数树 $T_{n,d}$ 的叶子节点数量。

给定整数 $n, k, d$，请计算：

答案对 $10^9+7$ 取模。

† 在本题中，若 $y \ge 1$ 且存在整数 $z$ 使得 $x = y \cdot z$，则称 $y$ 是 $x$ 的除数。

输入格式

每个测试文件包含多组测试用例。 第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。

每组测试用例仅一行，包含三个整数 $n, k, d$：

• $1 \le n \le 10^9$
• $1 \le k,d \le 10^5$

数据保证：所有测试用例的 $n$ 之和不超过 $10^9$。

输出格式

对于每组测试用例，输出上述求和式的结果，对 $10^9+7$ 取模。

样例输入

3
6 1 1
1 3 3
10 1 2

样例输出

14
1
53

样例解释

• 第一个测试用例：$n=6,\;k=1,\;d=1$ 需要计算 $T_{1,1},T_{2,1},\dots,T_{6,1}$ 的叶子总数。

  • $T_{1,1}$：$1$ 片叶子
  • $T_{2,1}$：$2$ 片叶子
  • $T_{3,1}$：$2$ 片叶子
  • $T_{4,1}$：$3$ 片叶子
  • $T_{5,1}$：$2$ 片叶子
  • $T_{6,1}$：$4$ 片叶子 总和：$1+2+2+3+2+4=14$。

• 第二个测试用例：$n=1,\;k=3,\;d=3$ 仅需计算 $T_{1^3=1,3}$，叶子数量为 $1$。

• 第三个测试用例：$n=10,\;k=1,\;d=2$ 求和结果为 $53$。