Shino and K-Special Cells
Tag(s):

## Combinatorics basics, Easy, Mathematics

Problem
Editorial
Analytics

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$

SAMPLE INPUT
1
2 2 2
1 2 4
2 1 7
SAMPLE OUTPUT
11

Explanation

.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

ThoughtWorks QA Analyst Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Arrays