Квадратная матрица n × n называется особой, если:
- она бинарная, то есть в каждой ячейке стоит либо 0, либо 1;
- количество единиц в каждой строке и каждом столбце равно 2.
Вам заданы n и первые m строк матрицы. Выведите количество особых матриц n × n таких, первые m строк которых совпадают с заданными.
Так как искомое значение может быть очень большим, то выведите остаток от деления значения на заданное число mod.
Выходные данные
Выведите остаток при делении искомого количества на число mod.
Примечание
Для первого теста искомые матрицы:
011
101
110
011
110
101
Во втором тесте особая матрица уже задана полностью, поэтому ответ 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 1000
011
|
2
|
|
2
|
4 4 100500
0110
1010
0101
1001
|
1
|