Пусть \(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\).
Выходные данные
Для каждого набора входных данных выведите \(\sum\limits_{i=1}^{n} f(i^k,d)\), по модулю \(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}\), поскольку \(1^3 = 1\). В этом дереве всего один лист, так что ответ равен \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 1 1
1 3 3
10 1 2
|
14
1
53
|