Gazda Srba ima voćnjak šljiva u srcu Šumadije. Kako je Srba veliki perfekcionista, on svoj šljivik održava uvek u formi pravougaonika, tako da u svakom od ukupno N redova šljivika bude tačno po M stabala šljiva. Na svakom stablu se nalaze plodovi, čiji broj gazda Srba uredno kontroliše.

Srba je i ponosni otac K dece, koja obožavaju šljive, i da bi ih obradovao, rešio je da za svako dete nabere isti broj šljiva. Međutim, pošto kao i obično želi da sve bude "pod konac", gazda Srba će odabrati deo voćnjaka koji će takođe biti u obliku pravougaonika, čije su stranice paralelne stranicama voćnjaka, ali tako da, kad sa tog dela nabere sve šljive, on može sve da ih podeli svojoj deci tako da svako od njih dobije isti broj šljiva.

Odrediti na koliko načina gazda Srba može da odabere deo šljivika koji će da obere.

Ulaz:

(Ulazni podaci se nalaze u datoteci sljivik.in.) U ulaznoj datoteci se u prvom redu nalaze tri broja N, M i K (1 ≤ N, M ≤ 250, 1 ≤ K ≤ 1.000.000), broj redova i kolona Srbinog voćnjaka i broj Srbine dece, respektivno. U sledećih N redova se nalaze po M brojeva iz intervala [1, 10⁹] koji predstavljaju broj plodova na svakom od stabala.

Izlaz:

(Izlazne podatke upisati u datoteku sljivik.out) U prvom i jedinom redu izlazne datoteke ispisati broj različitih načina da gazda Srba odabere deo šljivika koji će da obere.

Primer:

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

4

Objašnjenje.

Rešenja su ovi pravougaonici (prva dva broja su koordinate gornjeg levog ugla, a druga dva koordinate donjeg desnog ugla pravougaonika sa kojeg će Srba da bere šljive): (1,1)-(3,3) , (2,1)-(2,1) , (3,1)-(3,2) , (2,2)-(3,3).

#include <algorithm>
#include <cstdio>
#include <cstdlib>

using namespace std;

int z[1000555],br[1000555],a[555][555],s[555][555];

int main() {

    freopen("sljivik.in", "r", stdin);
    freopen("sljivik.out", "w", stdout);

    int n,m,k,i,j,e,t,op,r1,r2,i2,j2,tt;
    long long res,res2;

    scanf("%d%d%d", &n, &m, &k);

    for(i=0; i<=max(n,m); i++) s[0][i] = 0;

    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {

            scanf("%d", &a[i][j]);
            s[i][j] = (a[i][j] + s[i-1][j]) % k;
        }
    }

    for(i=0; i<=k; i++) {
        z[i] = 0;
        br[i] = 0;
    }

    op = 0; res = 0;
    for(r1=1; r1<=n; r1++) {
        for(r2=r1; r2<=n; r2++) {
            op++;
            t = 0;
            z[0] = op;
            br[0] = 1;
            for(i=1; i<=m; i++) {
                e = s[r2][i] - s[r1-1][i];
                if (e < 0) e = k + e;
                t = (t + e) % k;

                if (z[t] == op) {
                    res += br[t];
                    br[t]++;
                } else {
                    z[t] = op;
                    br[t] = 1;
                }
            }
        }
    }

    printf("%I64lld\n", res);

    // O(N^4) Resenje

    //for(i=0; i<=max(n,m); i++) { s[i][0] = 0; s[0][i] = 0; }

    //res2 = 0;
    //for(i=1; i<=n; i++) {
    //    for(j=1; j<=m; j++) {
    //        s[i][j] = (a[i][j] + s[i][j-1] + s[i-1][j] - s[i-1][j-1]) % k;
    //        for(i2=1; i2<=i; i2++) {
    //            for(j2=1; j2<=j; j2++) {
    //                t = (s[i][j] - s[i2-1][j] - s[i][j2-1] + s[i2-1][j2-1]) % k;
    //                if (t == 0) {
    //                    res2++;
    //                    //printf("%d %d - %d %d\n", i2, j2, i, j);
    //                }
    //            }
    //        }
    //    }
    //}

    //printf("%I64lld\n", res2);

    return 0;
}