// Problem: P2020 [NOI2011] 兔农
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2020
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
using i64 = long long;

const int N = 6e6;
i64 n,f[N + 5],k,p,m,a[N + 5],T;
bool flag[N + 5];

struct matrix {
	i64 g[3][3];
	matrix() {
		memset(g , 0 , sizeof(g));
	}
	void clear() {
		memset(g , 0 , sizeof(g));
		return ;
	}
	void init() {
		g[0][0] = g[1][1] = g[2][2] = 1;
		return ;
	}
	matrix operator * (const matrix& z)const {
		matrix c;
		for(int k = 0;k < 3;++ k)
			for(int i = 0;i < 3;++ i)
				for(int j = 0;j < 3;++ j)
					(c.g[i][j] += g[i][k] * z.g[k][j] % p) %= p;
		return c; 
	}
}F,G,P,pac;

matrix power(matrix x,i64 y) {
	matrix ans;
	ans.init();
	for(;y;y >>= 1) {
		if(y & 1)
			ans = ans * x;
		x = x * x;
	}
	return ans;
}

int main() {
	freopen("noi2011_rabbit.in","r",stdin);
	freopen("noi2011_rabbit.out","w",stdout);
	scanf("%lld %lld %lld",&n,&k,&p);
	std::vector<i64> tags;
	f[1] = f[2] = 1;
	for(int i = 3;i <= N;++ i) {
		f[i] = (f[i - 1] + f[i - 2]) % k;
		if(f[i] == 1) {
			flag[i] = true;
			tags.pb(i);
			f[i] = 0;
		}
	}
	f[1] = f[2] = 1;
	for(int i = 3;i <= N;++ i) {
		f[i] = (f[i - 1] + f[i - 2]) % p;
		if(flag[i])
			(f[i] += p - 1) %= p;
	}
	if(n <= (i64)N) {
		printf("%lld\n",f[n]);
		return 0;
	}
	G.g[0][0] = 1;
	G.g[1][0] = 1;
	G.g[0][1] = 1;
	G.g[2][2] = 1;
	P = G;
	P.g[2][0] = p - 1;
	F.g[0][0] = f[tags[0]];
	F.g[0][1] = f[tags[0] - 1];
	F.g[0][2] = 1;
	m = tags.size();
	for(int i = 1;i < m;++ i)
		a[i] = tags[i] - tags[i - 1];
	i64 len = 0;
	for(T = 1;T <= 10;++ T) {
		bool flag = true;
		for(int i = 1;i < m - T&&i <= 1000;++ i) {
			if(a[i] != a[i + T]) {
				flag = false;
				break ;
			}
		}
		if(flag) {
			pac.init();
			for(int i = 1;i <= T;++ i) {
				pac = pac * power(G , a[i] - 1);
				pac = pac * P;
				len += a[i];
			}
			break ;
		}
	}
	pac = power(pac , (n - tags[0]) / len);
	F = F * pac;
	i64 res = n - tags[0] - ((n - tags[0]) / len) * len;
	for(int i = 1;i <= T;++ i) {
		if(res <= 0)
			break ;
		F = F * power(G , std::min(res , a[i] - 1));
		res -= a[i] - 1;
		if(res <= 0)
			break ;
		F = F * P;
		-- res;
	}	
	printf("%lld\n",F.g[0][0]);
	return 0;
}