数列 $(a_n)$ を $a_n = \displaystyle\sum_{i=0}^{n-1} A^i$ で定めると、$a_0 = 0$、$a_{n+1} = Aa_n + 1$ を満たします。求めるべきものは $a_X \bmod M$ です。

ここで、上の漸化式より行列を用いて $\begin{pmatrix} a_{n+1} \\ 1 \end{pmatrix} = \begin{pmatrix} A & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} a_n \\ 1 \end{pmatrix}$ と表すことができます。

$a_0 = 0$ であったため、$\begin{pmatrix} a_X \\ 1 \end{pmatrix} = \begin{pmatrix} A & 1 \\ 0 & 1 \end{pmatrix}^X \begin{pmatrix} 0 \\ 1 \end{pmatrix}$ です。

$\begin{pmatrix} A & 1 \\ 0 & 1 \end{pmatrix}^X$ の各成分を $M$ で割った余りは繰り返し二乗法を用いて $O(\log X)$ で求めることができます（整数の $X$ 乗を $M$ で割った余りを求めるのと同様の要領です）。

よってこの問題を $O(\log X)$ で解くことができました。

なお、$\displaystyle\sum_{i=0}^{X-1} A^i = \frac{A^X-1}{A-1}$ ですが、これを利用して解こうとする場合 $\text{mod } M$ における $A-1$ の逆元が存在するとは限らないことに注意してください。

実装例

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod) {
	// 行列乗算
	int n = a.size();
	vector<vector<ll>> res(n, vector<ll>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				res[i][j] += a[i][k] * b[k][j];
				res[i][j] %= mod;
			}
		}
	}
	return res;
}
vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll b, ll mod) {
	// 行列累乗
	int n = a.size();
	vector<vector<ll>> res(n, vector<ll>(n));
	for (int i = 0; i < n; i++) res[i][i] = 1;
	while (b) {
		if (b & 1) res = mat_mul(res, a, mod);
		a = mat_mul(a, a, mod);
		b >>= 1;
	}
	return res;
}
int main() {
	ll a, x, m;
	cin >> a >> x >> m;
	vector<vector<ll>> f = { {a,1},{0,1} };
	vector<vector<ll>> g = mat_pow(f, x, m);
	cout << g[0][1] << '\n';
}

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod) {
	// 行列乗算
	int n = a.size();
	vector<vector<ll>> res(n, vector<ll>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				res[i][j] += a[i][k] * b[k][j];
				res[i][j] %= mod;
			}
		}
	}
	return res;
}

vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll b, ll mod) {
	// 行列累乗
	int n = a.size();
	vector<vector<ll>> res(n, vector<ll>(n));
	for (int i = 0; i < n; i++) res[i][i] = 1;
	while (b) {
		if (b & 1) res = mat_mul(res, a, mod);
		a = mat_mul(a, a, mod);
		b >>= 1;
	}
	return res;
}

int main() {
	ll a, x, m;
	cin >> a >> x >> m;
	vector<vector<ll>> f = { {a,1},{0,1} };
	vector<vector<ll>> g = mat_pow(f, x, m);
	cout << g[0][1] << '\n';
}