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 ~t~ truy vấn, mỗi truy vấn là một số nguyên dương ~n~, hãy in ra tổng các ước của số ~n~.

Input

• Dòng đầu tiên gồm một số nguyên dương miêu tả số ~t~ ~(1 \le t \le 3*10^5)~

• ~t~ dòng sau, mỗi dòng gồm một số nguyên dương ~n~ ~(1 \le n \le 10^7)~ miêu tả truy vấn tương ứng.

  Output

• Với mỗi truy vấn, in ra kết quả tương ứng theo từng dòng.

Sample Test

Input:

4
10
8
15
16

Output:

18
15
24
31

Cho một số nguyên dương ~n~, hãy phân tích số ~n~ thành tổng của một số số nguyên dương sao cho bội chung nhỏ nhất của chúng là lớn nhất có thể.

Input

• Gồm một số nguyên dương ~n~, ~(1 \le n \le 340)~

Output

• In ra bội chung nhỏ nhất tìm được.

Sample Test

Input:

10

Output:

30

Giải thích: Số ~10~ được phân tích thành tổng của ~3~ số ~{2,3,5}~, bội chung nhỏ nhất của ba số đó bằng ~30~, đây là kết quả lớn nhất có thể.

Theo truyền thuyết, vua Sêram rất khâm phục và đã tặng thưởng cho nhà thông thái Sêta vì đã sáng tạo ra cờ vua. Phần thưởng mà Sêta mong muốn là tất cả các hạt lúa mì đặt trên bàn cờ theo quy tắc sau: Ô thứ nhất đặt một hạt, ô thứ hai đặt 2 hạt, ô thứ ba đặt 4 hạt, … , tiếp tục theo quy luật ô sau có số hạt gấp đôi số hạt của ô trước, cho tới khi đặt đến ô thứ 64 trên bàn cờ vua. Rất thích thú với truyền thuyết này, Long và Vân cùng nhau giải quyết bài toán sau:

Xét một bảng số kích thước ~m*n~, các hàng được đánh số từ 1 đến ~m~ từ trên xuống dưới, các cột được đánh số từ 1 đến ~n~ từ trái sang phải. Ô nằm giao giữa hàng ~i~ và cột ~j~ được gọi là ô ~(i,j)~. Với một số nguyên dương ~k~ ~(k \le 10)~, lần lượt điền các số vào các ô của bảng theo nguyên tắc sau:

• Bắt đầu điền từ ô ~(1,1)~ ghi số ~1~;
• Điền lần lượt từng ô từ trên xuống dưới, từ trái qua phải. Ô tiếp theo điền giá trị gấp ~k~ lần giá trị điền ô trước.

Với bộ 4 số nguyên dương ~(x,y,u,v)~ thỏa mãn ~1≤x≤u≤m~ và ~1≤y≤v≤n~, hai bạn Long và Vân muốn tính tổng các số nằm trong các ô ~(i,j)~ mà ~x≤i≤u~ và ~y≤j≤v~.

Yêu cầu: Cho ~7~ số nguyên dương ~m,n,k,x,y,u,v~, hãy tính tổng các số nằm trong các ô ~(i,j)~ mà ~x≤i≤u~ và ~y≤j≤v~ của bảng số được điền theo quy tắc trên.

Input

• Một dòng chứa 7 số nguyên dương ~m,n,k,x,y,u,v~. ~(1 \le n,m \le 10^9)~

Output

• Một dòng chứa một số là phần dư của phép chia tổng các số được tính chia cho ~111539768~.

Sample Test

Input:

4 4 2 1 2 2 3

Output:

102

Cho số tự nhiên ~n, m~, hãy tính ~\sum_{i=1} ^{m} n \% i~.

Input

• Chứa 2 số tự nhiên ~1 \le n, m \le 10^{13}~.

Output

• Đáp án modulo ~10^9+7~.

Sample Test

Input:

3 4

Output:

4

Nhắc lại ~F_n~ là số fibonacci thứ ~n~ với ~F_1 = F_2 = 1~.

Cho mảng ~a~ có ~n~ phần tử và ~q~ truy vấn có một trong 2 dạng sau đây:

• 1 l r, cộng thêm giá trị ~F_{i - l + 1}~ với mỗi phần tử ~l \le i \le r~.
• 2 l r, in ra ~\sum_{i=l} ^{r} a_i~ modulo ~10^9+9~.

Input

• Dòng đầu tiên gồm 2 số ~1 \le n, q \le 300000~.
• Dòng tiếp theo gồm ~n~ số tự nhiên của mảng ~a~ (~1 \le a_i \le 10^9~).

Output

• In ra kết quả của mỗi truy vấn 2.

Sample Test

Input:

4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3

Output:

17
12