Một cửa hàng có ~ n ~ loại kẹo khác nhau, các loại kẹo đều có rất nhiều kẹo và giá mỗi cái kẹo như nhau. Tom vào cửa hàng và muốn mua ~ k ~ cái kẹo. Hỏi Tom có bao nhiêu cách chọn để mua được ~ k ~ cái kẹo.

Dữ liệu vào

• Dòng đầu ghi số nguyên ~ t ~ ~ (1 ≤ t ≤ 200) ~ cho biết số lượng testcase
• ~ 2×t ~ dòng tiếp theo, mỗi hai dòng lần lượt cho biết thông tin về một testcase
  • Dòng đầu ghi số nguyên ~ n ~ ~ (1≤n≤1000) ~
  • Dòng thứ hai ghi số nguyên ~ k ~ ~ (1 ≤ k ≤ 1000) ~

Kết quả

• Với mỗi testcase in ra số cách Tom có thể mua được ~ k ~ cái kẹo. Kết quả được chia lấy dư cho ~ 10^9 ~

Ví dụ:

Input 1

2
4
1
2
3 

Output 1

4
4