SOLVE
LATER
Today Jin has given a task to Shino, Shino has to travel from cell \((1,1)\) to cell \((N,M)\) in a grid of size \(N * M \). But in order make this task interesting for Shino, Jin has decided to keep some special candies in some K special cells of the grid, where each candy has an amount of happiness associated with it.
Shino can travel only in right & down direction in the grid, as he is too careful & does not want to fall out of grid. Now, we call the value of a path the happiness of all cells lying on the path. All non-special cells have happiness equal to 0.
Now, you need to find and print the sum of the values of all paths from \((1,1)\) to \((N,M)\), traveling only right and down to an adjacent cell.
As Shino is not good at counting help him find the answer.
Input Format
The first Line contains a single integer T denoting number of test cases
The next line contains 3 space separated integers, N, M and K where N * M is the size of grid & K denoting number of special cells
The next K lines contains three integers \(X_{i}, Y_i, H_i \) where \((Xi,Yi)\) is cell coordinate & \(H_i\) is the amount of happiness Shino will get from a candy at cell \((X_i,Y_i)\)
Constraints
\( 1 \le T \le 3 \)
\( 1 \le N,M,K \le 10^5 \)
\( 1 \le X_{i} \le N, 1 \le Y_{i} \le M \)
\( 1 \le H_{i} \le 10^5 \)
Output Format
For each test case you will output a single integer denoting the total amount of happiness Shino will get. As the answer can be quiet large you can output answer modulo \( 10^9+7 \)
.