Description

给定一个数，其值用A的B次方表示(B<100000)，求该数除以一个整数C（C<100000）所得的余数。注意算法的合理性，其性能有一定的要求。 每行有三个数，依次表示A，B，C，每行对输出对应的余数。

Sample

Input

1 2 3
2 1 3
3 3 5

Output

1
2
2