Last Digits

Raising a number to repeated powers can produce a very large value.

You are given integers $b$, $n$, and $i$. The function $f$ is defined by

$f(x) = b^{f(x-1)} \quad (x > 0), \qquad f(0) = 1$

so $f(i)$ is a power tower of height $i$ with base $b$. Write a program that finds the last $n$ digits of $f(i)$.

The input consists of several test cases. Each test case consists of three lines: the first line contains $b$ ($1 \le b \le 100$), the second line contains $i$ ($1 \le i \le 100$), and the third line contains $n$ ($1 \le n \le 7$). A single line containing $0$ follows the last test case and marks the end of input.

For each test case, print the last $n$ digits of $f(i)$ on its own line. If $f(i)$ has fewer than $n$ digits, pad it with leading zeros so that exactly $n$ digits are printed.