# The cut number

Easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

Vasylko wrote a number which is multiple of d on a scrap of paper. His smaller brother Dmytro 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

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, divisible by d.

## Examples

Input #1

Answer #1

Submissions 2K

Acceptance rate 23%