K Turns Allowed

Moderate

0/80

Average time to solve is 25m

Contributed by

10 upvotes

Asked in companies

Problem statement

Ninja has been given the dimensions of a matrix, count the number of paths to reach the bottom right from top left with maximum k turns allowed.

A valid turn :

There are two possible scenarios when a turn can occur at point (i, j):

Turns Right: (i - 1, j)  ->  (i, j)  ->  (i, j + 1)

Turns Down:  (i, j-1)  ->  (i, j)  ->  (i+1, j)

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains three space-separated integers ‘N’, ’M’, and ‘K’ denoting the number of rows, columns, and maximum turn around respectively.

Output Format:

For each case, we need to print the total number of possible paths % (10 ^ 9 + 7).

Note:

The answer should be in the mod(10 ^ 9 + 7)

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, and it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 50
1 <= M <= 50
1 <= K <= 100

Time limit: 1 sec.

Sample Input 1:

1 
3 3 2

Sample Output 1:

Explanation of Sample Input 1:

Test case 1:
For the first test case of sample output 1, we can reach the right bottom point through the following ways:
0 turns -> 0 ways
1 turn -> 2 ways
2 turns -> 2 ways
Hence our answer shall be 4

Sample Input 2:

2 
4 5 3
2 3 4

Sample Output 2:

19
3

Explanation of Sample Input 2:

Test case 1:
For the first test case of sample output 2, we can reach the right bottom point through the following ways:
0 turns -> 0 ways
1 turn -> 2 ways
2 turns -> 5 ways
3 turns -> 12 ways
Hence our answer shall be 19

Test case 2:
For the second test case of sample output 2, we can reach the right bottom point through the following ways:
0 turns -> 0 ways
1 turn -> 2 ways
2 turns -> 1 ways
Hence our answer shall be 3.

Console