Cho ba số nguyên dương M, N, K. Hãy tìm K chữ số cuối cùng của M^N.

Input

Ba số nguyên dương M, N, K. Điều kiện: 0 < K ≤ 9, 0 ≤ M, N ≤ 10⁶.

Output

K chữ số cuối cùng của M^N.

Ví dụ

Input

2 10 2

Output

24

Giải thích: 2¹⁰ = 1024, hai chữ số cuối là 24.