Cerința

Șirul lui Fibonacci este definit astfel:

$$F_n = \begin{cases} 1& \text{dacă } n = 1 \text{ sau } n = 2 ,\\ F_{n-1} + F_{n-2} & \text{dacă } n > 2. \end{cases}$$

Se dă un număr natural n. Determinați al n-lea termen al șirului, modulo 666013.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran numărul F, reprezentând al n-lea termen al șirului, modulo 666013.

Restricții și precizări

• 1 ≤ n ≤ 2.000.000.000

Exemplu

Intrare

6

Ieșire

8

Explicație

Termenii sunt: 1 1 2 3 5 8 13 21 34 55 89 ...

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

#define MOD 666013

void produs(long long P[][2] , long long A[][2] , long long B[][2])
{
    P[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
    P[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
    P[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
    P[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD;
}

void copiere(long long A[][2] , long long B[][2])
{
    for(int i = 0 ; i <= 1 ; i++)
        for(int j = 0 ; j <= 1 ; j++)
            A[i][j] = B[i][j];
}

int fibo(int n)
{
    long long A[2][2] = {{1 , 1} , {1 , 0}} , P[2][2] = {{1 , 0} , {0 , 1}} , B[2][2];
    while(n > 0)
    {
        if(n % 2 == 1)
        {
            produs(B , A , P);
            copiere(P , B);
        }
        produs(B , A , A);
        copiere(A , B);
        n /= 2;
    }
    return P[0][1];
}

int main()
{
    int n;
    cin >> n;
    cout << fibo(n);
    return 0;
}