unittest
{
	assert( [ "6 2 1001" ].solve == 1369 );
	assert( [ "1000 2 16" ].solve == 6 );
	assert( [ "10000000000 10 99959" ].solve == 492443256176507 );
	
	assert( [ "100 1 1" ].solve == 0 );		// 追加ケース
	assert( [ "100 1 2" ].solve == 100 );		// 追加ケース
	assert( [ "3 2 100" ].solve == 22 );		// 追加ケース
}



import std.conv;
import std.format;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = 0L;
	auto x = 0L;
	auto m = 0L;
	input.front.formattedRead!"%s %s %s"( n, x, m );
	
	if( x == 1 && m == 1 ) return 0L;
	
	// 途中で余りがループするはずなので、ループ長と合計を計算
	auto ts = new long[ 1 + m + 1 ];
	long[ long ] bs;
	auto l = 0L;
	auto r = 0L;
	for( auto i = 0L; i <= m; i++ )
	{
		ts[ i + 1 ] = ts[ i ] + x;
		if( x in bs )
		{
			l = bs[ x ];
			r = i;
			break;
		}
		bs[ x ] = i;
		x = x ^^ 2 % m;
	}
	if( n <= r ) return ts[ n ];
	
	// ループ回数と余りを計算
	auto c = ( n - l ) / ( r - l );
	auto k = ( n - l ) % ( r - l );
	
	// 答えを計算
	return ts[ l ] + ( ts[ r ] - ts[ l ] ) * c + ( ts[ l + k ] - ts[ l ] );
}
