Tìm ~K~ chữ số cuối cùng của ~M^N\ (0< K ≤ 9, 0 < M, N ≤ 10^6)~.

Ví dụ: ~K=2, M=2, N=10~, ta có ~2^{10}=1024~, như vậy ~2~ chữ số cuối cùng của ~2^{10}~ là ~24~.

Input

• Một dòng duy nhất chứa ba số nguyên dương ~K, M, N~.

Output

• Một dòng duy nhất chứa đáp số bài toán.

Sample

Input #1

2 2 10

Output #1

24

Input #2

5 2 10

Output #2

01024

Problem source: Chuyên Sơn La Online Judge