favorite We need a little bit of your help to keep things running, click on this banner to learn more

ADA University - February 9

The cut number

Vasylko wrote a number which is multiple of d on a scrap of paper. His smaller brother Dmitri cut the number into k parts. Vasylko decided to restore the number that 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 must use all parts to make a number.


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


Print the amount of different numbers.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 3
Output example #1