Se dau numerele naturale b n p. Determinați numărul format din ultimele p cifre ale lui bn.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran numărul format din ultimele p cifre ale lui bn.

Restricții și precizări

• 1 ≤ b ≤ 1000000
• 1 ≤ n < 231
• 1 ≤ p ≤ 9

Exemplu

Intrare

2 10 2

Ieșire

24

Explicație

210=1024. Numărul format din ultimele 2 cifre ale lui 1024 este 24.

Citim numere b n p și calculăm M=10p.

Vom determina rezultatul folosind exponențierea rapidă:

Să considerăm A25. Să-l scriem pe 25 ca sumă de puteri ale lui 2 (orice număr natural poate fi scris ca sumă de puteri ale lui 2 într-un singur mod): 25=1+8+16.
Atunci  A25=A1+8+16=A1⋅A8⋅A16

#include <bits/stdc++.h>

using namespace std;
int p,p10,n,b;
long long mod(long long baza,long long exp)
{
    if(exp==0)return 1;
    if(exp==1)return baza;
    long long rez=mod(baza,exp/2)%p10;
    if(exp%2==1)
    {
        return (((rez*rez)%p10)*baza)%p10;
    }
    return(rez*rez)%p10;
}
long long rid(long long baza,long long exp)
{
    if(exp==0)return 1;
    if(exp==1)return baza;
    long long rez=rid(baza,exp/2);
    if(exp%2==1)
    {
        return rez*rez*baza;
    }
    return rez*rez;
}
int main()
{
    cin>>b>>n>>p;
    p10=rid(10,p);
    cout<<mod(b,n)%p10;
    return 0;
}