求助蜜汁 MLE

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple <int, int, bool> idx;
typedef pair <ll, ll> val;
const int N = 10000010;
const ll mod = 998244353;
int T, b, l1, a1[N], l2, a2[N];
ll pw[N];
map <idx, val> dp;
val dfs (int i, int j, bool up, bool o) {
	int lim = up? o? a2[i]: a1[i]: b - 1;
	if (i == 1) {
		bool f = (j <= lim);
		return {f, f * j};
	}
	if (dp.count ({i, j, up})) {
		return dp[{i, j, up}];
	}
	val& res = dp[{i, j, up}];
	for (int j1 = 0; j1 <= min (j, lim); j1++) {
		val x = dfs (i - 1, j - j1, up && (j1 == lim), o);
		(res.first += x.first) %= mod;
		(res.second += 1ll * j1 * x.first % mod + x.second) %= mod;
	}
	if (j > lim) {
		return res;
	}
	for (int j1 = b - j; j1 < b; j1++) {
		val x = dfs (i - 1, j1, up && (j == lim), o);
		(res.first += x.first * b % mod) %= mod;
		(res.second += 1ll * j * x.first % mod * b % mod + x.second) %= mod;
	}
	return res;
}
int main () {
	// freopen ("pocket.in", "r", stdin);
	// freopen ("pocket.out", "w", stdout);
	scanf ("%d", &T);
	while (T --> 0) {
		scanf ("%d%d", &b, &l1);
		for (int i = 1; i <= l1; i++) {
			scanf ("%d", &a1[i]);
		}
		scanf ("%d", &l2);
		for (int i = 1; i <= l2; i++) {
			scanf ("%d", &a2[i]);
		}
		pw[0] = 1;
		for (int i = 1; i <= l2; i++) {
			pw[i] = pw[i - 1] * b % mod;
		}
		bool A = (l1 == l2);
		for (int i = 1; i <= l1; i++) {
			if (!A || a1[i] != a2[i]) {
				A = false;
				break;
			}
		}
		if (A) {
			int s = 0, w = 0;
			ll ans = 0;
			for (int i = 1; i <= l2; i++) {
				if (a2[i] + s < b) {
					s += a2[i];
				} else {
					(ans += s * pw[w++]) %= mod;
					s = a2[i];
				}
			}
			(ans += s * pw[w++]) %= mod;
			printf ("%lld\n", ans);
			continue;
		}
		for (int i = 1; i <= l1; i++) {
			a1[i]--;
			if (i == l1 && a1[i] == 0) {
				l1--;
				break;
			}
			if (a1[i] >= 0) {
				break;
			}
			a1[i] = b - 1;
		}
		dp = map <idx, val> ();
		ll ans = 0;
		for (int i = 0; i < b; i++) {
			(ans += mod - dfs (l1, i, true, false).second) %= mod;
		}
		dp = map <idx, val> ();
		for (int i = 0; i < b; i++) {
			(ans += dfs (l2, i, true, true).second) %= mod;
		}
		printf ("%lld\n", ans);
	}
	return 0;
}