描述

一个整数对另一个整数进行幂运算时，结果往往会非常大。在本题中，我们将基于重复幂运算来计算一个函数，但仅输出结果的最后 n 位数字。为了高效实现这一要求，需要仔细考虑如何避免计算出整个大数。

给定整数 b、n 和 i，我们用以下递归关系定义函数 f(x)：

• 当 x > 0 时，f(x) = b ^ f(x-1)（即 b 的 f(x-1) 次幂）
• 当 x = 0 时，f(0) = 1

你的任务是高效地计算出 f(i) 的最后 n 位十进制数字。

输入

输入由多个测试用例组成。每个测试用例的格式如下：

• 第一行给出整数 b（1 ≤ b ≤ 100），即底数；
• 第二行给出整数 i（1 ≤ i ≤ 100），即迭代次数；
• 第三行给出整数 n（1 ≤ n ≤ 7），即要求输出的十进制位数。

当 b = 0 时，表示输入结束。

输出

对于每个测试用例，在一行内输出 f(i) 的最后 n 位数字。若结果位数不足 n 位，则在左侧补零，使得输出恰好为 n 位数字。

2
4
7
10
10
6
3
10
7
0

0065536
000000
4195387

题目来源
Rocky Mountain 2005