Vasylko wrote a number which is multiple of d on a scrap of paper. His smaller brother Dmytryk cut the number to k parts. Vasylko decided to restore the number, which he wrote. He remembered only number d. But there was a problem. It is possible to make many numbers which are multiple of d.

   How many numbers multiple of d can make Vasylko? He uses all parts when he make a number.

   Input

   The first line contains two integers d and k (1 ≤ k < 9, 1 ≤ d ≤ 100). The parts of the number lie in the next k lines. The number of digits in each part does not exceed 10.

   Output

   Print the amount of different numbers.