All Tracks Math Combinatorics Basics of Combinatorics Problem

Shino and K-Special Cells
Tag(s):

Easy, Math

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...
Your Rating:

Contributor

This Problem was Asked in

ThoughtWorks

Challenge Name

ThoughtWorks QA Analyst Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?