### Problem Statement

The top few rows of Pascal's triangle are drawn below:
```                 1
1   1
1   2   1
1   3   3   1
1   4   6   4   1```
The leftmost and rightmost values of a particular row are always 1. An inner value v can be found by adding together the 2 numbers found immediately above v, on its right and left sides. For example, the 6 in the above figure is the sum of the two 3s above it. Return the number of values in row i of Pascal's triangle that are evenly divisible by d. The rows are 0-based, so row 3 contains 1,3,3,1.

### Definition

 Class: PascalCount Method: howMany Parameters: int, int Returns: int Method signature: int howMany(int i, int d) (be sure your method is public)

### Notes

-The jth element (0-based) of row i can be computed by the formula:
`   	  i!    ---------------      j! * (i-j)! `
where k! = 1*2*...*k and 0! = 1.

### Constraints

-i will be between 0 and 5000000 inclusive.
-d will be between 2 and 6 inclusive.

### Examples

0)

 `3` `3`
`Returns: 2`
 Row 3 is 1,3,3,1 so there are 2 elements divisible by 3.
1)

 `3` `4`
`Returns: 0`
 Row 3 has no elements that are divisible by 4.
2)

 `4` `2`
`Returns: 3`
 1,4,6,4,1 has 3 elements divisible by 2.
3)

 `4` `6`
`Returns: 1`
 Row 4 has a single element divisible by 6.
4)

 `0` `3`
`Returns: 0`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3564

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6519&pm=3564