CareerCup

Testing Strings
Mr X and Mr Y, his friend are programmers and testers respectively working in the same company. So, once they faced the following scenario :

Mr X wrote an application that took as input some user data. The data the application took as input was a string in some strange language. That language consisted of
K
K distinct letters. However, due to some issues, the application got corrupted and one particular String among many was lost.

However, Mr X had seen that String once before it got lost. He remembers some info about it. Particu-larly, he remembers the lost String had length equal to
M
M.

Mr Y, being the chief QA person in his company needs to try and figure out the number of possible different possible candidate Strings for the lost String.

Mr X remembers N pieces of info. For each one, he gives you 2 numbers
L
L and
R
R and a number
Z
Z. He remembers for sure that the
Z
t
h
Zth letter of the language of the string did not occur between positions
L
L and
R
R inclusive of the lost String.

Input Format :

The first line contains
3
3 space separated integers
N
N ,
M
M and
K
K.

Each of the next
N
N contains
3
3 space separated integers, denoting
L
L ,
R
R and
Z
Z respectively.

Output Format :

You need to find and print the number of different possible candidate Strings for the lost String based on the info Mr X remembers. As the number of such Strings can be large, print it Modulo
10
6
+
3
106+3
Constraints:

1
≤
N
,
M
,
K
≤
10
5
1≤N,M,K≤105

1
≤
L
≤
R
≤
M
1≤L≤R≤M
1
≤
Z
≤
K
1≤Z≤K
Sample Input
1 2 26
1 2 1
Sample Output
625

Today Jin has given a task to Shino, Shino has to travel from cell
(
1
,
1
)
(1,1) to cell
(
N
,
M
)
(N,M) in a grid of size
N
∗
M
N∗M. But in order make this task interesting for Shino, Jin has decided to keep some special candies in some
K
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
0.

Now, you need to find and print the sum of the values of all paths from
(
1
,
1
)
(1,1) to
(
N
,
M
)
(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
T denoting number of test cases

The next line contains
3
3 space separated integers,
N
N,
M
M and
K
K where N * M is the size of grid & K denoting number of special cells

The next
K
K lines contains three integers
X
i
,
Y
i
,
H
i
Xi,Yi,Hi where
(
X
i
,
Y
i
)
(Xi,Yi) is cell coordinate &
H
i
Hi is the amount of happiness Shino will get from a candy at cell
(
X
i
,
Y
i
)
(Xi,Yi)

Constraints

1
≤
T
≤
3
1≤T≤3
1
≤
N
,
M
,
K
≤
10
5
1≤N,M,K≤105

1
≤
X
i
≤
N
,
1
≤
Y
i
≤
M
1≤Xi≤N,1≤Yi≤M

1
≤
H
i
≤
10
5
1≤Hi≤105

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
109+7
Sample Input
1
2 2 2
1 2 4
2 1 7
Sample Output
11