input:
1
ex
w?q
w
answer:
0

仅有的一篇题解输出了 $-1$。

由于数据过水，导致我和题解的代码都可以通过此题，但是随便一拍就不一样。附我的代码，欢迎找错。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
		f = (ch == '-' ? -1 : 1), ch = getchar();
	while (ch >= '0' && ch <= '9')
		s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return s * f;
}

const int mod = 1000000009;

int n;
char s[3][1000005];
int len[3], a[3][1000005];
int dp[1000005][2][2] = {{{0}}};

int work() {
	for (int i = 1; i <= n; i++) {
		int v1 = 0, v2 = 0, v3 = 0, v4 = 0, v10 = 0, v11 = 0, v20 = 0, v21 = 0, all = 1;
		for (int j = 0; j < 3; j++)
			if (a[j][i] == -1)
				all *= 26;
		if (a[0][i] == -1 && a[1][i] == -1 && a[2][i] == -1) {
			v1 = 26 * 25 * 24 / 6, v2 = v3 = 26 * 25 / 2, v4 = 26;
			v10 = v20 = 26 * 26, v11 = v21 = 26 * 25 / 2 * 26;
		}
		if (a[0][i] != -1 && a[1][i] == -1 && a[2][i] == -1) {
			v1 = (25 - a[0][i]) * (24 - a[0][i]) / 2, v2 = v3 = 25 - a[0][i], v4 = 1;
			v10 = 26, v11 = (25 - a[0][i]) * 26, v20 = 26, v21 = 26 * 25 / 2;
		}
		if (a[0][i] == -1 && a[1][i] != -1 && a[2][i] == -1) {
			v1 = a[1][i] * (25 - a[1][i]), v2 = 25 - a[1][i], v3 = a[1][i], v4 = 1;
			v10 = 26, v11 = a[1][i] * 26, v20 = 26, v21 = (25 - a[1][i]) * 26;
		}
		if (a[0][i] == -1 && a[1][i] == -1 && a[2][i] != -1) {
			v1 = a[2][i] * (a[2][i] - 1) / 2, v2 = v3 = a[2][i], v4 = 1;
			v10 = 26, v11 = 26 * 25 / 2, v20 = 26, v21 = a[2][i] * 26;
		}
		if (a[0][i] != -1 && a[1][i] != -1 && a[2][i] == -1) {
			bool le = a[0][i] < a[1][i], eq = a[0][i] == a[1][i];
			v1 = le * (25 - a[1][i]), v2 = eq * (25 - a[1][i]), v3 = le, v4 = eq;
			v10 = eq * 26, v11 = le * 26, v20 = 1, v21 = (25 - a[1][i]);
		}
		if (a[0][i] != -1 && a[1][i] == -1 && a[2][i] != -1) {
			bool le = a[0][i] < a[2][i], eq = a[0][i] == a[2][i];
			v1 = le * (a[2][i] - a[0][i] - 1), v2 = v3 = le, v4 = eq;
			v10 = 1, v11 = 25 - a[0][i], v20 = 1, v21 = a[2][i];
		}
		if (a[0][i] == -1 && a[1][i] != -1 && a[2][i] != -1) {
			bool le = a[1][i] < a[2][i], eq = a[1][i] == a[2][i];
			v1 = le * a[1][i], v2 = le, v3 = eq * a[1][i], v4 = eq;
			v10 = 1, v11 = a[1][i], v20 = eq * 26, v21 = le * 26;
		}
		if (a[0][i] != -1 && a[1][i] != -1 && a[2][i] != -1) {
			bool eq1 = a[0][i] == a[1][i], le1 = a[0][i] < a[1][i], eq2 = a[1][i] == a[2][i], le2 = a[1][i] < a[2][i];
			v1 = le1 && le2, v2 = eq1 && le2, v3 = le1 && eq2, v4 = eq1 && eq2;
			v10 = eq1, v11 = le1, v20 = eq2, v21 = le2;
		}
		dp[i][1][1] = dp[i - 1][1][1] * v4 % mod;
		dp[i][0][1] = (dp[i - 1][0][1] * v20 % mod + dp[i - 1][1][1] * v3 % mod) % mod;
		dp[i][1][0] = (dp[i - 1][1][0] * v10 % mod + dp[i - 1][1][1] * v2 % mod) % mod;
		dp[i][0][0] = (dp[i - 1][1][1] * v1 % mod + dp[i - 1][1][0] * v11 % mod + dp[i - 1][0][1] * v21 % mod + dp[i - 1][0][0] * all % mod) % mod;
	}
	int cnt = 0, mx = 0;
	for (int i = 0; i < 3; i++) {
		len[i] -= n, cnt += len[i] > 0, mx = len[i] > len[mx] ? i : mx;
		for (int j = 1; j <= len[i]; j++)
			a[i][j] = a[i][j + n];
	}
	if (!cnt)
		return dp[n][0][0];
	if (cnt == 1) {
		int ans = dp[n][0][0];
		if (len[1] > 0)
			ans = (ans + dp[n][1][0]) % mod;
		if (len[2] > 0)
			ans = (ans + dp[n][0][1]) % mod;
		for (int i = n + 1; i <= len[mx]; i++)
			if (a[mx][i] == -1)
				ans = ans * 26 % mod;
		return ans;
	}
	int res[2][2];
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			res[i][j] = dp[n][i][j];
	if (len[0] <= 0) {
		n = len[0] = min(len[1], len[2]);
		for (int i = 1; i <= len[1]; i++)
			a[0][i] = 0;
		dp[0][0][0] = (res[0][0] + res[1][0]) % mod, dp[0][1][0] = dp[0][1][1] = 0, dp[0][0][1] = (res[0][1] + res[1][1]) % mod;
	}
	else if (len[1] <= 0) {
		swap(len[0], len[1]), swap(a[0], a[1]);
		n = len[0] = min(len[1], len[2]);
		for (int i = 1; i <= len[1]; i++)
			a[0][i] = 0;
		dp[0][0][0] = (res[0][0] + res[0][1]) % mod, dp[0][1][0] = dp[0][1][1] = dp[0][0][1] = 0;
	}
	else {
		swap(len[1], len[2]), swap(a[1], a[2]), swap(len[0], len[1]), swap(a[0], a[1]);
		n = len[0] = min(len[1], len[2]);
		for (int i = 1; i <= len[1]; i++)
			a[0][i] = 0;
		dp[0][0][0] = res[0][0], dp[0][1][0] = dp[0][1][1] = 0, dp[0][0][1] = res[1][0];
	}
	work();
	int ans = dp[n][0][0] + dp[n][1][0];
	if (len[1] < len[2])
		ans = (ans + dp[n][0][1] + dp[n][1][1]) % mod, swap(len[1], len[2]), swap(a[1], a[2]);
	for (int i = 1; i <= len[1]; i++)
		if (a[1][i] == -1)
			ans = ans * 26 % mod;
	return ans;
}

signed main() {
	int T = read();
	while (T--) {
		scanf("%s\n%s\n%s", s[0] + 1, s[1] + 1, s[2] + 1);
		n = 1e9;
		for (int i = 0; i < 3; i++)
			len[i] = strlen(s[i] + 1), n = min(n, len[i]);
		for (int i = 0; i < 3; i++)
			for (int j = 1; j <= len[i]; j++)
				a[i][j] = s[i][j] == '?' ? -1 : s[i][j] - 'a';
		dp[0][1][1] = 1, dp[0][0][0] = dp[0][1][0] = dp[0][0][1] = 0;
		printf("%lld\n", work());
	}
	return 0;
}