Униз кролячою норою#715
Аліса побігла за білим кроликом із червоними очима у кролячу нору, не задумуючись, як повертатиметься. Спочатку нора була схожа на тунель, а потім раптово різко пішла вниз. Аліса летіла, наче в глибоку криницю. Чи була криниця дуже глибока, чи падала вона дуже повільно — часу подумати й поміркувати про те, що попереду, було вдосталь.
Стіни криниці були вкриті числами, і Аліса почала складати з цих цифр -значні числа, кожне з яких вона поділила на своє улюблене число . Дивно, але всі ці числа ділилися на без остачі.
— Цікаво, скільки ж таких чисел існує? — промовила Аліса вголос. — Чи не доведеться мені рахувати їх, поки я падатиму крізь всю Землю? Оце було б смішно! Вибираюсь нагору — а там усі догори ногами! Як їх звати?.. Антипатії, здається...
Спробуйте визначити, скільки існує таких чисел... Оскільки ця кількість може бути дуже великою, дайте відповідь по модулю 1{,}000{,}000{,}007.
У першому рядку вхідного файлу задано числа , і , де — кількість різних цифр на стінах криниці (K \leq 10). У другому рядку перелічено різних цифр. Число не перевищує , а число не перевищує . Усі числа у файлі — невід'ємні цілі.
Виведіть одне число — відповідь до задачі. При складанні чисел кожну з поданих цифр можна використовувати скільки завгодно разів. Число повинно містити рівно цифр, причому перша цифра не має бути .
Приклад 1