Sol là một cậu bé có niềm đam mê đặc biệt với những con số. Cậu thích khám phá các quy luật và tạo ra những thử thách độc đáo để rèn luyện kỹ năng tính toán của mình. Một ngày nọ, khi dạo bước trong chợ làng, Sol nhìn thấy một người bán hàng bày ra một tấm thảm có in một lưới số kỳ lạ. Mỗi ô vuông được sắp xếp theo hàng và cột, tạo thành một ma trận số tuyệt đẹp. Bị cuốn hút, Sol hỏi người bán về ý nghĩa của nó và được biết rằng đây là một lưới bí ẩn với các quy luật ẩn giấu do người tạo ra nghĩ ra.

Bị vẻ đẹp ấy hấp dẫn, Sol quyết định tạo ra lưới của riêng mình, không phải là sự sắp xếp ngẫu nhiên của các con số, mà là một cấu trúc rõ ràng và logic. Cậu đã nghĩ ra một cách đặc biệt để điền số vào lưới:

1. Cấu trúc lưới:

   • Sol sẽ tạo một lưới kích thước ~M \times N~, với ~M~ hàng và ~N~ cột. Cậu tưởng tượng mỗi ô trong lưới như một ô vuông trống, sẵn sàng để được trang trí bằng những con số của mình.

2. Quy tắc điền số: Để giữ cho lưới hài hòa, Sol quyết định:

   • Ở ô nằm tại hàng ~i~ và cột ~j~, cậu sẽ điền số ~(i - 1) \times N + j~ nếu tổng ~(i + j)~ là số chẵn. Điều này đảm bảo rằng các ô ở vị trí hài hòa sẽ sáng lên với những con số theo quy luật.
   • Nếu tổng ~(i + j)~ là số lẻ, cậu sẽ điền ~0~ vào ô đó. Cách này tạo nên một mẫu xen kẽ giữa các ô nổi bật và trung tính, tạo ra sự đối xứng cuốn hút.

Nhiệm vụ:

Hãy giúp Sol tính tổng tất cả các số trong lưới theo quy tắc trên, lấy dư theo (C).

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên ~Q~, là số lượng truy vấn ~(Q \leq 10^5)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~M, N,~ và ~C~ ~(M, N, C \leq 10^{18})~.

Dữ liệu ra:

• Gồm ~Q~ dòng, mỗi dòng chứa một số nguyên: tổng các phần tử trong lưới theo modulo ~C~.

Ví dụ nhập

1
3 4 100

Ví dụ xuất

38

Ghi chú

• Lưới do Sol điền theo quy tắc như sau:

Trong một vương quốc, các thành phố được kết nối với nhau bằng những con đường đơn giản. Để quản lý giao thông tốt hơn và xác định số tuyến đường có thể đi giữa các thành phố, nhà quản lý đã nhờ bạn hỗ trợ thực hiện một số phép tính.

Cụ thể, vương quốc có ~N~ thành phố và ~M~ con đường. Mỗi con đường nối trực tiếp hai thành phố và có trọng số là ~1~. Nhà quản lý đã chuẩn bị một tập truy vấn để tính toán các tuyến đường cụ thể.

Với mỗi truy vấn, bạn được cho ba số nguyên ~u~, ~v~, và ~K~, và bạn phải tính số đường đi từ thành phố ~u~ đến thành phố ~v~ với tổng trọng số chính xác bằng ~K~. Bạn có thể đi qua lại cùng một thành phố nhiều lần nếu cần để đạt được tổng trọng số yêu cầu.

Nhiệm vụ của bạn là giúp nhà quản lý trả lời các truy vấn này. Với mỗi truy vấn, hãy tính số đường đi từ thành phố ~u~ đến thành phố ~v~ có trọng số bằng ~K~, và trả về kết quả theo modulo ~10^9 + 7~.

Dữ liệu vào:

1. Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(M \leq \frac{N(N-1)}{2})~.
2. ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~, biểu thị một con đường trực tiếp giữa thành phố ~u~ và thành phố ~v~ ~(1 \leq u \leq v \leq N)~.
3. Dòng tiếp theo chứa một số nguyên ~Q~, là số lượng truy vấn.
4. ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~, và ~K~, biểu thị một truy vấn.

Dữ liệu ra:

• ~Q~ dòng, mỗi dòng chứa một số nguyên: số đường đi từ thành phố ~u~ đến thành phố ~v~ có tổng trọng số bằng ~K~, theo modulo ~10^9 + 7~.

Ví dụ nhập

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

Ví dụ xuất

3
1

Ghi chú

Với truy vấn ~1~, các đường đi là:

• ~1 \to 3 \to 1 \to 3~
• ~1 \to 3 \to 2 \to 3~
• ~1 \to 3 \to 4 \to 3~

Với truy vấn ~2~, đường đi là:

• ~2 \to 3 \to 1~

Giới hạn:

• Subtask ~1~ (~40%~ số điểm): ~N, Q, K \leq 10~.
• Subtask ~3~ (~15%~ số điểm): ~N \leq 10, K \leq 20,~ và ~Q \leq 10^5~.
• Subtask ~4~ (~15%~ số điểm): ~N \leq 100, K \leq 10,~ và ~Q \leq 20~.
• Subtask ~5~ (~15%~ số điểm): ~N \leq 100, K \leq 50,~ và ~Q \leq 10^5~.
• Subtask ~6~ (~15%~ số điểm): ~N \leq 100, K \leq 10^5,~ và ~Q \leq 10~.

