Cây \(k\) phân có trọng số là một cây vô hạn có gốc và chúng thoả mãn những tính chất sau:

• Mỗi đỉnh có chính xác \(k\) đỉnh con

• Mỗi cạnh đều có trọng số

• Nếu chúng ta xem xét các cạnh từ đỉnh nào đó đến con của nó (chính xác là \(k\) cạnh), thì trọng số của chúng sẽ bằng \(1, 2, 3, ..., k\)

(Hình ảnh minh hoạ cây \(3-\)phân có trọng số)

Yêu cầu: Hỏi có bao nhiêu đường đi xuất phát từ gốc có tổng trọng số là \(n\) và những đường đi này phải chứa ít nhất một cạnh mà trọng số của nó không nhỏ hơn \(d\).

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên \(n,k,d (1\le n,k\le 100; 1\le d\le k)\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm, vì đáp số có thể rất lớn, nên cần lấy mod \(10^9+7\) trước khi in ra.

Example

2
3 4 2
2 2 2

3
1