Permutation Divisibility

Given a numeric string \(s\) and a positive integer \(d\), count the number of distinct permutations of \(s\) (permutations may have leading zeros) that are divisible by \(d\). In other words, if you form a number by rearranging the digits of \(s\), how many different arrangements yield a number that satisfies

[ N \equiv 0 \pmod{d} ]

For example, for \(s = 123434\) and \(d = 2\), there are 90 distinct permutations that are divisible by 2. Among them, 30 permutations end with 2 and 60 permutations end with 4.

inputFormat

The input consists of two lines:

1. The first line contains the numeric string \(s\) (which may contain leading zeros).
2. The second line contains the positive integer \(d\).

outputFormat

Output a single integer representing the number of distinct permutations of \(s\) that are divisible by \(d\).

sample

123434
2

90