Василий на бумажке в виде полоски написал число, кратное d. Его младший брат Дмитрий разрезал число на k частей. Василий решил восстановить написанное число, но столкнулся с проблемой. Он помнил только число d, а чисел, кратных d, можно сложить несколько.
Сколько чисел, кратных числу d, может составить Василий, если составляя исходное число, он использует все части.
Входные данные
В первой строке записано два числа d и k (1 ≤ k < 9, 1 ≤ d ≤ 100). В следующих k строках находятся части числа. Количество цифр в разрезанных частях не превышает 10.
Выходные данные
Количество разных чисел.
Пример входных данных5 313 85 45 |
Пример выходных данных4 |