In the Far Away Kingdom there are coins with the value in 1 gold piece, k gold pieces, k2 gold pieces, k3 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 ≤ 1018; 2 ≤ k ≤ 1018; 1 ≤ l ≤ 100).
Output the number of sets modulo 109 + 7.
12 3 4
7 2 5
7 2 2
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