In the Far Away Kingdom there are coins with the value in 1 gold piece, k gold pieces, k² gold pieces, k³ 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.

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¹⁸; 2 ≤ k ≤ 10¹⁸; 1 ≤ l ≤ 100).

Output the number of sets modulo 10⁹ + 7.

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.