Se dă o matrice pătratică de n x n numere naturale și o valoare naturală T. Suma unei submatrice este suma elementelor submatricei.

Cerința

Să se determine numărul submatricelor care au suma mai mică sau egală cu T.

Date de intrare

Programul citește de la tastatură, în această ordine, numerele T n A B C D. Elementele matricei se vor genera după formula: a[i,j] = (A * i + B * j + C) % D.

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând numărul submatricelor de sumă mai mică sau egală cu T.

Restricții și precizări

• 1 ≤ n, A, B, C, D ≤ 400
• 1 ≤ T ≤ 30.000
• O submatrice poate fi formată dintr-un singur element (este o submatrice cu o linie și o coloană).

Exemplu

Intrare

10 2 1 1 1 43

Ieșire

8

Explicație

Matricea generată este:
3 4
4 5
Singura submatrice care nu are suma mai mică sau egală cu T este doar matricea întreagă.

#include <bits/stdc++.h>

using namespace std;

int A[502][502] , n , t , a , b , c , d , x[502];
long long cnt;

int main()
{
    cin >> t >> n >> a >> b >> c >> d;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
        {
            A[i][j] = (a * i + b * j + c) % d;
            A[i][j] += A[i - 1][j];
        }

    for(int x1 = 1 ; x1 <= n ; x1++)
        for(int x2 = x1 ; x2 <= n ; x2++)
        {
            for(int i = 1 ; i <= n ; i++)
                x[i] = A[x2][i] - A[x1 - 1][i];
            int st = 1 , sp = 0;
            for(int i = 1 ; i <= n ; i++)
            {
                sp += x[i];
                while(sp > t)
                {
                    sp -= x[st];
                    st++;
                }
                cnt += i - st + 1;
            }
        }
        cout << cnt;
}