这个题不想写矩乘，搞成了这个东西：

$X_i\equiv aX_{i-1}+c,X_i+\dfrac c {a-1}\equiv aX_{i-1}+c+\dfrac c {a-1}\equiv aX_{i-1}+c(\dfrac a {a-1})\pmod m$

即 $X_i+\dfrac c{a-1}\equiv a(X_{i-1}+\dfrac c {a-1})\pmod m$

构成等比数列了。

于是按照这个思路写了这么个东西：

#include <bits/stdc++.h>
#define ull long long
using namespace std;
ull MOD,mod;
void extend_gcd(ull a,ull b,ull &x,ull &y) {
	if(!b) {x=1,y=0;return;}
	extend_gcd(b,a%b,x,y);
	ull tmp=x;
	x=y;
	y=tmp-(a/b)*y;
}
ull mod_inverse(ull a,ull m) {
	ull x,y;
	extend_gcd(a,m,x,y);
	return (m+x%m)%m;
}
inline ull div_mod(ull a,ull b) {
	return ((a%MOD)*(mod_inverse(b,MOD)%MOD))%MOD;
}
inline ull qp(ull a, ull b) {
	ull ans=1;
	while(b) {
		if(b&1) ans=(ans*a)%MOD;
		a=(a*a)%MOD,b>>=1; 
	}
	return (ans+MOD)%MOD;
}
int main(void) {
	ull a,p,q,k;
	cin>>MOD>>p>>q>>a>>k>>mod;
	a%=MOD,q%=MOD;
	if(p==1) k%=MOD,cout<<((a+(k*q)%MOD)%MOD+MOD)%MOD<<endl;
	else {
		ull qq=qp(p,k);
		ull sub=div_mod(q,p-1);
		ull ans=(a+sub)%MOD*qq%MOD-sub;
		cout<<(ans+mod)%mod<<endl; 
	}
	return 0;
} 

WA 20pts

ull 指的是 long long 无所谓（