Number of ways of scoring R runs in B balls with at most W wickets

Given three integers R, B, and W which denote the number of runs, balls, and wickets. One can score 0, 1, 2, 3, 4, 6, or a wicket in a single ball in a cricket match. The task is to count the number of ways in which a team can score exactly R runs in exactly B balls with at-most W wickets. Since the number of ways will be large, print the answer modulo 1000000007. 
Examples: 
 

Input: R = 4, B = 2, W = 2 
Output: 7 
The 7 ways are: 
0, 4 
4, 0 
Wicket, 4 
4, Wicket 
1, 3 
3, 1 
2, 2 
Input: R = 40, B = 10, W = 4 
Output: 653263 
 

Approach: The problem can be solved using Dynamic Programming and Combinatorics. The recurrence will have 6 states, we initially start with runs = 0, balls = 0 and wickets = 0. The states will be: 
 

• If a team scores 1 run off a ball then runs = runs + 1 and balls = balls + 1.
• If a team scores 2 runs off a ball then runs = runs + 2 and balls = balls + 1.
• If a team scores 3 runs off a ball then runs = runs + 3 and balls = balls + 1.
• If a team scores 4 runs off a ball then runs = runs + 4 and balls = balls + 1.
• If a team scores 6 runs off a ball then runs = runs + 6 and balls = balls + 1.
• If a team scores no run off a ball then runs = runs and balls = balls + 1.
• If a team loses 1 wicket off a ball then runs = runs and balls = balls + 1 and wickets = wickets + 1.

The DP will consist of three stages, with the run state being a maximum of 6 * Balls, since it is the maximum possible. Hence dp[i][j][k] denotes the number of ways in which i runs can be scored in exactly j balls with losing k wickets. 
Below is the implementation of the above approach: 
 

653263

Time Complexity: O(r*b*w), as we are using recursion with memorization, so we will avoid redundant function calls and the complexity will be O(r*b*w)

Auxiliary Space: O(300*50*10), as we are using extra space for the dp matrix.