Integer sequence $\boldsymbol{a}$ having length $2n+2$ is defined as follows:

$a_{0}=0$
$a_{1}=C$
$a_{i+2}=(a_{i+1}+a_i)\ \text{\% M}$, where $0\leq i<2n$

Write a function generator, $gen$, to generate the remaining values for $a_2$ through $a_{2n+1}$. The values returned by $gen$ describe two-dimensional vectors $v_1\ldots v_n$, where each sequential pair of values describes the respective $\boldsymbol{x}$ and $y$ coordinates for some vector $\boldsymbol{\nu}$ in the form $x_1,y_1,x_2,y_2,\ldots,x_n,y_n$. In other words, $v_1=(a_2,a_3),v_2=(a_4,a_5),...,v_n=(a_{2n},a_{2n+1})$.

Let $\mbox{S}$ be the set of scalar products of $v_i$ and $v_j$ for each $1\leq i,j\leq n$, where $i\neq j$.
Determine the number of different residues in $\mbox{S}$ and print the resulting value modulo $\mbox{M}$.

Input Format

A single line of three space-separated positive integers: $\mbox{C}$ (the value of $a_1$), $\mbox{M}$ (the modulus), and $n$ (the number of two-dimensional vectors), respectively.

Constraints

$1\leq C\leq10^9$
$1\leq M\leq10^9$ 
$1\leq n\leq3\times10^5$

Output Format

Print a single integer denoting the number of different residues $\textbf{\% M}$ in $\mbox{S}$.

Sample Input
4 5 3

Sample Output
2

Explanation

Sequence $a=a_0,a_1,(a_1+a_0)\text{\%}M,(a_2+a_1)\text{\%}M,...,(a_{2n}+a_{2n-1})\text{\%}M\}$ 
$=\{0,\ 4,\ (4+0)\%5,\ (4+4)\%5,\ (3+4)\%5,\ (2+3)\%5,\ (0+2)\%5,\ (2+0)\%5\}$
$=\{0,4,4,3,2,0,2,2\}$.

This gives us our vectors: $v_1=(4,3)$, $v_2=(2,0)$, and $v_3=(2,2)$.  

Scalar product $S_0(v_1,v_2)=8$. 

Scalar product $S_2(v_2,v_3)=4$. 

Scalar product $S_0(v_1,v_3)=14$. 

There are $2$ residues $\%5$ in $\mbox{S}$ (i.e.: $3$ and $4$), so we print the result of $2\%5$ (which is $2$).

Difficulty: MEDIUM_HARD
Tags: Number theory

Starter code:

