### PROBLEM LINK:

**Author**: Devendra Agarwal

**Tester**: Anudeep Nekkanti

**Editorialist**: Amit Pandey

### DIFFICULTY:

Simple.

### PREREQUISITES:

Dynamic programming or combinatorics.

### PROBLEM:

Dehatti wonders how many ways can his team score exactly R runs in B balls with L wickets. Given that each ball can result in 4, 6, 0 runs or a wicket(wicket won’t add anything to score).

### QUICK EXPLANATION:

Suppose we want to make R runs in B balls, having X number of 4's, Y number of 6's, (W \le L) number of wickets and Z number of 0's. So there will be 4X + 6Y = R and X+Y+W+Z = B. If (x,y,z,w) is a particular solution to given equations, then number of ways of arrangement will be \frac {B!}{(x!)(y!)(w!)(z!)}. We have to add all such cases, and the given time limit is sufficient for it.

### EXPLANATION:

First of all, pre-calculate the value of ^n C_{r} which can be done using a simple dynamic programming approach. You may refer this link for the more details.

As batsman has to make R runs in B balls, if R > 6B, there will not be any way of doing it.

Suppose he makes R runs in B balls, with at-max L wickets. So, we will have the following equations.

4 \times \text{fours} + 6 \times \text{sixes} = R \\ \text{fours} + \text{sixes} + \text{wickets}(\le L) + \text{zeros} = B

There will be many solutions to the given equations for particular values of R,B and L. We have to consider each one of them.

Let us consider that a particular solution of the equation is fours = X, sixes = Y, wickets = W and zeros = Z, or (X,Y,Z,W) is a solution to the given equations.

So, number of ways of arranging X \hspace{2 mm}4's, Y \hspace{2 mm}6's, W wickets ans Z \hspace{2 mm}0's can be calculated easily using the formula.

\text{Ways} = \frac {B!}{(X!)(Y!)(Z!)(W!)} \\ ={B \choose X} {B-X \choose Y} {B-X-Y \choose W}

Values can be used from initially calculated {n \choose r} values . Take care of modulus as well.

T only thing remains is to produce all the triplets (X,Y,Z,W).

We can run a loop on number of sixes varying from 0 to min(B,R/6),number of fours will be fixed i.e.

```
Number of fours = (R -6*sixes)/4 if ((R - 6*sixes) % 4 == 0)
```

And we can loop over number of wickets from 0 to L.

```
Number of zeros = B-sixes-fours-wickets
```

The following piece of self explanatory code will do all the calculations.

```
for(int six=0; six*6 <= r && six <= b; six++) {
int other = r - six*6;
if(other % 4 == 0) {
int four = other/4;
for(int wicket=0; wicket <= l; wicket++) {
if(six + four + wicket <= b) {
long long cur = C[b][six];
( cur *= C[b-six][four] ) %= 1000000007;
( cur *= C[b-six-four][wicket] ) %= 1000000007;
ways += cur;
}
}
ways %= 1000000007;
}
}
```

### Solutions:

Setter’s solution can be found here .

Setter’s another solution can be found here .

Tester’s solution can be found here.