Cei N2 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≤i,j≤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≤z≤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 N2-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)≠(p,q) şi 0≤i,j≤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•Pmax(z,i,j)) modulo Q).

Cerinţă

Fie S suma valorilor P(T+1,i,j) (0≤i,j≤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≤i,j≤N-1), modulo Q.

Restricţii

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

Exemple

v2d.in	v2d.out
3 10 10 1 2 3 4 5 6 7 8 9	2
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	24385

autor: Mugurel Ionuţ Andreica

propunător: Prof. Emanuela Cerchez

Liceul de Informatică ″Grigore Moisil″

emanuela.cerchez@gmail.com