Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

F. Особые матрицы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Квадратная матрица n × n называется особой, если:

  • она бинарная, то есть в каждой ячейке стоит либо 0, либо 1;
  • количество единиц в каждой строке и каждом столбце равно 2.

Вам заданы n и первые m строк матрицы. Выведите количество особых матриц n × n таких, первые m строк которых совпадают с заданными.

Так как искомое значение может быть очень большим, то выведите остаток от деления значения на заданное число mod.

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

Первая строка входных данных содержит три целых чисел n, m, mod (2 ≤ n ≤ 500, 0 ≤ m ≤ n, 2 ≤ mod ≤ 109). Далее идут m строк по n символов в каждой из них — первые строки искомых особых матриц. В каждой из этих строк ровно два символа '1' и все остальные символы — '0'. В каждом столбце заданной m × n таблицы не более двух единиц.

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

Выведите остаток при делении искомого количества на число mod.

Примеры
Входные данные
3 1 1000
011
Выходные данные
2
Входные данные
4 4 100500
0110
1010
0101
1001
Выходные данные
1
Примечание

Для первого теста искомые матрицы: 


011
101
110

011
110
101

Во втором тесте особая матрица уже задана полностью, поэтому ответ 1.