经调试发现乘法过程中会出现负数导致无法右移TLE，不知该怎么解决

#include<bits/stdc++.h>
#define ll long long
#define maxn 55
using namespace std;
template<typename T>inline void read(T &a){
	T x=0;a=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')a=-1;
	for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	a*=x;
}
ll a,p,c,x0,n,g;
inline int mul(ll a,ll b){
	//cout<<"Multiplying..."<<endl;
	ll res=0;
	for(;b;b>>=1,a=(a<<1)%p)if(b&1)res=(res%p+a%p)%p;
	return res%p;
}
struct Mat{
	ll x[4][4];
	Mat(){memset(x,0,sizeof(x));}
	inline Mat operator*(Mat b){
		//for(int i=1;i<=2;i++){
		//	for(int j=1;j<=2;j++)cout<<b.x[i][j]<<" ";cout<<endl;
		//}cout<<endl;
		Mat res;
		for(int i=1;i<=2;i++)
			for(int j=1;j<=2;j++)
				for(int k=1;k<=2;k++)
					res.x[i][j]=(res.x[i][j]%p+mul(x[i][k],b.x[k][j]))%p;
		//for(int i=1;i<=2;i++){
		//	for(int j=1;j<=2;j++)cout<<res.x[i][j]<<" ";cout<<endl;
		//}cout<<endl;
		return res;
	}
};
inline Mat pow(Mat a,ll b){
	//cout<<"Power..."<<endl;
	Mat res;res.x[1][1]=res.x[2][2]=1;
	for(;b;b>>=1,a=a*a)if(b&1)res=res*a;
	return res;
}
int main(){
	read(p),read(a),read(c),read(x0),read(n),read(g);
	if(n==0){printf("%d\n",x0);return 0;}
	Mat ans;ans.x[1][1]=a,ans.x[1][2]=ans.x[2][2]=1;
	ans=pow(ans,n);
	Mat init;init.x[1][1]=x0,init.x[2][1]=c;
	ans=ans*init;
	printf("%lld\n",ans.x[1][1]%g);
	return 0;
}