A famous Byteotia game theory specialist, Baj Tash, invented a very interesting game. The game board consists of some number of cells arranged in a straight line. Initially, there is one token on each cell. There are two kinds of tokens: blue and red.

The players have several patterns available, each made of blue and red tokens. The players move alternately. On each move, a player may take from the board a group of tokens arranged exactly as in one of the patterns (both the token colors and their relative positions must match; however, the pattern may be scaled and reversed). For example, for the pattern CNCN and the board CNCCCCCNCCC, the player may take the 2nd, 4th, 6th, 8th, and 10th token (the pattern was reversed and scaled by a factor of 2). Then the player may remove all tokens that certainly cannot be taken in any later move, because they do not match any pattern. Each such token counts as one point. The game is won by the player who scores the most points.

Wanting to get rich, Baj Tash demonstrated his game to the second richest man in the world, Gill Bytes of Byteotia.

Bytes liked the game very much (largely because Tash cleverly let Bytes win a few times) and asked what reward Tash would like for it. Tash said that he wanted to receive as many Byteotian cents as the number of ways to arrange in a line the sapphires and rubies used as tokens in the game. For example, 2 rubies (R) and 2 sapphires (S) can be arranged in 6 ways: RRSS, RSRS, RSSR, SRRS, SRSR, SSRR. Bytes readily agreed.

After Tash left, Bytes ordered you—his hired programmer—to compute how much he would have to pay.

Byteotia has an interesting currency system: 10 Byteotian cents make 1 Byteotian dime, 10 Byteotian dimes make 1 Byteotian dollar, 10 Byteotian dollars make a Byteotian hamilton, and so on; if we take 10 of any Byteotian monetary unit, we obtain 1 of the next larger unit. Gill Bytes is very meticulous, so he is most interested in the least significant digits of the reward he promised to pay. He would like to know the last $k$ digits of the reward expressed in the largest Byteotian monetary units in which it is an integer.

Input

In the first line there are three numbers $r$, $s$, and $k$ ($1 \le r, s \le 10^{15}$, $1 \le k \le 9$), denoting respectively the number of rubies, the number of sapphires, and the number of digits expected by Bytes.

In tests worth 30% of the points, the condition $s < 9$ holds.

In tests worth 30% of the points, the condition $k = 1$ holds.

Output

Output the last $k$ digits of the reward. If the reward has fewer than $k$ digits, output leading zeros so that exactly $k$ digits are printed in total.

Example

For the input:

11 5 9

the correct output is:

000004368