计算如下公式的值：


R = BP mod M


B、P 和 M 都是很大的数字，速度要快，这可是有时间限制的！


输入
每组输入有三个很大的数字 B、P 和 M，B 和 P 的取值范围在 [0, 2147483647] 之间，而 M 的取值范围在 [1, 46340] 之间。组与组之间有一个空行。


输出
上述算式的结果。
输入：
1101020232
718099356
10827

41629812
399515788
29139

220793754
2831418
18232

266960184
401372383
27652

1089628815
919033167
29752

1975443642
897236187
12357

340638690
28996060
16939

1192487670
346405248
8007

548453889
944101956
23478

560544556
151939736
27063

417307800
363130680
34872

55129542
778679088
25788
输出：
1026
3111
2400
7156
1679
4941
9298
5220
7827
19384
15984
23640
数还有很多也很大，时间限制是一秒；谁有巧妙的算法能保证时间不超过限制?