## pooja.senger86

BAN USER- 0of 0 votes

AnswersTesting Strings

- pooja.senger86 in United States

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

A9 abc .Net/C Java - 0of 0 votes

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

- pooja.senger86 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

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

Open Chat in New Window