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

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

Cho số nguyên dương ~n~, hãy tính tổng sau:

• ~S = \lfloor \frac{n}{1} \rfloor + \lfloor \frac{n}{2} \rfloor + ... + \lfloor \frac{n}{n} \rfloor ~

Ở đây, ~\lfloor x \rfloor~ kí hiệu số nguyên dương lớn nhất nhất không vượt quá ~x~.

Input

• Dòng đầu chứa số nguyên dương ~T~ ~(1 \le T \le 30)~ là số lượng bộ test.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ ~(1 \le n \le 10^{12})~

Output

• Gồm ~T~ dòng, mỗi dòng in ra đáp án tương ứng sau khi lấy modulo cho ~10^6~.

Scoring

• 50% số test có ~n \le 10^6~
• 50% số test còn lại không có ràng buộc gì thêm

Sample Input 1

2
1
5

Sample Output 1

1
10

Đếm số cách chia ~n~ cái kẹo cho ~k~ người sao cho số kẹo của mỗi người nhận được đều thuộc đoạn ~[0,n]~. Hai cách chia kẹo được coi là khác nhau nếu tồn tại một người nhận được số kẹo khác nhau trong hai cách.

Nói cách khác, đếm số nghiệm nguyên của phương trình: ~x_1 + x_2 + ... + x_k = n~, sao cho ~\forall i \in [1,n]: 0 \le x_i \le n~.

Input

• Gồm hai số nguyên dương: ~n~ ~k~

Constraint

• ~1 \le k \le n \le 10^6~

Subtask

• Subtask ~1~ ~(30\%)~: ~1 \le n \le 10~.
• Subtask ~2~ ~(30\%)~: ~k \le n \le 1000~
• Subtask ~3~ ~(40\%)~: ~k \le n \le 10^6~

Output

• In ra kết quả bài toán sau khi chia lấy dư cho ~10^9+7~.

Sample Input 1:

6 3

Sample Output 1:

28

Trên hệ trục tọa độ OXY, hiện đang có ~n~ điểm được tô màu xanh, còn lại là các điểm màu đỏ.

Bạn cần thực hiện lần lượt ~q~ truy vấn, trong đó mỗi truy vấn thuộc một trong hai loại sau:

• ~1~ ~x~ ~y~ : Đổi màu của điểm ~(x,y)~. Tức là nếu trước đó nó là màu xanh thì sẽ đổi thành đỏ và ngược lại.
• ~2~ ~x~ ~y~ ~u~ ~v~: Bạn cần in ra số cách để đi từ điểm ~(x,y)~ tới điểm ~(u,v)~ mà chỉ đi qua các điểm màu xanh. Bạn chỉ có thể đi từ điểm ~(a,b)~ tới điểm ~(c,d)~ nếu nó đều có màu xanh và ~a < c~. Vì kết quả có thể rất lớn, bạn chỉ cần in nó ra theo module ~10^9 + 7~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ ~(1 \le n,q \le 2 \times 10^5)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~x_i~ và ~y_i~ miêu tả điểm ~(x_i,y_i)~ ban đầu có màu xanh. Dữ liệu đảm bảo rằng ~n~ điểm này phân biệt và ~-10^9 \le x_i, y_i \le 10^9~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ miêu tả truy vấn thứ ~i~ theo một trong hai loại:
  • ~1~ ~x_i~ ~y_i~ ~(-10^9 \le x_i, y_i \le 10^9)~.
  • ~2~ ~x_i~ ~y_i~ ~u_i~ ~v_i~ - dữ liệu đảm bảo rằng đây là các điểm đang có màu xanh. ~(-10^9 \le x_i, y_i,u_i,v_i \le 10^9)~

Subtask

• Subtask ~1~: ~n,q \le 100~ ~(20\%)~
• Subtask ~2~: ~n,q \le 2000~ ~(20\%)~
• Subtask ~3~: Các điểm có tọa độ trong khoảng ~[1,10^5]~ ~(20\%)~
• Subtask ~4~: ~n,q \le 5 \times 10^4~ ~(20\%)~
• Subtask ~5~: Không giới hạn gì thêm ~(20\%)~

Output

• Với mỗi truy vấn loại ~2~, in ra kết quả tương ứng.

Example

Sample Input 1

7 9
-1 -2
-2 -1
2 0
-1 1
0 3
3 3 
-3 4
1 -8 -9 
2 2 0 2 0
2 3 3 -1 -2
1 -8 -9
2 -1 -2 3 3
1 2 2
2 -2 -1 0 3
1 -2 -1
2 -3 4 3 3

Sample Output 1

1
0
4
3
18

Explanation

