Słynny bajtocki specjalista z zakresu teorii gier, Baj Tash, wynalazł bardzo interesującą grę. Plansza do tej gry składa się z pewnej liczby pól ułożonych w linii prostej. Początkowo na każdym polu planszy znajduje się jeden pionek. Są dwa rodzaje pionków, niebieskie i czerwone.

Gracze mają do dyspozycji kilka schematów, złożonych z niebieskich i czerwonych pionków. Gracze ruszają się na przemian. Każdy z graczy może wziąć z planszy grupę pionków ułożonych dokładnie tak samo, jak w którymś ze schematów (musi się zgadzać kolor pionków i ich wzajemne położenie; schemat można jednak skalować i odwrócić). Na przykład dla schematu CNCN i planszy CNCCCCCNCCC gracz może wziąć drugi, czwarty, szósty, ósmy i dziesiąty pionek (schemat został odwrócony i przeskalowany dwukrotnie). Następnie gracz może zabrać wszystkie pionki, których na pewno nie będzie można wziąć w kolejnych ruchach, ze względu na to, że nie pasują do żadnego schematu. Każdy taki pionek liczy się jako punkt. Grę wygrywa gracz, który zdobędzie największą liczbę punktów.

Chcąc się wzbogacić, Baj Tash zademonstrował swoją grę drugiemu najbogatszemu człowiekowi na świecie, Gillowi Bytesowi z Bajtycji.

Gra bardzo spodobała się Bytesowi (duża zasługa miało tu to, że Tash sprytnie pozwolił Bytesowi kilka razy wygrać) i spytał, jaką nagrodę Tash chciałby za nią dostać. Tash powiedział, że chce za nią dostać tyle bajtyckich centów, na ile sposobów można ułożyć w linię szafiry i rubiny, które zostały użyte jako pionki w grze. Na przykład, 2 rubiny (R) i 2 szafiry (S) można ułożyć na 6 sposobów: RRSS, RSRS, RSSR, SRRS, SRSR, SSRR. Bytes ochoczo się na to zgodził.

Po odejściu Tasha Bytes polecił Tobie - zatrudnionemu przez siebie informatykowi - obliczenie, ile będzie musiał mu zapłacić.

Bajtycja posiada interesujący system walut - 10 bajtyckich centów tworzy 1 bajtycką dimę, 10 bajtyckich dim to 1 bajtycki dolar, 10 bajtyckich dolarów to bajtycki hamilton, i tak dalej; jak weźmiemy 10 w dowolnych bajtyckich jednostkach monetarnych, to otrzymamy 1 w następnej większej jednostce. Gill Bytes jest bardzo drobiazgowy, także najbardziej go interesują najmniej znaczące cyfry nagrody, którą obiecał zapłacić. Chciałby on poznać $k$ ostatnich cyfr nagrody wyrażonej w największych bajtyckich jednostkach monetarnych, w których wyraża się ona liczbą całkowitą.

Wejście

W pierwszym wierszu podane są trzy liczby $r$, $s$ i $k$ ($1 \le r, s \le 10^{15}$, $1 \le k \le 9$), oznaczające odpowiednio liczbę rubinów, liczbę szafirów oraz liczbę cyfr oczekiwanych przez Bytesa.

W testach wartych 30% punktów zachodzi warunek $s < 9$.

W testach wartych 30% punktów zachodzi warunek $k = 1$.

Wyjście

Należy podać $k$ ostatnich cyfr nagrody. Jeśli nagroda ma mniej niż $k$ cyfr, to należy wypisać zera wiodące tak, by łącznie zostało wypisanych dokładnie $k$ cyfr.

Przykład

Dla danych wejściowych:

11 5 9

poprawną odpowiedzią jest:

000004368