D - Jouley

Cerință

După ce te-ai enervat că ai nevoie de $O(N^3)$ operații să înmulțești $2$ matrici te-ai gândit să faci următorul algoritm de înmulțirea matricilor:

Doua matrici de $N$ x $N$ se înmulțesc rotind a doua matrice în sensul acelor de ceasornic $90$ de grade. Iar apoi element cu element rezultatul din căsuța $(i,j)$ este egal cu produsul elementelor din cele două matrici pe pozițile $(i,j)$ plus suma lor.
Formal, dacă avem $A \cdot B = M$ iar $C$ este matricea $B$ rotită $90$ de grade la dreapta, atunci $M_{i,j} = A_{i,j} \cdot C_{i,j} + A_{i,j} + C_{i,j}$.

Se dă o matrice $M$, câte perechi de matrici $(A, B)$, cu elemente naturale, există cu proprietatea că $A \cdot B = M$ ?
Răspunsul este foarte mare astfel se va afișa restul rezultatulului prin împărțirea cu $998244353$.

Date de intrare

Pe prima linie se află $N$, după care matricea $M$.

Date de ieșire

Numărul de perechi de matrici cerut modulo $998244353$.

Restricții și precizări

• $1 \leq N \leq 1000$
• $0 \leq M_{i,j} \leq 10^6$

Exemplul 1

stdin

2
0 0
0 1

stdout

2

Explicație

O pereche e:

A=$\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$

și

B=$\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$

Matricea $B$ rotită și compusă cu $A$ cum scrie în enunț face chiar matricea din input.

Cealaltă pereche este:

A=$\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$

și

B=$\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$

Exemplul 2

stdin

4
8 12 54 1
43 34 1 32
0 0 123 34
101 64 72 10

stdout

28311552