vrajitoare

A mischievous child was walking through the park when suddenly a bear appeared in his path. Fortunately, a very old witch appeared and saved the child from the bear's claws. However, the witch's help is not unconditional. To repay her, the witch brought her dwarfs and told the child:

"Look closely at the dwarfs. Each of them has three numbers written on their forehead. Let's denote the numbers on dwarf $i$ with $v_i$, $b_i$, and $x_i$. We consider the number $m_i$, which is equal to the number of gadfadarian numbers from $0$ to $v_i$. You might wonder what a gadfadarian number is. Well, it is a number that has $x_i$ ones in its representation in base $b_i$. I want to know $m_i$. However, I will be generous today and only ask for the result modulo $10^9 + 7$."

Help the witch find the answer to the question!

Input data

The first line contains a natural number $n$, representing the number of dwarfs.

The next $n$ lines contain the numbers on the dwarfs' foreheads, with $v_i$ representing the number written on the forehead of dwarf $i$, $b_i$ representing the base referred to by the witch, and $x_i$ representing the number of ones in the base $b_i$ representation that we need. The number is given in base $b_i$.

Output data

For each dwarf, output the required answer on a separate line, representing the value of $m_i$ modulo $10^9 + 7$.

Constraints and clarifications

• $1 \leq n \leq 100$
• $v_i$ has at most $10^5$ digits in base $b_i$
• $2 \leq b_i \leq 10$
• $0 \leq x_i \leq |v_i|$

Example 1

stdin

6
99 10 1
1110100011 2 3
1110100011 2 2
12103 5 2
681 9 0
999 10 2

stdout

18
120
45
219
377
27

Explanation

For the first example, valid numbers are $1$, numbers from $10$ to $19$ except $11$, and numbers $21$, $31$, $\dots$, $91$.