Cho ~m~ cái kẹo cần chia cho ~n~ đứa trẻ .

Yêu cầu:

Đếm số cách chia kẹo cho ~n~ đứa trẻ sao cho mỗi đứa có ít nhất là ~k~ cái kẹo .

Kết quả lấy phần dư khia chia cho 100003 .

INPUT:

Dòng đầu: Gồm số nguyên dương số test : ~T~ ( ~T~ < 10000) .

~T~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~m , n , k~ (~m , n , k < 10^{16}~ ).

OUTPUT:

Kết quả bài toán .

Ví dụ

input

1
3 2 1

output

2