{"code":"caykphan","name":"Đếm trên cây k phân có trọng số","description":"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:\r\n\r\n- Mỗi đỉnh có chính xác $k$ đỉnh con\r\n\r\n- Mỗi cạnh đều có trọng số \r\n\r\n- 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$\r\n\r\n![Imgur](https://i.imgur.com/CzTEWeL.png) \r\n\r\n(Hình ảnh minh hoạ cây $3-$phân có trọng số)\r\n\r\n**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$.\r\n\r\n

Input

\r\n\r\n- Dòng thứ nhất chứa số $t(1\\le t\\le 100)$ - Thể hiện số testcase \r\n\r\n- $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)$\r\n\r\n

Output

\r\n\r\n- Ứ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.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 2\r\n 3 4 2\r\n 2 2 2\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 3\r\n 1\r\n ```","points":380.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}