### Problem Statement

We define a permutation of an integer N as an integer that has the exact same digits as N, but possibly in a different order. Two permutations of N are considered different if the numbers they represent are not the same. For example, the set of all different permutations of the number N = 313 is {133, 313, 331}.

Given a String N and an int M, determine the number of different permutations of N that are divisible by M.

### Definition

 Class: DivisiblePermutations Method: count Parameters: String, int Returns: long Method signature: long count(String N, int M) (be sure your method is public)

### Constraints

-N will contain between 1 and 15 non-zero digits ('1'-'9'), inclusive.
-M will be between 1 and 50, inclusive.

### Examples

0)

 `"133"` `7`
`Returns: 1`
 There are three permutations of 133 (133, 313, 331), but only 133 is divisible by 7.
1)

 `"2753"` `5`
`Returns: 6`
 The permutations of 2753 that are divisible by 5 are 2375, 2735, 3275, 3725, 7235 and 7325.
2)

 `"1112225"` `5`
`Returns: 20`
3)

 `"123456789"` `17`
`Returns: 21271`
4)

 `"987654321999999"` `39`
`Returns: 19960896`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8076&pm=4838

Andrew_Lazarev

#### Testers:

PabloGilberto , brett1479 , Olexiy

#### Problem categories:

Dynamic Programming