ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

## 2129. 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.

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