В предвкушении 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\) (см. формат вывода).
Выходные данные
Выведите вероятность того, что табличка окажется выигрышной, по модулю \(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}\).
Примечание
В первом примере любые два события образуют линию, поэтому табличка будет выигрышной, если произойдут любые два события. Вероятность этого равна \(\frac{11}{16}\), а \(5927 \cdot 16 \equiv 11 \pmod{31\,607}\).