出题人丧心病狂的卡常数，导致 $O(T \log n)$ 的程序都无法通过了 /kk

求各路神仙帮忙卡常，盲猜是数据类型转换常数太大

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using Int = __int128;

int T;
Int ans[2], t[2][2];

void mul(Int ans[], Int a[], Int b[][2], LL p) {
	Int tmp[2] = {0};
	for (int i = 0; i < 2; i ++ )
		for (int j = 0; j < 2; j ++ )
			tmp[i] = (tmp[i] + (Int)a[j] * b[j][i]) % p;
	memcpy(ans, tmp, sizeof tmp);
}

void mul(Int ans[][2], Int a[][2], Int b[][2], LL p) {
	Int tmp[2][2] = {0};
	for (int i = 0; i < 2; i ++ )
		for (int j = 0; j < 2; j ++ )
			for (int k = 0; k < 2; k ++ )
				tmp[i][j] = (tmp[i][j] + (Int)a[i][k] * b[k][j]) % p;
	memcpy(ans, tmp, sizeof tmp);
}

void solve(LL a, LL b, LL n, LL p) {
	ans[0] = 1, ans[1] = 1;
	t[0][0] = b, t[0][1] = 0, t[1][0] = a, t[1][1] = a;
	while (n) {
		if (n & 1) mul(ans, ans, t, p);
		mul(t, t, t, p); n >>= 1;
	}
	
	LL res = ans[0];
	printf("%lld\n", res);
}

int main() {
	scanf("%d", &T);
	while (T -- ) {
		LL n, a, b, p;
		scanf("%lld%lld%lld%lld", &n, &a, &b, &p);
		solve(a, b, n, p);
	}
	
	return 0;
}