v2d

Cei $N^2$ vrăjitori de la Universitatea Nevăzută îşi au birourile într-o matrice pătratică având latura egală cu $N$. În fiecare celulă $(i, j)$ a matricei $(0 \leq i, j \leq N - 1)$ se află biroul unui vrăjitor. În continuare vom identifica vrăjitorii prin coordonatele biroului lor. Vrăjitorii se află în conflict permanent, deoarece fiecare vrea să ocupe poziţia de Arhicancelar al universităţii. Acest conflict se desfăşoară pe parcursul a $T$ zile (numerotate de la $1$ la $T$).

În fiecare zi $z \ (1 \leq z \leq T)$, fiecare vrăjitor $(i, j)$ are o putere de atac $P(z, i, j)$. Un vrăjitor $(i, j)$ atacă toţi ceilalţi $N^2 - 1$ vrăjitori, iar puterea cu care vrăjitorul $(i, j)$ atacă un vrăjitor $(p, q)$ în ziua $z$ este $PA(z, i, j, p, q) = P(z, i, j) - dist(i, j, p, q)$. $dist(i, j, p, q)$ reprezintă distanţa dintre vrăjitorii $(i, j)$ şi $(p, q)$, şi este definită ca $|i - p| + |j - q|$. Efectul atacurilor resimţit de un vrăjitor $(p, q)$ în ziua z este $Pmax(z, p, q) = max \{PA(z, i, j, p, q) | (i, j) \neq (p, q)$ şi $0 \leq i, j \leq N - 1 \}$.

Puterea de atac a unui vrăjitor $(i, j)$ în ziua $z+1$ va fi: $P(z+1, i, j) = z + 1 + ((P(z, i, j) + z \cdot Pmax(z, i, j))$ modulo $Q)$.

Cerinţă

Fie $S$ suma valorilor $P(T+1, i, j), (0 \leq i,j \leq N-1)$. Determinaţi valoarea ($S$ modulo $Q$).

Date de intrare

Prima linie a fişierului de intrare v2d.in conţine numerele naturale $N$, $T$ şi $Q$, separate prin câte un spaţiu. Următoarele $N$ linii conţin valorile puterilor de atac ale vrăjitorilor la începutul zilei $1$. Fiecare dintre aceste linii conţine $N$ numere naturale, separate prin spaţii. Al $C$-lea număr $(1 ≤ C ≤ N)$ de pe a $L$-a $(1 ≤ L ≤ N)$ dintre aceste linii reprezintă valoarea $P(1, L - 1, C - 1)$.

Date de ieșire

În fişierul de ieşire v2d.out veţi afişa suma valorilor $P(T + 1, i, j)$, $(0 \leq i, j \leq N - 1)$, modulo $Q$.

Restricții și precizări

• $2 \leq N \leq 500$
• $1 \leq T \leq 50$
• $2 \leq Q \leq 30 \ 000$
• $1 \leq P(1, i, j) \leq Q + T$

Exemplul 1

v2d.in

3 10 10
1 2 3
4 5 6
7 8 9

v2d.out

2

Exemplul 2

v2d.in

5 50 30000
1000 900 800 700 30050
900 800 700 600 1000
800 700 600 1000 900
700 600 1000 900 800
600 1000 900 800 700

v2d.out

24385