fib.cpp

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

struct mat
{
	ull m[2][2];

	mat operator* (const mat &rhs) const
	{
		mat ans = {0, 0, 0, 0};
	
		for (int i = 0; i < 2; i++) {

			for (int j = 0; j < 2; j++) {

				for (int k = 0; k < 2; k++) {

					ans.m[i][j] += m[i][k]*rhs.m[k][j];
				}
			}
		}

		return ans;
	}

	mat operator% (ull x) const
	{
		mat ans = {0, 0, 0, 0};

		for (int i = 0; i < 2; i++) {

			for (int j = 0; j < 2;  j++) {

				ans.m[i][j] = m[i][j]%x;
			}
		}

		return ans;
	}
};

mat power(mat x, ull b, ull mod)
{
	mat ans = {1, 0, 0, 1};

	while (b) {

		if (b&1ull) ans = (ans*x) % mod;

		x = (x*x) % mod;
		b >>= 1;
	}

	return ans;
}

int main()
{
	ull n, b;
	cin >> n >> b;

	mat fib = {1, 1, 1, 0};

	fib = power(fib, n, b);

	ull ans = 2ull*fib.m[0][0] - 1;

	ans %= b;

	cout << ans << "\n";

	return 0;
}