3

K Turns Allowed

Difficulty: MEDIUM
Avg. time to solve
25 min
Success Rate
70%

Problem Statement
Suggest Edit

Given a matrix, count 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)
See the sample input.
Note:
The answer should be in the mod(10^9+7)
Input format :
Line 1 : Number of rows N in the matrix
Line 2 : Number of cols M in the matrix
Line 3 : Maximum turns allowed K
Output Format :
 Return number of paths
Constraints :
 1 <= N <= 10^2
 1 <= M <= 10^2
 1 <= K <= 200
Sample Input :
3
3
2
Sample Output :
4
Explanation :
Paths with 0 turn = 0
Paths with 1 turn = 2
Paths with 2 turns = 2
Want to solve this problem? Login now to get access to solve the problems