Cerința

Fiind dat N, un număr natural nenul, calculați suma $S=1^{2}+2^{2}+3^{2}+\cdots+N^{2}$, modulo 10.234.573.

Date de intrare

Programul citește de la tastatură numărul N.

Date de ieșire

Programul va afișa pe ecran numărul S, modulo 10.234.573.

Restricții și precizări

• 1 ≤ N ≤ 2.000.000.000

#include <bits/stdc++.h>
using namespace std;

int main()
{
    /// S = n * (n + 1) * (2 * n + 1) / 6

    int MOD = 10234573;
    int n;
    cin >> n;
    long long a, b, c;
    a = n;
    b = n + 1;
    c = 1LL * 2 * n;
    c += 1;

    if(a % 2 == 0)
        a/=2;
    else
        b/=2;

    if(a % 3 == 0)
        a /= 3;
    else if(b % 3 == 0)
        b /= 3;
    else
        c /= 3;

    cout << a % MOD * b % MOD * c % MOD;

    return 0;
}