###############
($x,$m,$y,$e,$k)=`dc '-e2p?pd*1pp-|p'`;
while($k){
	($e,$f)=(($e*$x+3*$f*$y)%$m,($e*$y+$f*$x)%$m)if$k%2;
	($x,$y)=(($x*$x+3*$y*$y)%$m,$x*$y*2%$m);
	$k>>=1;
}
print 2*($e-1)%$m;