## A9 Interview Question for abcs

- 0of 0 votes

AnswerToday Jin has given a task to Shino, Shino has to travel from cell

- pooja.senger86 October 29, 2017 in United States

(

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| Report Duplicate | Flag | PURGE

A9 abc .Net/C Algorithm Java

**Country:**United States

**Interview Type:**Written Test

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

DP soln. - O(n^2)

- sudip.innovates October 31, 2017