($A,$N,$M)=glob<>;
die if not 1<=$A&&$A<=1e9;
die if not 0<=$N&&$N<=1e9;
die if not 1<=$M&&$M<=2e3;
if($M==1){print 0;exit}
@a=$a=1;
push@a,$a while(($a*=$A)%=$M)-1;
@_[@b=(1,$b=$A%@a)]=0..++$i;
$_[$b]=++$i,push@b,$b until$_[$b=$a[$b%@a]]//0;
print$b[$N<$_[$b]?$N:$_[$b]+($N-$_[$b])%(@b-$_[$b])]