CF17D.Notepad

Nick is attracted by everything unconventional. He doesn't like decimal number system any more, and he decided to study other number systems. A number system with base b caught his attention. Before he starts studying it, he wants to write in his notepad all the numbers of length n without leading zeros in this number system. Each page in Nick's notepad has enough space for c numbers exactly. Nick writes every suitable number only once, starting with the first clean page and leaving no clean spaces. Nick never writes number 0 as he has unpleasant memories about zero divide.

Would you help Nick find out how many numbers will be written on the last page.

尼克被一切非传统的事物所吸引。他不再喜欢十进制数系，转而决定研究其他数系。一个以 $b$ 为底的数系引起了他的注意。在开始学习之前，他想在自己的笔记本上写下该数系中所有长度为 $n$ 且不含前导零的数。尼克的笔记本每页恰好能容纳 $c$ 个数。尼克每个符合条件的数仅写一次，从第一页空白页开始书写，且页内不留空位。由于对“除零错误”有不愉快的记忆，尼克从不写下数字 $0$。

你能否帮尼克算出最后一页上会写多少个数？

The only input line contains three space-separated integers b, n and c (2 ≤ b < 10106, 1 ≤ n < 10106, 1 ≤ c ≤ 109). You may consider that Nick has infinite patience, endless amount of paper and representations of digits as characters. The numbers doesn't contain leading zeros.

唯一的一行输入包含三个以空格分隔的整数 $b$、$n$ 和 $c$（满足 $2 \le b < 10^{106}$，$1 \le n < 10^{106}$，$1 \le c \le 10^9$）。你可以认为 Nick 具有无限的耐心、无限量的纸张，以及将数字表示为字符的能力。这些数字不含前导零。

In the only line output the amount of numbers written on the same page as the last number.

在唯一的一行中输出与最后一个数字写在同一张纸上的数字个数。

In both samples there are exactly 4 numbers of length 3 in binary number system. In the first sample Nick writes 3 numbers on the first page and 1 on the second page. In the second sample all the 4 numbers can be written on the first page.

在两个样例中，二进制表示下长度恰好为 3 的数字均有且仅有 4 个。在第一个样例中，Nick 在第一页上写了 3 个数字，在第二页上写了 1 个数字。在第二个样例中，全部 4 个数字均可写在第一页上。