Простий збіг

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

Вхідні дані

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

Вихідні дані

Виведіть кількість способів вибрати перестановку циклічних зсувів, щоб їх конкатенація ділилася на p. Відповідь виведіть за модулем 1000000007.

Приклади