K special cells#11455
You are given a matrix of size n \times m with special cells. You need to reach cell starting from . From any cell, you are allowed to move only to the right or down.
Each of the special cells has a certain power. The -th special cell has power p_i, and if you pass through this cell, you gain this power.
Your task is to find the total power that can be collected over all possible paths from to .
Note that:
The power of a path is the sum of the values p_i of all special cells visited along this path.
Regular cells that are not special have power equal to zero.
The first line contains an integer — the number of test cases.
The first line of each test case contains three integers n, m~(1 \le n, m \le 10^5) and k~(1 \le k \le 10^6), where n \times m is the size of the grid, and is the number of special cells.
Each of the next lines contains three integers x_i, y_i~(1 \le x_i \le n, 1 \le y_i \le m) and p_i~(1 \le p_i \le 10^5), where (x_i, y_i) is the position of a special cell, and p_i is its power.
For each test case, print on a separate line the total power that can be collected. Since the result may be very large, output it modulo 10^9 + 7.
Example 1