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. Huy vào cửa hàng và muốn mua \(k\) cái kẹo. Hỏi Huy có bao nhiêu cách chọn để mua được \(k\) cái kẹo.

Input

• Dòng đầu ghi số nguyên \(t(1 \le t \le 200)\) cho biết số lượng testcase
• \(2 \times 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\)
  • Dòng thứ hai ghi số nguyên \(k\)

Output

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

Điều kiện

• \(1 \le n,k \le 10^{3}\)

Sample Input 1

2
4
1
2
3

Sample Output 1

4
4