Solutions:
(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


from sys import stdin as inp
(C, M, N) = map(int, inp.readline().rstrip().split())
vals = set()
(f1, f2) = (0, 1)
for i in range(4 * N - 2):
	tmp = f2
	f2 = (f1 + f2) % M
	f1 = tmp
	if i >= 5 and i % 2 == 1:
		vals.add(f2 * C ** 2 % M)
print(len(vals) % M)


(C, M, n) = map(int, input().split())
a = 3 * C * C
b = 5 * C * C
residues = set()
for _ in range(2 * n - 3):
	a = (a + b) % M
	b = (a + b) % M
	residues.add(b)
print(len(residues))


def my_sol(C, M, n):
	if n == 1:
		return 0
	if M == 1:
		return 1
	min_k = 7
	max_k = n * 4 - 1
	S = set()
	a_p0 = 0
	a_p1 = 1
	for i in range(2, max_k + 1):
		a = (a_p0 + a_p1) % M
		if i >= min_k and i % 2 == 1:
			S.add(a * C ** 2 % M)
		a_p0 = a_p1
		a_p1 = a
	return len(S)
(C, M, n) = map(lambda x: int(x), input().split())
print(my_sol(C, M, n))


(c, m, n) = list(map(int, input().split()))
a = [0] * (2 * n + 2)
a[1] = c
for i in range(2, 2 * n + 2):
	a[i] = (a[i - 1] + a[i - 2]) % m
ss = set()
level = 1
while level <= n:
	i = 0
	while i < n - level:
		ss.add((a[2 * i + 2] * a[2 * (i + level) + 2] + a[2 * i + 3] * a[2 * (i + level) + 3]) % m)
		i += level
	level = 2 * level
level = 1
while level <= n:
	i = 1
	while i < n - level:
		ss.add((a[2 * i + 2] * a[2 * (i + level) + 2] + a[2 * i + 3] * a[2 * (i + level) + 3]) % m)
		i += level
	level = 2 * level
print(len(ss) % m)


(C, M, n) = map(int, input().split())
b0 = 0
b1 = C
idx = {}
g = set()
for i in range(n):
	(b0, b1) = ((b0 + b1) % M, (b0 + 2 * b1) % M)
	if (b0, b1) in g:
		for j in range(i, min(i * 2, n)):
			idx[j + 1] = idx[j + 1 - i]
		break
	g.add((b0, b1))
	idx[i + 1] = (b0, b1)
k = sorted(idx.keys())
r = set([(idx[d][0] * idx[c][0] + idx[d][1] * idx[c][1]) % M for (c, d) in zip(k[1:], k[:-1])] + [(idx[d][0] * idx[c][0] + idx[d][1] * idx[c][1]) % M for (c, d) in zip(k[2:], k[:-2])])
print(len(r) % M)


r = input()
r = r.split(' ')
c = int(r[0])
m = int(r[1])
n = int(r[2])
a = 0
b = 1
d = {}
c = c * c % m
for i in range(2, 4 * n):
	next = (a + b) % m
	a = b
	b = next
	if i > 6 and i % 2 == 1:
		d[b * c % m] = '*'
print(len(d) % m)


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


def solve(C, M, n):
	residues = set()
	fib = [0, C % M] + [0] * (2 * n + 2 * (n - 1))
	for i in range(2, len(fib)):
		fib[i] = (fib[i - 2] + fib[i - 1]) % M
	residues = set()
	for i in range(3, 2 * n):
		residues.add(fib[2 * i + 1] * C % M)
	return len(residues) % M
(C, M, n) = map(int, input().split())
print(solve(C, M, n))


(C, M, N) = map(int, input().split())
p = set()
a = 3 * C * C % M
b = 5 * C * C % M
for n in range(3, 2 * N):
	a = (a + b) % M
	b = (a + b) % M
	p.add(b)
print(len(p))


class Matrix2:

	def __init__(self, a=1, b=0, c=0, d=1):
		(self.m00, self.m01, self.m10, self.m11) = (a, b, c, d)

	def __mul__(self, B):
		return Matrix2((self.m00 * B.m00 + self.m01 * B.m10) % P, (self.m00 * B.m01 + self.m01 * B.m11) % P, (self.m10 * B.m00 + self.m11 * B.m10) % P, (self.m10 * B.m01 + self.m11 * B.m11) % P)

	def __pow__(self, n):
		if n == 0:
			return Matrix2()
		if n & 1 == 0:
			return (self * self) ** (n >> 1)
		return self * (self * self) ** (n >> 1)

def main():
	global P
	(C, P, n) = map(int, input().split())
	C %= P
	F2 = Matrix2(0, 1, 1, 1) ** 2
	M = F2 ** 2
	S = set()
	for ipj in range(3, 2 * n):
		M *= F2
		S.add(M.m11 * C * C % P)
	print(len(S) % P)
main()


from math import sqrt, pow
data = input()
(C, M, n) = list(map(int, data.split(' ')))
if n > 1:
	lambda_1 = (3 - sqrt(5)) / 2
	lambda_2 = (3 + sqrt(5)) / 2
	alpha = C ** 2 % M * (pow(lambda_1, 4) / (1 + lambda_1) + pow(lambda_2, 4) / (1 + lambda_2))
	S = [int(alpha) % M]
	if n > 2:
		alpha = C ** 2 % M * (pow(lambda_1, 5) / (1 + lambda_1) + pow(lambda_2, 5) / (1 + lambda_2))
		S.append(int(alpha) % M)
		for k in range(6, 2 * n + 1):
			alpha = (3 * S[-1] - S[-2]) % M
			S.append(alpha)
	print(len(set(S)) % M)
else:
	print(0)


import math as m

def solve(C, M, n):
	phi = (1 + m.sqrt(5)) / 2
	psi = (1 - m.sqrt(5)) / 2
	phi_2 = 1 + phi
	psi_2 = 1 + psi
	alpha = C ** 2 % M * int(pow(phi_2, 4) / (1 + phi_2) + pow(psi_2, 4) / (1 + psi_2))
	S = [alpha % M]
	if n == 1:
		print(0)
	else:
		if n > 2:
			alpha = C ** 2 % M * int(pow(phi_2, 5) / (1 + phi_2) + pow(psi_2, 5) / (1 + psi_2))
			S.append(alpha % M)
			for k in range(6, 2 * n + 1):
				alpha = 3 * S[-1] - S[-2]
				S.append(alpha % M)
		S = set(S)
		print(len(S))
data = input()
(C, M, n) = list(map(int, data.split(' ')))
solve(C, M, n)


import math as m

def solve(C, M, n):
	phi = (1 + m.sqrt(5)) / 2
	psi = (1 - m.sqrt(5)) / 2
	phi_2 = 1 + phi
	psi_2 = 1 + psi
	alpha = C ** 2 % M * int(pow(phi_2, 4) / (1 + phi_2) + pow(psi_2, 4) / (1 + psi_2))
	S = [alpha % M]
	if n == 1:
		print(0)
	else:
		if n > 2:
			alpha = C ** 2 % M * int(pow(phi_2, 5) / (1 + phi_2) + pow(psi_2, 5) / (1 + psi_2))
			S.append(alpha % M)
			for k in range(6, 2 * n + 1):
				alpha = 3 * S[-1] - S[-2]
				S.append(alpha % M)
		S = set(S)
		print(len(S))
data = input()
(C, M, n) = list(map(int, data.split(' ')))
solve(C, M, n)


(c, m, n) = list(map(int, input().split()))
a = [0] * (2 * n + 2)
a[1] = c
for i in range(2, 2 * n + 2):
	a[i] = (a[i - 1] + a[i - 2]) % m
ss = set()
level = 1
while level <= n:
	i = 0
	while i < n - level:
		ss.add((a[2 * i + 2] * a[2 * (i + level) + 2] + a[2 * i + 3] * a[2 * (i + level) + 3]) % m)
		i += level
	level = 2 * level
level = 1
while level <= n:
	i = 1
	while i < n - level:
		ss.add((a[2 * i + 2] * a[2 * (i + level) + 2] + a[2 * i + 3] * a[2 * (i + level) + 3]) % m)
		i += level
	level = 2 * level
print(len(ss) % m)


def numResidues(f1, mod, n):
	f0 = 0
	fs = []
	for i in range(0, 2 * n):
		f2 = (f0 + f1) % mod
		fs.append(f2)
		f0 = f1
		f1 = f2
	ps = set()
	for i in range(1, 2 * n - 2):
		ps.add((fs[i] * fs[i] + fs[i + 1] * fs[i + 1]) % mod)
	return len(ps) % mod

def main():
	(f1, mod, n) = input().split()
	(f1, mod, n) = [int(f1), int(mod), int(n)]
	print(numResidues(f1, mod, n))
main()


(C, M, n) = map(int, input().split())
CC = C * C % M
p = 5
q = 3
r = 2
residues = set()
for _ in range(3, 2 * n):
	(p, q, r) = ((2 * p + q) % M, (p + q) % M, (q + r) % M)
	res = p * CC % M
	residues.add(res)
print(len(residues))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


def solve(C, M, n):
	residues = set()
	fib = [0, C % M] + [0] * (2 * n + 2 * (n - 1))
	for i in range(2, len(fib)):
		fib[i] = (fib[i - 2] + fib[i - 1]) % M
	residues = set()
	for i in range(3, 2 * n):
		residues.add(fib[2 * i + 1] * C % M)
	return len(residues) % M
(C, M, n) = map(int, input().split())
print(solve(C, M, n))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


import sys

def solve(C, M, n):
	s = set()
	(f0, f1) = (0, C)
	for k in range(2, 4 * n):
		(f0, f1) = (f1, (f0 + f1) % M)
		if 7 <= k and k % 2 == 1:
			s.add(C * f1 % M)
	return len(s) % M

def main():
	(C, M, n) = list(map(int, sys.stdin.readline().split()))
	print(solve(C, M, n))
main()


def solve(C, M, n):
	residues = set()
	fib = [0, C % M] + [0] * (2 * n + 2 * (n - 1))
	for i in range(2, len(fib)):
		fib[i] = (fib[i - 2] + fib[i - 1]) % M
	residues = set()
	for i in range(3, 2 * n):
		residues.add(fib[2 * i + 1] * C % M)
	return len(residues) % M
(C, M, n) = map(int, input().split())
print(solve(C, M, n))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


[c, m, n] = list(map(int, input().split(' ')))
veclist = []
currvec = [0, c]
for i in range(2 * n - 1):
	currvec = [(currvec[0] + currvec[1]) % m, (currvec[0] + 2 * currvec[1]) % m]
	veclist.append(currvec)
resset = set()
for i in range(1, 2 * n - 2):
	resset.add((veclist[0][0] * veclist[i][0] + veclist[0][1] * veclist[i][1]) % m)
print(len(resset) % m)


def solve(C, M, n):
	residues = set()
	fib = [0, C % M] + [0] * (2 * n + 2 * (n - 1))
	for i in range(2, len(fib)):
		fib[i] = (fib[i - 2] + fib[i - 1]) % M
	residues = set()
	for i in range(3, 2 * n):
		residues.add(fib[2 * i + 1] * C % M)
	return len(residues) % M
(C, M, n) = map(int, input().split())
print(solve(C, M, n))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


def fib_gen(mod):
	(f0, f1) = (0, 1)
	while True:
		yield f0
		(f0, f1) = (f1, f0 + f1 % mod)
(c, m, n) = map(int, input().split())
fib_it = fib_gen(m)
for _ in range(7):
	next(fib_it)
ret = len(set((c * c * fi % m for (fi, _1, _2) in zip(fib_it, fib_it, range(3, 2 * n)))))
print(ret)


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


def fib_gen(mod):
	(f0, f1) = (0, 1)
	while True:
		yield f0
		(f0, f1) = (f1, f0 + f1 % mod)
(c, m, n) = map(int, input().split())
fib_it = fib_gen(m)
for _ in range(7):
	next(fib_it)
ret = len(set((c * c * fi % m for (fi, _1, _2) in zip(fib_it, fib_it, range(3, 2 * n)))))
print(ret)


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


def fib_gen(mod):
	(f0, f1) = (0, 1)
	while True:
		yield f0
		(f0, f1) = (f1, f0 + f1 % mod)
(c, m, n) = map(int, input().split())
fib_it = fib_gen(m)
for _ in range(7):
	next(fib_it)
ret = len(set((c * c * fi % m for (fi, _1, _2) in zip(fib_it, fib_it, range(3, 2 * n)))))
print(ret)


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


def fib_gen(mod):
	(f0, f1) = (0, 1)
	while True:
		yield f0
		(f0, f1) = (f1, f0 + f1 % mod)
(c, m, n) = map(int, input().split())
fib_it = fib_gen(m)
for _ in range(7):
	next(fib_it)
ret = len(set((c * c * fi % m for (fi, _1, _2) in zip(fib_it, fib_it, range(3, 2 * n)))))
print(ret)


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


def fib_gen(mod):
	(f0, f1) = (0, 1)
	while True:
		yield f0
		(f0, f1) = (f1, f0 + f1 % mod)
(c, m, n) = map(int, input().split())
fib_it = fib_gen(m)
for _ in range(7):
	next(fib_it)
ret = len(set((c * c * fi % m for (fi, _1, _2) in zip(fib_it, fib_it, range(3, 2 * n)))))
print(ret)


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


def solve(C, M, n):
	residues = set()
	fib = [0, C % M] + [0] * (2 * n + 2 * (n - 1))
	for i in range(2, len(fib)):
		fib[i] = (fib[i - 2] + fib[i - 1]) % M
	residues = set()
	for i in range(3, 2 * n):
		residues.add(fib[2 * i + 1] * C % M)
	return len(residues) % M
(C, M, n) = map(int, input().split())
print(solve(C, M, n))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = map(int, input().split())
if n == 1:
	print('0')
else:
	arr = [0 for i in range(2 * n + 2)]
	arr[0] = 0
	arr[1] = c
	l = []
	for i in range(2, 2 * n + 2):
		arr[i] = (arr[i - 1] + arr[i - 2]) % m
	for i in range(2, 2 * n - 2, 2):
		temp = (arr[i] * arr[i + 2] + arr[i + 1] * arr[i + 3]) % m
		l.append(temp)
		temp = (arr[i] * arr[i + 4] + arr[i + 1] * arr[i + 5]) % m
		l.append(temp)
	temp = (arr[2 * n - 2] * arr[2 * n] + arr[2 * n - 1] * arr[2 * n + 1]) % m
	l.append(temp)
	l = set(l)
	print(len(l))


(c, m, n) = list(map(int, input().strip().split()))
last = 0
current = c
residues = set()
for i in range(2 * n - 1):
	(current, last) = ((current + last) % m, current % m)
	(current, last) = ((current + last) % m, current % m)
	if i >= 2:
		residues.add(current * c % m)
print(len(residues))