Panda và Phản ứng dây chuyền

Trong một buổi tập võ, FullHouse Dev được sư phụ giao cho một bài toán thú vị về phản ứng dây chuyền. Với tinh thần võ đạo nghiêm túc, họ quyết tâm giải quyết bài toán này để nâng cao trình độ võ học của mình.

Bài toán

FullHouse Dev được cho biết về một dãy phòng thí nghiệm vô hạn, trong đó phòng số \(K\) được kết nối với phòng số \(K-1\). Các phòng được đánh số bắt đầu từ 0. Ban đầu, có \(X\) hạt trong phòng số 0. Số hạt trong phòng \(K\) bằng \(K\) lần số hạt trong phòng \(K-1\). Nhiệm vụ của nhóm là tìm ra số hạt trong phòng thứ \(N\).

Lưu ý: Số hạt trong phòng \(K\) chỉ có thể được tính sau khi biết số hạt trong phòng \(K-1\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Mỗi test case gồm hai số nguyên \(N\) và \(X\) cách nhau bởi dấu cách.

OUTPUT FORMAT:

• Với mỗi test case, in ra số hạt trong phòng thứ \(N\). Do kết quả có thể rất lớn, hãy in ra phần dư khi chia cho \(10^6+3\).

Ràng buộc:

• \(1 \leq T \leq 10^5\)

Subtask 1: (20 điểm)

• \(1 \leq N, X \leq 10^5\)

Subtask 2: (80 điểm)

• \(1 \leq N, X \leq 10^{18}\)

Ví dụ

INPUT

2
1 3
2 1

OUTPUT

3
2

Giải thích

• Test case 1: Ban đầu có 3 hạt. Trong phòng \(K=1\), số hạt trở thành \(1*3 = 3\).
• Test case 2: Ban đầu có 1 hạt. Trong phòng \(K=1\), số hạt trở thành \(1*1 = 1\). Trong phòng \(K=2\), số hạt trở thành \(2*1 = 2\).