Let $n$ and $d$ be positive integers. We build the the divisor tree $T_{n,d}$ as follows:

• The root of the tree is a node marked with number $n$. This is the $0$-th layer of the tree.
• For each $i$ from $0$ to $d - 1$, for each vertex of the $i$-th layer, do the following. If the current vertex is marked with $x$, create its children and mark them with all possible distinct divisors$^\dagger$ of $x$. These children will be in the $(i+1)$-st layer.
• The vertices on the $d$-th layer are the leaves of the tree.

For example, $T_{6,2}$ (the divisor tree for $n = 6$ and $d = 2$) looks like this:

Define $f(n,d)$ as the number of leaves in $T_{n,d}$.

Given integers $n$, $k$, and $d$, please compute $\sum\limits_{i=1}^{n} f(i^k,d)$, modulo $10^9+7$.

$^\dagger$ In this problem, we say that an integer $y$ is a divisor of $x$ if $y \ge 1$ and there exists an integer $z$ such that $x = y \cdot z$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line of each test case contains three integers $n$, $k$, and $d$ ($1 \le n \le 10^9$, $1 \le k,d \le 10^5$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^9$.

Output

For each test case, output $\sum\limits_{i=1}^{n} f(i^k,d)$, modulo $10^9+7$.

Note

In the first test case, $n = 6$, $k = 1$, and $d = 1$. Thus, we need to find the total number of leaves in the divisor trees $T_{1,1}$, $T_{2,1}$, $T_{3,1}$, $T_{4,1}$, $T_{5,1}$, $T_{6,1}$.

• $T_{1,1}$ has only one leaf, which is marked with $1$.
• $T_{2,1}$ has two leaves, marked with $1$ and $2$.
• $T_{3,1}$ has two leaves, marked with $1$ and $3$.
• $T_{4,1}$ has three leaves, marked with $1$, $2$, and $4$.
• $T_{5,1}$ has two leaves, marked with $1$ and $5$.
• $T_{6,1}$ has four leaves, marked with $1$, $2$, $3$, and $6$.

The total number of leaves is $1 + 2 + 2 + 3 + 2 + 4 = 14$.

In the second test case, $n = 1$, $k = 3$, $d = 3$. Thus, we need to find the number of leaves in $T_{1,3}$, because $1^3 = 1$. This tree has only one leaf, so the answer is $1$.