You are given a matrix which has k special cells in it. You have to reach (n,m) from (1,1). From any cell, you can only move rightwards or downwards.
The k special cells are those cells in this grid which have special strength at them. i-th special cell has pi units of strength and if you travel through this cell, you store the strength.
Find the total strength you can store after travelling through all the possible paths in the grid to reach cell (n,m).
Note that:
The strength of a path is the sum of strength pi of all the special cells that are visited in this path.
The cells that are not special have power quotient equals to zero.
The first line contains the total number of test cases t.
The first line of each test case contains three space separated integers n,m(1≤n,m≤105) and k(1≤k≤106) where n∗m is the size of grid and k is the total number of special cells in the grid. Each of next k lines contains xi,yi(1≤xi≤n,1≤yi≤m), and pi(1≤pi≤105) where (xi,yi) is the location of special cell and pi is the cell strength.
For each test case, print in a new line a single integer representing the total strength that you can store, as the total strength can be too large, print it modulo 109+7.