说明

Description

你有一个本子，你要往上面写全部的长度为$n$的$b$进制数字，每一页可以写$c$个。要求所有数字必须严格不含前导$0$。求最后一页上有多少个数字

Input

三个数，依次是进制数$b$,数字长度$n$，每一页的个数$c$。

Output

一行一个整数代表答案

Hint

$Forall:$

$2~\leq~b~<~10^{10^6}~,~1~\leq~n~<~10^{10^6}~,~1~\leq~c~\leq~10^9$

感谢@一扶苏一 提供的翻译

输入格式

The only input line contains three space-separated integers $ b $ , $ n $ and $ c $ ( $ 2<=b<10^{106} $ , $ 1<=n<10^{106} $ , $ 1<=c<=10^{9} $ ). 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.

输出格式

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

样例

2 3 3

1

样例

2 3 4

4

提示

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.