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.