Sol is a boy with a peculiar passion for numbers. He enjoys discovering patterns and creating unique challenges to improve his calculation skills. One day, while strolling through the village market, he noticed a vendor displaying a peculiar grid of numbers on a mat. Each square was arranged in rows and columns, forming a beautiful numeric grid. Intrigued, Sol asked the vendor about its significance and was told that it was a mysterious grid with hidden patterns devised by its creator.

Fascinated by its beauty, Sol decided to create his own grid, not just a chaotic arrangement of numbers, but one following a clear and logical pattern. He devised a special way to fill the grid with numbers:

1. Grid Structure:

   • Sol would create a grid of size ~M \times N~, with ~M~ rows and ~N~ columns. He imagined each cell in the grid as an empty square, ready to be adorned with his numbers.

2. Filling Rules: To maintain harmony in the grid, Sol decided:

   • In the cell located at row ~i~ and column ~j~, he would fill the number ~(i - 1) \times N + j~ if the sum ~(i + j)~ is even. This ensures that cells in harmonious positions will glow with patterned numbers.
   • If the sum ~(i + j)~ is odd, he would fill the cell with ~0~. This creates an alternating pattern of highlighted and neutral cells, producing a fascinating symmetry.

Task:

Help Sol compute the sum of all numbers in the grid following the rules above, modulo (C).

Input:

• The first line contains an integer ~Q~, the number of queries ~(Q \leq 10^5)~.
• The next ~Q~ lines, each containing three positive integers ~M, N,~ and ~C~ ~(M, N, C \leq 10^{18})~.

Output:

• The output consists of ~Q~ lines, each containing a single integer: the sum of the grid elements modulo ~C~.

Sample Input

1
3 4 100

Sample Output

38

Notes

• The grid filled by Sol based on the rules is as follows:

In a kingdom, cities are connected by simple roads. To better manage traffic and determine the number of routes possible between cities, the administrator has asked for your help in performing some calculations.

Specifically, the kingdom has ~N~ cities and ~M~ roads. Each road directly connects two cities and has a weight of ~1~. The administrator has prepared a set of queries to calculate specific routes.

For each query, you are given three integers ~u~, ~v~, and ~K~, and you must calculate the number of paths from city ~u~ to city ~v~ with a total weight exactly equal to ~K~. You may revisit the same city multiple times if necessary to achieve the required total weight.

Your task is to help the administrator answer these queries. For each query, compute the number of paths from city ~u~ to city ~v~ with a weight of ~K~, and return the result modulo ~10^9 + 7~.

Input:

1. The first line contains two integers ~N~ and ~M~ ~(M \leq \frac{N(N-1)}{2})~.
2. The next ~M~ lines each contain two integers ~u~ and ~v~, indicating a direct road between city ~u~ and city ~v~ ~(1 \leq u \leq v \leq N)~.
3. The following line contains an integer ~Q~, the number of queries.
4. The next ~Q~ lines each contain three integers ~u~, ~v~, and ~K~, representing a query.

Output:

• ~Q~ lines, each containing an integer: the number of paths from city ~u~ to city ~v~ with a total weight of ~K~, modulo ~10^9 + 7~.

Sample Input

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

Sample Output

3
1

Notes

For query ~1~, the paths are:

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

For query ~2~, the path is:

• ~2 \to 3 \to 1~

Constraints:

• Subtask ~1~ (~40\%~ of points): ~N, Q, K \leq 10~.
• Subtask ~3~ (~15\%~ of points): ~N \leq 10, K \leq 20,~ and ~Q \leq 10^5~.
• Subtask ~4~ (~15\%~ of points): ~N \leq 100, K \leq 10,~ and ~Q \leq 20~.
• Subtask ~5~ (~15\%~ of points): ~N \leq 100, K \leq 50,~ and ~Q \leq 10^5~.
• Subtask ~6~ (~15\%~ of points): ~N \leq 100, K \leq 10^5,~ and ~Q \leq 10~.

Once upon a time, in a small village at the foot of a mountain, there was a blacksmith named Jack. He was famous throughout the region for crafting weapons with perfect durability and sharpness. One day, he received a request from the king of the kingdom to prepare a large quantity of weapons for the army in defense of the upcoming winter.

Jack has ~n~ types of rare iron ores, each with a different weight, and he can melt a maximum of ~m~ kg of ores at a time in his forge. It is known that each different combination of ores results in a different product. Jack wants to find all possible ways to select ores to put into the forge, such that the total weight of the selected ores does not exceed ~m~ kg. Notably, each type of ore can only be selected once.

Jack is very meticulous and wants to ensure that no combination is missed. He hopes that you, with your mathematical talent, can help him count all the ways to choose the ores such that the total weight is within the allowed limit.

Task:

Help Jack compute the number of ways to choose different types of ores such that their total weight does not exceed ~m~ kg. Since the number of ways may be very large, return the result modulo ~10^9 + 7~.

Input:

• The first line contains two integers ~n~ and ~m~ (~n, m \leq 1000~).
• The second line contains ~n~ integers ~a_1, a_2, ..., a_n~ (~a_i \leq 1000~), representing the weight of each ore type.

Output:

• A single integer: the number of ways to choose ores such that their total weight does not exceed ~m~ kg, modulo ~10^9 + 7~.

Sample Input

2 16
9 7

Sample Output

4

Notes

Jack can melt ores as follows:

• Way ~1: 9~
• Way ~2: 7~
• Way ~3: 9 \to 7~
• Way ~4: 7 \to 9~

Constraints:

• Subtask ~1~ (~30\%~ of points): ~n \leq 6~
• Subtask ~2~ (~30\%~ of points): ~n \leq 20~
• Subtask ~3~ (~40\%~ of points): No additional constraints.

One beautiful morning, J97 sat by the window, holding a cup of hot coffee, watching the clouds drifting by. Today was a day off, and J97 wanted to take some time to reflect on what he had experienced. Like many people, J97's life was a series of ordinary days interspersed with a few special moments, sometimes filled with joy, sometimes tinged with a bit of sadness. And, like everyone else, J97 realized that his life had "weights" - moments when the ups and downs were more pronounced, leaving a deeper mark in his heart.

J97 suddenly thought: "If every day, every sequence of memories, were a number, then what would be the 'weight' of that sequence of memories?" He imagined that for each memory segment - from the shortest, consisting of just one moment, to the longest, including the entire past year - he could measure the "weight" of that segment: the difference between the best and worst moments of each memory. A very peaceful day would have a weight of 0, while a week with all kinds of emotions would have a greater weight.

With this thought, J97 decided to find a way to calculate the sum of all the "weights" of the memory segments in his life, from the shortest to the longest. This was an interesting problem, and he found a way to simulate it with an integer array ~A~, which contains ~n~ elements: ~A_1, A_2, ..., A_n~. Now, J97 wants you to help him calculate the total weight of all contiguous subarrays of ~A~ to understand the weight of his life. The weight of a subarray is defined as the difference between the maximum and minimum elements in that subarray.

Input:

• The first line contains a positive integer ~n~ (~n \leq 4 \times 10^5~).
• The second line contains ~n~ positive integers ~A_1, A_2, ..., A_n~ (~A_i \leq 10^6~).

Output:

• A single integer representing the result.

Sample Input

3 
1 2 3

Sample Output

4

Notes

The weights are represented as follows:

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

Constraints:

• Subtask ~1~ (~30\%~ of points): ~n \leq 4 \times 10^2~
• Subtask ~2~ (~30\%~ of points): ~n \leq 10^4~
• Subtask ~3~ (~40\%~ of points): No additional constraints.