true DIVIDE ET IMPERA

#include <iostream>

using namespace std;



long long calc2(long long a, long long b)
{
    long long p=1;
    for(int i=0; i<b; i++)
    {
        p*=a;
        p%=668543;
    }
    return p;
}


long long calc(long long a, long long b)
{
    if (b==0) return 1;
    long long valoare = calc(a,b/2);
    if (b%2==0) return (valoare*valoare)%668543;
    else return (((valoare*valoare)%668543)*a)%668543;

}


int main()
{
    long long a, b;
    a = 123;
    b = 2000000000;
    // a ^ b % 668543;
    cout << calc(a,b);

    return 0;
}