F. Бинго
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В предвкушении VK Fest 2021 вы составили себе табличку из $$$n$$$ строк и $$$n$$$ столбцов, и в каждую ячейку этой таблички записали некоторое событие, связанное с фестивалем, которое может произойти или нет — например, удастся ли вам выиграть на фестивале приз, или пойдёт ли дождь.

Алгоритмы предсказания ВКонтакте уже оценили для каждого события вероятность того, что оно произойдёт. Событие в строке $$$i$$$ и столбце $$$j$$$ произойдёт с вероятностью $$$a_{i, j} \cdot 10^{-4}$$$. При этом все события совместно независимы друг от друга.

Назовём табличку с событиями выигрышной, если найдётся такая линия, на которой произойдут все $$$n$$$ событий. Линией считается любая горизонталь (ячейки $$$(i, 1), (i, 2), \ldots, (i, n)$$$ для некоторого $$$i$$$), любая вертикаль (ячейки $$$(1, j), (2, j), \ldots, (n, j)$$$ для некоторого $$$j$$$), главная диагональ (ячейки $$$(1, 1), (2, 2), \ldots, (n, n)$$$) и побочная диагональ (ячейки $$$(1, n), (2, n - 1), \ldots, (n, 1)$$$).

Определите вероятность того, что ваша табличка окажется выигрышной, и выведите её по модулю $$$31\,607$$$ (см. формат вывода).

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

В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 21$$$) — длина стороны таблички.

В $$$i$$$-й из следующих $$$n$$$ строк задано $$$n$$$ целых чисел $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$ ($$$0 < a_{i, j} < 10^4$$$). Вероятность того, что событие в ячейке таблицы $$$(i, j)$$$ произойдёт, равна $$$a_{i, j} \cdot 10^{-4}$$$.

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

Выведите вероятность того, что табличка окажется выигрышной, по модулю $$$31\,607$$$.

Формально, пусть $$$M = 31\,607$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

Примеры
Входные данные
2
5000 5000
5000 5000
Выходные данные
5927
Входные данные
2
2500 6000
3000 4000
Выходные данные
24812
Входные данные
3
1000 2000 3000
4000 5000 6000
7000 8000 9000
Выходные данные
25267
Примечание

В первом примере любые два события образуют линию, поэтому табличка будет выигрышной, если произойдут любые два события. Вероятность этого равна $$$\frac{11}{16}$$$, а $$$5927 \cdot 16 \equiv 11 \pmod{31\,607}$$$.