Phản ứng dây chuyền

Trong một buổi thực tập tại ngân hàng, FullHouse Dev được giao một bài toán thú vị về chuỗi phản ứng trong hệ thống giao dịch. Họ cần tính toán số lượng giao dịch tại mỗi nút mạng dựa trên một quy luật đặc biệt.

Bài toán

Có vô số phòng được đánh số từ 0, trong đó phòng số \(K\) được kết nối với phòng số \(K-1\). Ban đầu, có \(X\) phần tử ở phòng số 0. Số phần tử trong phòng \(K\) bằng \(K\) lần số phần tử trong phòng \(K-1\). FullHouse Dev cần tìm số phần tử trong phòng thứ \(N\).

Lưu ý: Không thể tính số phần tử trong phòng \(K\) nếu chưa tính được số phần 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ố phần 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 phần tử. Ở phòng \(K=1\), số phần tử là \(1*3 = 3\).
• Test case 2: Ban đầu có 1 phần tử. Ở phòng \(K=1\), số phần tử là \(1*1 = 1\). Ở phòng \(K=2\), số phần tử là \(2*1 = 2\).