RXD and numbers

Problem Description

RXD has a sequence $A_1,A_2,A_3,\dots A_n$, which possesses the following properties:

• $1\leq A_i\leq m$
• $A_1 = A_n = 1$
• for all $1\leq x\leq m$, there is at least one position $p$ where $A_p = x$.
• for all $x, y$, the number of $i(1 \leq i < n)$ which satisfies $A_i = x ~ and ~ A_{i + 1} = y$ is $D_{x, y}$. One day, naughty boy DXR clear the sequence. RXD wants to know, how many valid sequences are there. Output the answer module $998244353$. $0\leq D_{i, j}<500,1\leq m\leq 400$ $n \geq 2$

Input

There are several test cases, please keep reading until EOF. There are about 10 test cases, but only 1 of them satisfies $m > 50$ For each test case, the first line consists of 1 integer $m$, which means the range of the numbers in sequence. For the next $m$ lines, in the $i$-th line, it consists of $m$ integers, the $j$-th integer means $D_{i, j}$. We can easily conclude that $n = 1 + \sum_{i = 1}^{m}\sum_{j = 1}^{m}{D_{i, j}}$.

Output

For each test case, output "Case #x: y", which means the test case number and the answer.

Sample Input

2

1 2

2 1

4

1 0 0 2

0 3 0 1

2 1 0 0

0 0 3 1

4

0 1 0 0

1 0 0 0

0 0 0 1

0 0 1 0

Sample Output

Case #1: 6

Case #2: 18

Case #3: 0

Source

2017 Multi-University Training Contest - Team 3

https://acm.hdu.edu.cn/showproblem.php?pid=6064