Ngày xửa ngày xưa, tại một ngôi làng nhỏ dưới chân núi, có một người thợ rèn tên là Jack. Ông nổi tiếng khắp vùng vì rèn ra những vũ khí có độ bền và độ sắc bén hoàn hảo. Một ngày nọ, ông nhận được yêu cầu từ nhà vua của vương quốc chuẩn bị một số lượng lớn vũ khí cho quân đội để phòng thủ trong mùa đông sắp tới.

Jack có ~n~ loại quặng sắt hiếm, mỗi loại có trọng lượng khác nhau, và ông có thể nấu chảy tối đa ~m~ kg quặng trong lò rèn cùng một lúc. Người ta biết rằng mỗi tổ hợp quặng khác nhau sẽ tạo ra một sản phẩm khác nhau. Jack muốn tìm tất cả các cách có thể để chọn quặng đưa vào lò, sao cho tổng trọng lượng của các quặng được chọn không vượt quá ~m~ kg. Đáng chú ý, mỗi loại quặng chỉ có thể được chọn một lần.

Jack rất cẩn thận và muốn chắc chắn rằng không bỏ sót bất kỳ tổ hợp nào. Ông hy vọng rằng bạn, với tài năng toán học của mình, có thể giúp ông đếm tất cả các cách chọn quặng sao cho tổng trọng lượng nằm trong giới hạn cho phép.

Nhiệm vụ:

Hãy giúp Jack tính số cách chọn các loại quặng khác nhau sao cho tổng trọng lượng không vượt quá ~m~ kg. Vì số cách có thể rất lớn, hãy trả về kết quả theo modulo ~10^9 + 7~.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~n, m \leq 1000~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~a_i \leq 1000~), biểu thị trọng lượng của từng loại quặng.

Dữ liệu ra:

• Một số nguyên: số cách chọn quặng sao cho tổng trọng lượng không vượt quá ~m~ kg, theo modulo ~10^9 + 7~.

Ví dụ nhập

2 16
9 7

Ví dụ xuất

4

Ghi chú

Jack có thể nấu chảy quặng như sau:

• Cách ~1: 9~
• Cách ~2: 7~
• Cách ~3: 9 \to 7~
• Cách ~4: 7 \to 9~

Giới hạn:

• Subtask ~1~ (~30%~ số điểm): ~n \leq 6~
• Subtask ~2~ (~30%~ số điểm): ~n \leq 20~
• Subtask ~3~ (~40%~ số điểm): Không có ràng buộc bổ sung.

Một buổi sáng đẹp trời, J97 ngồi bên cửa sổ, cầm trên tay tách cà phê nóng, ngắm nhìn những đám mây trôi lững lờ. Hôm nay là ngày nghỉ, và J97 muốn dành chút thời gian để suy ngẫm về những gì mình đã trải qua. Giống như nhiều người, cuộc đời J97 là chuỗi những ngày bình thường xen lẫn vài khoảnh khắc đặc biệt, đôi khi ngập tràn niềm vui, đôi khi lại vương chút buồn. Và, như mọi người khác, J97 nhận ra rằng cuộc sống của mình có những "sức nặng" – những lúc thăng trầm rõ rệt hơn, để lại dấu ấn sâu đậm trong tim.

Bất chợt, J97 nghĩ: "Nếu mỗi ngày, mỗi chuỗi ký ức đều là một con số, thì 'sức nặng' của chuỗi ký ức ấy sẽ là gì?"" Cậu hình dung rằng với mỗi đoạn ký ức – từ ngắn nhất chỉ gồm một khoảnh khắc, cho đến dài nhất bao trọn cả năm vừa qua – cậu có thể đo "sức nặng" của đoạn đó: chính là hiệu số giữa khoảnh khắc đẹp nhất và tệ nhất trong chuỗi ký ức. Một ngày thật yên bình sẽ có sức nặng bằng ~0~, còn một tuần với đủ mọi cảm xúc sẽ có sức nặng lớn hơn.

Với ý nghĩ đó, J97 quyết định tìm cách tính tổng tất cả "sức nặng" của những đoạn ký ức trong cuộc đời mình, từ ngắn nhất đến dài nhất. Đây là một bài toán thú vị, và cậu đã tìm ra cách mô phỏng nó bằng một mảng số nguyên ~A~ gồm ~n~ phần tử: ~A_1, A_2, ..., A_n~. Giờ đây, J97 muốn bạn giúp cậu tính tổng sức nặng của tất cả các dãy con liên tiếp của ~A~, để hiểu được sức nặng cuộc đời mình. Sức nặng của một dãy con được định nghĩa là hiệu giữa phần tử lớn nhất và nhỏ nhất trong dãy đó.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên dương ~n~ (~n \leq 4 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ (~A_i \leq 10^6~).

Dữ liệu ra:

• Một số nguyên duy nhất biểu thị kết quả.

Ví dụ nhập

3 
1 2 3

Ví dụ xuất

4

Ghi chú

Các sức nặng được tính như sau:

• ~[1, 2] = (2 - 1) = 1~
• ~[1, 3] = (3 - 1) = 2~
• ~[2, 3] = (3 - 2) = 1~

Giới hạn:

• Subtask ~1~ (~30%~ số điểm): ~n \leq 4 \times 10^2~
• Subtask ~2~ (~30%~ số điểm): ~n \leq 10^4~
• Subtask ~3~ (~40%~ số điểm): Không có ràng buộc bổ sung.