Cerința

Se dă un șir V. Știind V0 = 3 și regula de formare a șirului:

Vi = ([ Vi-1 * Vi-1 / (i + 2)] + V i-1 * i + i + 1) % 666013.

să se determine al n-lea termen al șirului. (unde [x] reprezintă partea întreagă a numărului x)

Date de intrare

Fișierul de intrare smen.in conține numărul n.

Date de ieșire

Fișierul de ieșire smen.out va conține al n-lea termen al șirului.

Restricții și precizări

• 1 ≤ n ≤ 20.000.000
• Atenție la limitele de timp și de memorie!

Exemple:

smen.in

10000000

smen.out

22230

#include <bits/stdc++.h>
using namespace std;
ifstream cin("smen.in");
ofstream cout("smen.out");
int main()
{
    unsigned long long n , a = 0 , b;
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        b = ( a * a / (i + 2) +  a * i + i + 1) % 666013;
        a = b;
        if(i!=n) b = 0;
    }
    cout << b << ' ';
}