Fie operaţia a n =a*a*...*a , produsul având n factori. Efectuând înmulţirile de la stânga la dreapta, se vor face n-1 înmulţiri. Numărul de înmulţiri necesar pentru a calcula a n este mult mai mic dacă folosim următoarele observaţii:

• a n = a * a n-1 , dacă n este impar.
• a n = ( a n/2)2 , dacă n este par.

Cerința

Se dau numerele naturale a n p. Calculați determinaţi numărul format din ultimele p cifre ale alui a n.

Date de intrare

Programul citește de la tastatură numerele a n p.

Date de ieșire

Programul va afișa pe ecran numărul X, valoarea cerută.

Restricții și precizări

• 1 ≤ a ≤ 1000
• 1 ≤ n ≤ 1.000.000.000
• 1 ≤ p ≤ 5

Exemplu

Intrare

2 16 3

Ieșire

536

Explicație

2 16 este 65536, iar numărul format din ultimele 3 cifre este 536.

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

int m, p, cif, i, nr;

int exp(int a, int n)
{
    if(n == 0) 
        return 1;
    if(n % 2 == 1)
    {
        long long tmp = exp(a, n - 1);
        tmp = tmp * a;
        return tmp % nr;
    }
    else
    {
        long long tmp = exp(a , n / 2);
        return (tmp * tmp) % nr;
    }
}


int main()
{
    cin >> m >> p >> cif;
    nr = 1;
    for(i=1;i<=cif;i++)
        nr = nr * 10;
    cout << exp(m, p);
    return 0;
}