Background

Description

幂的末尾（保留尾数是输入值） 输入a,b和c，都是正整数 幂![a^{b}]的末c位数是多少？

Format

Input

三个正整数a，b。1 <= a <= 100，1 <= b <= 10000，1<=c<=9。

Output

从高位到低位输出幂的末c位数字，中间无[分隔符]。若幂本身不足c位，在前面补零。

Samples

7
2011
5

26743

9
123
6

971929

15
259
3

375

Limitation

1s, 1024KiB for each test case.