Cho ~t~ truy vấn và giá trị ~mod~ ~(1 \le mod \le 2*10^9)~, mỗi truy vấn gồm hai số nguyên dương ~n~, ~k~. Kí hiệu ~C(k,n)~ là tổ hợp chập ~k~ của ~n~, hãy in ra ~C(k,n)~ cho mỗi truy vấn tương ứng. Do kết quả có thể rất lớn nên hãy in nó sau khi lấy phần dư cho ~mod~.

Subtask

• Sub ~1~: ~t \le 10^5~, ~1 \le k \le n \le 2000~. (30%)
• Sub ~2~: ~t = 1~, ~1 \le k \le n \le 10^5~. (30%)
• Sub ~3~: ~t \le 10^5~, ~1 \le k \le n \le 10^5~, ~mod = 10^9+7~. (40%)

Input

• Dòng đầu tiên gồm một số nguyên dương ~sub~ miêu tả subtask mà test này tương ứng. (~1 \le sub \le 3~)
• Dòng thứ hai gồm hai số nguyên dương ~t~ và ~mod~.
• ~t~ dòng sau, mỗi dòng gồm hai số nguyên dương ~n~, ~k~ (~k \le n~) miêu tả truy vấn tương ứng.

Output

• In ra ~t~ dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Sample Test

Input:

1
3 2345
6 4
8 4
15 8

Output:

15
70
1745

Cho ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~, hãy tìm số nguyên dương ~x~ nhỏ nhất thỏa mãn: ~\text{gcd}(a_i, x) > 1~ với mọi ~1 \le i \le n~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 50~).

• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~2 \le a_i \le 50~).

Output

• Một dòng duy nhất chứa đáp án của bài toán.

Sample Input 1

2
3 10

Sample Output 1

6

Sample Input 2

3
6 10 12

Sample Output 2

2

Pikachu đang ở ô ~(0,0)~ và cậu ấy muốn đi đến ô ~(n, m)~. Biết rằng khi đang ở ô ~(x,y)~, Pikachu chỉ có thể đi đến ô ~(x + 1, y)~ hoặc ~(x, y + 1)~. Hãy đếm số cách mà Pikachu có thể đi, vì kết quả có thể rất lớn nên hãy in ra theo module ~10^9+7~.

Input

• Dòng một chứa hai số nguyên dương ~t \; (t \leq 1000)~ và ~s~ lần lượt là số bộ dữ liệu của test và subtask của test.
• ~t~ dòng sau, mỗi dòng chứa ~2~ số nguyên dương ~n~ và ~m~ tương ứng với ~1~ bộ dữ liệu.

Output

• Gồm ~t~ dòng, mỗi dòng chứa kết quả của một test theo thứ tự đầu vào.

Subtask

• Sub ~1~: ~n, m \leq 1000~.
• Sub ~2~: ~n, m \leq 10^6~.

Sample Input 1:

3 1
2 2
4 7
5 6

Sample Output 1:

6
330
462

Bài này giống bài trước nhưng Pikachu có thẻ đi chéo

Pikachu đang ở ô ~(0,0)~ và cậu ấy muốn đi đến ô ~(n, m)~. Biết rằng khi đang ở ô ~(x,y)~, Pikachu chỉ có thể đi đến ô ~(x + 1, y)~, ~(x, y + 1)~ hoặc ~(x + 1, y + 1)~. Hãy đếm số cách mà Pikachu có thể đi, vì kết quả có thể rất lớn nên hãy in ra theo module ~10^9+7~.

Input

• Gồm một dòng duy nhất chứa ~2~ số nguyên dương ~n~ và ~m~.

Output

• Gồm một dòng chứa kết quả bài toán.

Subtask

• Sub ~1~: ~n, m \leq 1000~.
• Sub ~2~: ~n, m \leq 10^6~.

Sample Input 1:

4 3

Sample Output 1:

129

Năm ~404~ BC, vùng đất Westeros đang xôn xao vì một bài toán rất lạ được đưa ra từ một kẻ ẩn danh tới từ Essos. Khắp bảy phụ quốc, các lãnh chúa liên tục tìm người để giải quyết bài toán nhưng đều thất bại. Bài toán được lan truyền tới Oldtown và khiến các Maester ở Citadel cũng phải đau đầu. Hãy giúp các học sĩ giải quyết bài toán này nhé:

Số đẹp được định nghĩa là một số nguyên dương và chia hết cho một trong ba số: ~3~, ~5~, hoặc ~7~.

Ví dụ về dãy các số đẹp: ~3, 5, 6, 7, 9, 10, 12, 14, 15, 18,...~

Hãy tìm số đẹp thứ ~k~.

Input

• Gồm một dòng chứa số nguyên dương ~k~.

Output

• In ra kết quả của bài toán.

Sample Test

Input 1

2

Output 1

5

Input 2

10

Output 2

18

Giới hạn:

• Subtask 1 (50% số điểm): ~k \le 10^6~
• Subtask 2 (50% số điểm): ~k \le 10^9~

Bản đồ của ~1~ khu rừng được chia thành các ô vuông bằng nhau và biểu diễn dưới dạng mặt phẳng ~Oxy~ (mỗi ô ứng với ~1~ điểm có tọa độ nguyên). Một đám cháy rừng sẽ diễn ra như sau :

• Ban đầu chỉ có ~1~ ô bị cháy.
• Sau ~1~ đơn vị thời gian, đám cháy sẽ lan sang các ô có chung đỉnh hoặc chung cạnh với các ô đang cháy.

Cho ~2~ điểm ~A(0, a)~ và ~B(b, 0)~ trên mặt phẳng, bạn cần phải đi từ ~A~ đến ~B~ sao cho mỗi bước chỉ được đi xuống hoặc sang phải. Ngoài ra bạn cần trả lời các truy vấn sau:

• Mỗi truy vấn cho ~1~ cặp số ~x, t~. Hỏi nếu có ~1~ đám cháy ở ô ~(x, x)~ và đã kéo dài ~t~ đơn vị thời gian thì có bao nhiêu cách đi từ ~A~ tới ~B~ mà không đi qua các ô bị cháy ?

Ví dụ khi có điểm ~A(0, 4)~ và ~B(4, 0)~:

Input

• Gồm ~2~ dòng chứa ~2~ số nguyên ~a~ , ~b~ (thể hiện tọa độ điểm ~A~ và ~B~ như đề bài) và số nguyên ~Q~ là số lượng truy vấn. ~(1 \le a, b \le 10^{6})~ ~(1 \le q \le 3 \times 10^{5})~
• ~Q~ dòng tiếp theo , mỗi dòng chứa ~2~ số nguyên ~x~ , ~t~ là câu hỏi cho mỗi truy vấn. ~(0 \le |x|, t \le 10^{9})~

Output

• In ra ~Q~ dòng, mỗi dòng là phần dư của kết quả truy vấn đó sau khi chia cho ~10^9+7~.

Sample Input

4 4 2
2 1
2 0

Sample Output

2 
34

Subtask

• ~20\%~ số test có ~a \times b \le 1000000~ , ~q = 1~
• ~20\%~ số test tiếp theo có ~q = 1~ và ~x \le 0~
• ~60\%~ số test còn lại không có điều kiện gì thêm