 0

# Path with K Coins

Difficulty: HARD Contributed By
Ankush Gupta
Avg. time to solve
45 min
Success Rate
45%

Problem Statement

#### More formally, return the number of paths whose total sum of coins is equal to ‘K’ from 0,0 to ‘N - 1’, ‘M - 1’.

##### Note:
``````Since the answer can be very large print the answer modulo 10 ^ 9 + 7.
``````

#### For example

``````Given:
‘N’ = 3, ‘M’ = 3
‘Grid[][]’ = [[5, 2, 5],
[3, 3, 1],
[3, 5, 1]]
‘K’ = 14.
The answer will be 1, since There is only 1 path that is from (0,0) to (0,1) to (0,2) to (1,2) to (2,2) this is because 5 + 2 + 5 + 1 + 1 = 14
``````
##### Input format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘M,’ where ‘M’ is the number of rows in ‘SEATS’ and ‘N’ where ‘N’ is the number of columns in ‘GRID’.

The next ‘M’ lines of each test case contains ‘N’ space-separated integers, which denotes the number of coins at each point.

The next line of each test case contains a single integer ‘K’.
``````
##### Output Format :
``````For each test case, You are supposed to return an integer that denotes the total number of paths with the sum of coins equal to ‘K’.
``````
##### Note:
``````You are not required to print the expected output; it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= ‘T’ <= 10
1 <= ‘N’ <= 20
1 <= ‘M’ <= 20
0 <= ‘K’ <= 1000

Time Limit: 1sec.
``````

#### Sample Input 1 :

``````2
3 3
5 2 5
3 3 1
3 5 1
14
2 3
1 2 1
2 2 1
6
``````

#### Sample Output 1 :

``````1
2
``````

#### Explanation of the Sample Input 1:

``````In the first test case, The answer will be 1, since There is only 1 path that is from (0,0) to (0,1) to (0,2) to (1,2) to (2,2) this is because 5 + 2 + 5 + 1 + 1 = 14

In the second test case, The answer will be 2, since there are 2 paths those are (0,0) to (1,0) to (1,1) to (1,2) and (0,0) to (0,1) to (1,1) to (1,2) and 1 + 2 + 2 + 1 = 6 in both cases.
``````

#### Sample Input 2 :

``````2
3 3
1 2 3
4 5 6
1 2 3
11
2 2
1 1
1 1
3
``````

#### Sample Output 2 :

``````3
2
``````   Console