In the Far Away Kingdom there are coins with the value in 1 gold piece, k gold pieces, k^{2} gold pieces, k^{3} gold pieces and so on.
Ivan the Fool took from Koshchei the Immortal a mortgage for a new cottage and now he pays for it every month exactly n gold pieces. How many different sets of l coins exist, so he could pay n gold pieces without change? The order of coins in the set does not matter.
Input
The first line contains an integer t that is the number of tests (1 ≤ t ≤ 100). Each of the following t lines contains integers n, k, l (1 ≤ n ≤ 10^{18}; 2 ≤ k ≤ 10^{18}; 1 ≤ l ≤ 100).
Output
Output the number of sets modulo 10^{9} + 7.
Sample
input  output 

3
12 3 4
7 2 5
7 2 2
 2
1
0

Notes
In the first sample, 12 gold pieces can be paid with four coins of value in 3 gold pieces or one coin of value in 9 gold pieces and three coins of value in 1 gold piece. In the second sample, 7 gold pieces can be paid only with three coins of value in 1 gold piece and two coins of value in 2 gold pieces. In the third sample, no suitable set exists, because to pay 7 gold pieces you need at least three coins.
Problem Author: Daniil Ayzenshteyn, prepared by Oleg Merkurev
Problem Source: "Later is better than never" Contest