문자 'A', 'B', 'C'로 이루어진 문자열이 다음 조건을 만족하면 좋은 문자열이라고 합니다.

- 모든 인접한 두 문자가 다르다.

길이가 $2n+1$인 두 좋은 문자열 $s$, $t$의 쌍 $(s, t)$이 다음 조건을 만족하면 멋진 쌍이라고 한다.

- 두 문자열의 최장 공통 부분 수열(LCS)의 길이가 정확히 $n$이다.

당신은 두 개의 문자열 $s$, $t$가 주어지며, 각 문자열은 'A', 'B', 'C', '?'로 이루어져 있다. 여기서 각 '?'를 'A', 'B', 'C' 중 하나로 치환하는 모든 경우의 수를 구해야 한다. 단, 치환 후 $(s, t)$는 멋진 쌍이 되어야 한다.

치환 방법을 $998\ 244\ 353$으로 나눈 나머지를 출력하라.

[입력]

첫 번째 줄에 테스트케이스의 개수 $t$가 주어진다. 각 테스트케이스는 다음과 같이 주어진다.

첫 번째 줄에 정수 $n$이 주어진다. ($1 \le n \le 10^6$)

두 번째 줄에 길이 $2n+1$인 문자열 $s$가 주어진다. $s$는 'A', 'B', 'C', '?'로 이루어져 있다.

세 번째 줄에 길이 $2n+1$인 문자열 $t$가 주어진다. $s$는 'A', 'B', 'C', '?'로 이루어져 있다.

모든 테스트케이스에서 $n$의 총함이 $10^6$을 넘지 않음이 보장된다.


[출력]

각 테스트케이스마다 한 줄에 정수 하나를 출력한다. 이 값은 모든 '?'를 치환하는 방법의 수이며, $(s, t)$가 멋진 쌍이 되도록 하는 경우의 수를 $998\ 244\ 353$으로 나눈 나머지이다.


[힌트]

첫 번째 테스트 케이스에서, 멋진 쌍으로 가능한 것은 (ABA, CBC)이다.
두 번쨰 테스트 케이스에서, 멋진 쌍으로 가능한 것은 (ABA, CBC), (ACA, CBC), (ABA, CBC)이다.

댓글을 작성하려면 로그인해야 합니다.