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