Let us denote by f(x, m) the remainder of the Euclidean division of x by m.

Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M). Find \displaystyle{\sum_{i=1}^N A_i}.

Constraints

* 1 \leq N \leq 10^{10}
* 0 \leq X < M \leq 10^5
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N X M


Output

Print \displaystyle{\sum_{i=1}^N A_i}.

Examples

Input

6 2 1001


Output

1369


Input

1000 2 16


Output

6


Input

10000000000 10 99959


Output

492443256176507
n,x,m = map(int, raw_input().split())
ans = 0

seen = {}
reverse = {}
c = 0
while(x not in seen):
	seen[x] = c
	reverse[c] = x
	c+=1
	x = (x**2) % m
#print seen[x], c-1 
#print [(key, reverse[key])for key in sorted(reverse.keys())]
def f(n,a,b,reverse):
	ans = 0
	#print a,b
	for i in xrange(b+1):
		if n > 0:
			ans += reverse[i]
			n-=1
		else:
			break
	if n > 0:
		t = sum([reverse[uu] for uu in xrange(a,b+1)] or [0])
		ans += n/(b-a+1) * t
		n %= (b-a+1)

		for i in xrange(a,b+1):
			if n > 0:
				ans += reverse[i]
				n-=1
			else:
				break

	return ans


print f(n, seen[x], c-1, reverse)