• Chỉ có duy nhất một đường đi từ ~(2,0)~ tới ~(2,0)~ là không di chuyển.
• Không thể đi từ ~(3,3)~ tới ~(-1,-2)~
• Có 4 đường đi từ ~(-1, -2)~ đến ~(3, 3)~:

1. ~(-1, -2) \rightarrow (3, 3)~
2. ~(-1, -2) \rightarrow (0, 3) \rightarrow (3, 3)~
3. ~(-1, -2) \rightarrow (2, 0) \rightarrow (3, 3)~
4. ~(-1, -2) \rightarrow (0, 3) \rightarrow (2, 0) \rightarrow (3, 3)~

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

Chắc hẳn các bạn đều đã quen thuộc với trò chơi bốc sỏi, khởi nguồn cho trò chơi tổng Nim nổi tiếng. Vậy nên chúng ta sẽ đi tìm hiểu một biến thể khác của trò chơi này:

Multi Nim là một trò chơi hai người với ~n~ chồng đống sỏi, trong đó đống thứ ~i~ có ~a_i~ viên sỏi. Trong mỗi lượt, người chơi hiện tại có thể loại bỏ một số viên sỏi từ nhiều đống, với điều kiện là họ phải loại bỏ ít nhất một viên sỏi. Hai người chơi lần lượt chơi xen kẽ, và người thứ nhất là người chơi đầu tiên. Trò chơi kết thúc khi tất cả các đống sỏi đều trống.

Biến thể này có vẻ hơi nhàm chán, vậy nên thay vì chơi, công việc của bạn là đếm xem có bao ván chơi kết thúc ở đúng ~k~ lượt. Vì kết quả có thể rất lớn, hãy in ra theo module ~10^9+7~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ miêu tả số đống sỏi và số lượng lượt chơi ~(1 \le n,k \le 5000)~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~ - số lượng sỏi ở từng đống ~(a_i \le 10^5)~.

Subtask

• Subtask ~1~: ~n = 2, 1 \le k \le 500, a_i \le 500~ ~(20\%)~
• Subtask ~2~: ~n = 2, k \le 5000~ ~(20\%)~
• Subtask ~4~: ~n \le 500, k \le 500~ ~(30\%)~
• Subtask ~5~: Không giới hạn gì thêm ~(30\%)~

Output

• In ra số cách chơi kết thúc sau đúng ~k~ lượt.

Example

Sample Input 1

2 2
1 3

Sample Output 1

6

Sample Input 1

2 8
16 27

Sample Output 1

211991876

Explanation

Ở ví dụ ~1~ có các cách như sau:

• ~[0,1]~ ~[1,2]~
• ~[0,2]~ ~[1,1]~
• ~[0,3]~ ~[1,0]~
• ~[1,0]~ ~[0,3]~
• ~[1,1]~ ~[0,2]~
• ~[1,2]~ ~[0,1]~

Cho ~T~ bộ dữ liệu. Mỗi bộ dữ liệu gồm năm số nguyên dương ~a, b, c, d, k~.

Với mỗi bộ dữ liệu, hãy tính tổng ~i \times j~ của tất cả các cặp số ~(i, j)~ thỏa mãn:

• ~a \le i \le b~
• ~c \le j \le d~
• ~GCD(i, j) = k~

Nói cách khác, cần tính:

~\displaystyle\sum_{i=a}^{b}\sum_{j=c}^{d} i \times j \times [GCD(i, j) = k]~

Vì kết quả có thể rất lớn, hãy in ra kết quả sau khi chia lấy dư cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ ~(1 \le T \le 10^5)~, là số bộ dữ liệu.
• ~T~ dòng tiếp theo, mỗi dòng chứa năm số nguyên ~a, b, c, d, k~ ~(1 \le a \le b \le 10^5, 1 \le c \le d \le 10^5, 1 \le k \le 10^5)~.

Output

• In ra ~T~ dòng, dòng thứ ~i~ là đáp án của bộ dữ liệu thứ ~i~.

Subtask

Sample Input

2
1 5 1 5 1
1 5 1 5 2

Sample Output

155
20

Giải thích ví dụ

Với bộ dữ liệu thứ nhất, ta cần tính tổng ~i \times j~ với ~1 \le i, j \le 5~ và ~GCD(i, j) = 1~. Kết quả là ~155~.

Với bộ dữ liệu thứ hai, ta cần tính tổng ~i \times j~ với ~1 \le i, j \le 5~ và ~GCD(i, j) = 2~. Các cặp thỏa mãn là ~(2, 2)~, ~(2, 4)~, ~(4, 2)~, nên tổng là:

~2 \times 2 + 2 \times 4 + 4 \times 2 = 20~