Василько на смужці паперу написав число, кратне d. Його менший брат Дмитрик розрізав число на k частин. Пам’ятаючи тільки число d, Василько вирішив відновити написане число, але стикнувся з проблемою, що чисел, кратних d можна скласти декілька.

Скільки чисел, кратних d, може створити Василько, якщо складаючи число він має використати усі частини.

Вхідні дані

Перший рядок містить два числа d та k (1 ≤ k < 9, 1 ≤ d ≤ 100). Далі в k рядках знаходяться частини числа. Кількість цифр у розрізаних частинах не превищує 10.

Вихідні дані

Кількість різних чисел.