Пусть $$$n$$$ и $$$d$$$ — положительные целые числа. Построим дерево делителей $$$T_{n,d}$$$ следующим образом:
- Корень дерева — вершина, в которой записано число $$$n$$$. Она образует $$$0$$$-й уровень дерева.
- Для каждого $$$i$$$ от $$$0$$$ до $$$d - 1$$$, для каждой вершины на $$$i$$$-м уровне, сделаем следующее. Если в текущей вершине записано число $$$x$$$, то нужно создать её детей и записать в них все возможные различные делители$$$^\dagger$$$ числа $$$x$$$. Эти дети будут находиться уже на $$$(i+1)$$$-м уровне.
- Вершины на $$$d$$$-м уровне являются листьями дерева.
Например, дерево $$$T_{6,2}$$$ (дерево делителей для $$$n = 6$$$ и $$$d = 2$$$) выглядит так:
Через $$$f(n,d)$$$ обозначим число листьев в $$$T_{n,d}$$$.
По заданным $$$n$$$, $$$k$$$ и $$$d$$$, найдите $$$\sum\limits_{i=1}^{n} f(i^k,d)$$$, по модулю $$$10^9+7$$$.
$$$^\dagger$$$ В этой задаче мы считаем, что целое число $$$y$$$ является делителем числа $$$x$$$, если $$$y \ge 1$$$ и существует целое $$$z$$$, такое что $$$x = y \cdot z$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.
Для каждого набора входных данных выведите $$$\sum\limits_{i=1}^{n} f(i^k,d)$$$, по модулю $$$10^9+7$$$.
36 1 11 3 310 1 2
14 1 53
В первом наборе входных данных $$$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}$$$, поскольку $$$1^3 = 1$$$. В этом дереве всего один лист, так что ответ равен $$$1$$$.
