Задачи
Простое совпадение
Простое совпадение
Пусть \textbf{p} - простое число. Дано \textbf{p} цифровых строк длиной \textbf{p-1}. Разрешается брать любой циклический сдвиг каждой строки и менять строки местами. После чего все их конкатенировать в одну строку, возможно с ведущими нулями, - некоторое число. Найдите количество способов выбрать такой порядок циклических сдвигов, чтобы результирующее число делилось на \textbf{p}.
\InputFile
В первой строке простое число \textbf{p} (\textbf{2} ≤ \textbf{p} ≤ \textbf{23}). Далее \textbf{p} строк по \textbf{p-1} символ каждая, возможно с ведущими нулями. Все строки состоят только из цифр.
\OutputFile
Количество способов выбрать некоторую перестановку циклических сдвигов, чтобы их конкатенция делилась на \textbf{p}. Ответ вывести по модулю \textbf{1000000007}.
Входные данные #1
3 11 76 39
Выходные данные #1
48