Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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

```
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.
```

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

```
The answer should be in the mod(10 ^ 9 + 7)
The output of each test case will be printed in a separate line.
```

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

```
1 <= T <= 5
1 <= N <= 50
1 <= M <= 50
1 <= K <= 100
Time limit: 1 sec.
```

```
1
3 3 2
```

```
4
```

```
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
```

```
2
4 5 3
2 3 4
```

```
19
3
```

```
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.
```