Giải bài trực tuyến

Một cô gái xinh đẹp đột nhập vào cơ sở dữ liệu để ăn cắp thông tin cá nhân về các admin đẹp trai của C11, nhưng điều đó thật không dễ dàng vì cô phải vượt qua một mật mã đc mã hóa cực kì tinh vi bởi vị cao tăng Thích Thì Duyệt. Tất nhiên các admin và vị cao tăng biết cách để mở mật mã này. Vì những chàng trai trong mộng của mình, cô gái đã quyết định dùng sắc đẹp vốn có để mê hoặc vị cao tăng kia và cô đã thành công phần nào. Sau vài ba ngày giúp đại sư  “hoàn tục”, cô đã biết được mật mã kia được mã hóa bằng một dãy N số thỏa mãn 2 điều kiện :

• Các số thuộc dãy có giá trị nguyên từ 1 đến K
• Nếu lần lượt lấy các số trong dãy bỏ vào một stack theo thứ tự từ 1 đến N với điều kiện “khi M phần tử trên cùng của stack có giá trị giống nhau thì M phần tử đó sẽ biến mất trong stack” thì cuối cùng sẽ nhận được một stack rỗng.  

Và cô còn biết rằng mật mã để vào được cơ sở dữ liệu của C11 chính là số dãy N số thỏa mãn, nhưng vì số đó có thể rất lớn nên khi mã hóa đại sư đã lấy phần dư khi chia cho 10⁹+7. Dù đã biết đến vậy, nhưng cô vẫn không biết làm thế nào để tìm ra được mật mã chính xác, vì vậy cô đã tìm đến những coder tài năng và hứa hẹn sẽ đền đáp xứng đáng cho ai giúp cô giải được mật mã này.

Input

• Dòng đầu là số test (T <= 5)
• Sau đó là T dòng tương ứng với T bộ test, mỗi bộ test là 3 số N, K, M (1 <= N, K, M <= 1000) 

Output

• Gồm T dòng tương ứng với kết quả của T bộ test. Trên mỗi dòng là kết quả tìm được.

Example

Input:
2
6 2 2
4 4 2

Output:
20
28 

Chú ý : Có 20% test 1 <= N, M <= 10, K <= 4.