Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM-ICPC亚洲区预选赛(北京赛区)游戏对抗邀请赛​正在报名中

Language:
Last Digits
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2160 Accepted: 453

Description

Exponentiation of one integer by another often produces very large results. In this problem, we will compute a function based on repeated exponentiation, but output only the last n digits of the result. Doing this efficiently requires careful thought about how to avoid computing the full answer.

Given integers b, n, and i, we define the function f(x) recursively by f(x) = bf(x-1) if x > 0, and f(0)=1. Your job is to efficiently compute the last n decimal digits of f(i).

Input

The input consists of a number of test cases. Each test case starts with the integer b (1 <= b <= 100) called the base. On the next line is the integer i (1 <= i <= 100) called the iteration count. And finally, the last line contains the number n (1 <= n <= 7), which is the number of decimal digits to output. The input is terminated when b = 0.

Output

For each test case, print on one line the last n digits of f(i) for the base b specified. If the result has fewer than n digits, pad the result with zeroes on the left so that there are exactly n digits.

Sample Input

```2
4
7
10
10
6
3
10
7
0
```

Sample Output

```0065536
000000
4195387
```

Source

[Submit]   [Go Back]   [Status]   [Discuss]