Se consideră un șir de numere naturale a[1], a[2], …, a[n].

Cerința

Să se determine numărul tripletelor (a[i], a[j], a[p]) cu i < j < p, iar a[i] + a[j] + a[p] este divizibil cu 5.

Date de intrare

Programul citește de la tastatură numerele n, w, X, Y, Z. Șirul de n numere se generează după relațiile: a[1] = w, a[i] = (X * a[i-1] + Y) % Z;

Date de ieșire

Programul va afișa pe ecran numărul tripletelor cu suma divizibilă cu 5.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ w, X, Y, Z ≤ 1.000.000.000

Exemplu

Intrare

10 1 7 223 17

Ieșire

24

#include <bits/stdc++.h>

using namespace std;
long long a[20];
long long  Comb(long long n, long long k)
{
    if (n < k)return 0;
    long long  rez = 1;
    for (long long i = n - k + 1; i <= n; i ++) rez *= i;
    for (long long i = 1; i <= k; i ++) rez /= i;
    return rez;
}
int main()
{
    long long n, w, x, y, z, rez = 0;
    cin >> n >> w >> x >> y >> z;
    a[w % 5] ++;
    for (int i = 2; i <= n; i ++)
    {
        w = (w *x + y) % z;
        a[w % 5] ++;
    }
    for (int i = 0; i < 5; i ++)
        for (int j = i; j < 5; j ++)
        {
            if (i == 0 && j == 0) rez += Comb(a[0], 3);
            else
            {
                int k = (5 - (i + j) % 5) % 5;
                if (k >= j)
                {
                    if (i == j)rez += Comb(a[j], 2) * a[k];
                    else if (j == k)rez += Comb(a[j], 2) * a[i];
                    else rez += a[i] * a[j] * a[k];
                }
            }
        }
    cout << rez;
    return 0;
}