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)~

Cho hai số nguyên dương ~n~ và ~k~.

Ta có thể xây dựng một dãy số nguyên dương ~a~ gồm ~n~ phần tử: ~a_1,a_2,...,a_n~ sao cho với mọi ~1 \le i \le n~ thỏa mãn điều kiện ~a_i \in [1,k]~.

Gọi ~g(a)~ là ước chung lớn nhất của dãy số ~a~.

Nhiệm vụ của bạn chính là tính tổng ~g(a)~ của mọi dãy số có thể xây dựng (có ~k^n~ dãy số như vậy).

Vì kết quả có thể rất lớn, hãy in nó ra theo module ~10^9+7~.

Input: nhập vào từ file "SUMGCD.INP"

• Gồm một dòng chứa hai số nguyên dương ~n,k~ ~(1 \le n \le 10^9, 1 \le k \le 10^6)~.

Output: ghi ra file "SUMGCD.OUT"

• In ra kết quả theo module ~10^9+7~.

Subtask

• Subtask ~1~ ~(20\%)~: ~n,k \le 7~
• Subtask ~2~ ~(20\%)~: ~n \le 10^5, k = 4~
• Subtask ~3~ ~(25\%)~: ~n \le 10^5, k \le 20~
• Subtask ~4~ ~(20\%)~: ~k \le 10^5~
• Subtask ~5~ ~(15\%)~: Không giới hạn gì thêm.

Ví dụ

Sample Input 1

1  5

Sample Output 1

15

Sample Input 2

5 4

Sample Output 2

1060

Sample Input 3

3 2

Sample Output 3

9

Giải thích

Ở ví dụ ~3~ ta có:

• ~g([1,1,1]) = 1~
• ~g([1,1,2]) = 1~
• ~g([1,2,1]) = 1~
• ~g([1,2,2]) = 1~
• ~g([2,1,1]) = 1~
• ~g([2,1,2]) = 1~
• ~g([2,2,1]) = 1~
• ~g([2,2,2]) = 2~

Kết quả thu được là ~9~.

Ta có định nghĩa ~div(i)~ là số lượng ước số của số nguyên dương ~i~. Ví dụ ~div(3) = 2; div(6) = 4~.

Gọi ~S(n,m)~ là tập các số nguyên dương thỏa mãn ~div(i) = n~ và các thừa số nguyên tố của ~i~ đều bé hơn hoặc bằng số nguyên tố thứ ~m~. Ví dụ, ~S(2,3) = \{2,3,5\}~ vì số nguyên tố thứ ~3~ là ~5~.

Bạn hãy in ra số lượng phần tử trong tập ~S(n,m)~. Con số này có thể rất lớn nên hãy in ra theo modulo ~10^9+7~.

Input

• Dòng đầu chứa hai số nguyên dương ~t~ ~(1 \le 2 \times 10^5)~.
• ~t~ dòng sau, mỗi dòng gồm hai số nguyên dương ~n,m~ thể hiện truy vấn ~(1 \le n \le 2 \times 10^6, 1 \le m \le 10^9)~.

Output

• Với mỗi truy vấn, in ra kết quả.

Subtask:

• Subtask ~1~: ~t,n,m \le 10~ ~(30\%)~
• Subtask ~2~: ~t = 1, m \le 10^5~ ~(30\%)~
• Subtask ~3~: Không có ràng buộc gì thêm. ~(40\%)~

Sample Input 1

3
2 3
4 4
3 5

Sample Output 1

3
10
5

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~

Nhân dịp sinh nhật Alice được cha mẹ tặng ~n~ bộ xếp chữ, được đánh số từ ~1~ đến ~n~. Bộ xếp chữ thứ ~i~ có ~a_i~ chữ cái "A" và ~b_i~ chữ cái "B". Alice đưa ra một trò chơi như sau: chọn ra hai bộ xếp chữ trong ~n~ bộ, nhóm các chữ cái "A" và chữ cái "B" của hai bộ đã chọn, rồi xếp tất cả chúng thành một hàng ngang. Ví dụ là có ~3~ chữ cái "A" và ~4~ chữ cái "B" thì "ABABABB" và "BBBBAAA" là một trong các cách xếp hợp lệ, và "AAAABBB" là một trong các cách xếp không hợp lệ.

Alice muốn biết: có bao nhiêu cách chọn bộ và xếp chữ như vậy? Hai cách là khác nhau khi hai bộ xếp chữ được chọn ở hai cách là khác nhau, hoặc cách xếp nhận được là khác nhau.

Vì số cách chọn và xếp có thể rất lớn, bạn hãy in ra số cách tìm được chia lấy dư cho ~10^9+7~.

Input

Dòng đầu chứa số nguyên ~n~ (~2 \le n \le 2 \times 10^5~).

~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~, ~b_i~ (~1 \le a_i, b_i \le 2000~).

Output

In ra một số nguyên duy nhất là số cách chọn bộ và xếp chữ tìm được, modulo ~10^9+7~.

Scoring

• Subtask 1 (~20~ điểm): ~n \le 5~; ~a_i, b_i \le 10~.
• Subtask 2 (~20~ điểm): ~n \le 2000~.
• Subtask 3 (~30~ điểm): ~a_i, b_i \le 50~.
• Subtask 4 (~30~ điểm): Không có ràng buộc gì thêm.

Example

Input

2
1 1
2 1

Output

10

Xét đoạn mã sau:

int bubbleSort(int arr[], int n) {
  int cnt = 0;
  for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
              std::swap(arr[j], arr[j + 1]);
              cnt++;
          }
      }
  }
  return cnt;
}

Cho hai số nguyên dương ~n~ và ~k~, hãy đếm số bộ hoán vị độ dài ~n~ sao cho số phép thực hiện hàm swap trong code Bubble Sort trên đúng bằng ~k~.

Nói cách khác, gọi ~p(n)~ là hoán vị độ dài ~n~, hãy đếm các ~p(n)~ sao cho bubbleSort(p(n),n) = k.

Input

• Gồm một dòng chứa hai số nguyên ~n~ và ~k~. ~(n \le 10^5, k \le min(10^5, \frac{n\times (n-1)}{2})~

Output

• In ra một số nguyên là số hoán vị thỏa mãn, modulo ~10^9+7~.

Subtask

• ~30\%~ số test: ~n,k \leq 400~.

• ~30\%~ số test khác : ~n,k \le 4000~

• ~40\%~ số test còn lại : Không có ràng buộc gì thêm.

Example

Input 1

4 3

Output 1

6