Competitions

# 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.

#### Input

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

#### Output

Print the amount of different numbers.

Input example #1

5 3 13 85 45

Output example #1

4