为 2021 年 VK Fest 做准备,您准备了一张包含 $$$n$$$ 行和 $$$n$$$ 列的表格,并在该表格的每个单元格中填写了一些与节日相关的可能发生或不发生的事件:例如,您是否会在节日上赢得奖品,或者是否会下雨。
Forecasting algorithms used in VK have already estimated the probability for each event to happen. $$$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$$$) — 表格的尺寸。
接下来的 $$$n$$$ 行的第 $$$i$$$ 包含 $$$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}$$$。
示例
输入 #1
2 5000 5000 5000 5000
输出 #1
5927
输入 #2
2 2500 6000 3000 4000
输出 #2
24812
输入 #3
3 1000 2000 3000 4000 5000 6000 7000 8000 9000
输出 #3
25267
注意
在第一个示例中,任意两个事件形成一条线,如果任意两个事件发生,则该表获胜。其概率为 $$$\frac{11}{16}$$$ 和 $$$5927 \cdot 16 \equiv 11 \pmod{31\,607}$$$。