Простое совпадение

Пусть p - простое число. Дано p цифровых строк длиной p-1. Разрешается брать любой циклический сдвиг каждой строки и менять строки местами. После чего все их конкатенировать в одну строку, возможно с ведущими нулями, - некоторое число. Найдите количество способов выбрать такой порядок циклических сдвигов, чтобы результирующее число делилось на p.

Входные данные

В первой строке простое число p (2 ≤ p ≤ 23). Далее p строк по p-1 символ каждая, возможно с ведущими нулями. Все строки состоят только из цифр.

Выходные данные

Количество способов выбрать некоторую перестановку циклических сдвигов, чтобы их конкатенция делилась на p. Ответ вывести по модулю 1000000007.

Примеры