The cut number#50
Vasyl wrote a number that is a multiple of on a strip of paper. His younger brother Dmytro cut this number into parts. Vasyl wants to restore the number, but he remembers only , and there may be several ways to combine all the parts to form a multiple of .
How many different numbers that are multiples of can Vasyl form using all the parts exactly once, possibly in any order?
The first line contains two integers and (1 \leq k < 9, 1 \leq d \leq 100).Each of the next lines contains a part of the number. The number of digits in each part does not exceed .
Print the number of different numbers that are multiples of and can be formed by concatenating all the parts in any order, using each part exactly once.
Example 1