Cerința

Exact așa cum spuneam Alex e un băiat năzdrăvan! De data aceasta boacăna pe care a făcut-o l-a determinat pe profesorul de informatică să îi spună că nu va mai fi iertat și pentru această boacănă așa că îi dă de ales ori îl va asculta doar pe el și restul copiilor vor scăpa ori va dă test tuturor din clasă. Alex este conștient că nu trebuie să fie pedepsiți toți pentru greșeala lui așa ca decide ca doar el trebuie să răspundă! Profesorul complet degajat îi da problema:

Se dau două șiruri de câte n valori notate A și B. Pentru fiecare pereche $A_i B_i$ se calculează resturile împărțirii la 6669666 a lui ${A_i}^{B_i}$. Ajutați-l pe Alex să determine suma acestor resturi.

Date de intrare

Fișierul de intrare test.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații reprezentând elementele șirului A și apoi pe următoarea linie n numere naturale reprezentând elementele șirului B.

Date de ieșire

Fișierul de ieșire test.out va conține pe prima linie numărul S, reprezentând rezultatul suma cerută.

Restricții și precizări

• 1 ≤ n ≤ 1000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 4.294.967.296
• desigur că dacă îl veți ajuta Alex vă va răsplăti cu o bere sau cu un suc în funcție de vârstă

Exemplu

test.in

5
2 3 4 5 6
1 2 3 4 5

test.out

8476

Explicație

S-a calculat 21+32+43+54+65=8476.

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

ifstream cin("test.in");
ofstream cout ("test.out");

long long putere(long long a , long long p , int mod)
{
    if(p == 0) return 1;
    else
    {
       long long x = putere(a , p / 2 , mod);
       if(p % 2 == 0) return x * x % mod;
       else return x * x % mod * a % mod;
    }
}

int main()
{
    unsigned long long a[1005],b[1005] , s = 0;
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];
    for(int i = 1 ; i <= n ; i++) cin >> b[i];
    for(int i = 1 ; i <= n ; i++) s += putere(a[i],b[i] , 6669666);
    cout << s;
}