ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Later is better than never

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Mortgage in Far Away Kingdom

Time limit: 3.0 second
Memory limit: 128 MB
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.

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

Output

Output the number of sets modulo 109 + 7.

Sample

inputoutput
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
To submit the solution for this problem go to the Problem set: 2129. Mortgage in Far Away Kingdom