34345번 - SNUPC 문자열 (Hard)

문제

SNUPC 문자열이란, 알파벳 S,N,U,P,C로 이루어진 문자열을 말한다. 당신은 길이 $N$의 SNUPC 문자열 $S$를 선물받았지만, 그만 잃어버리고 말았다. 다행히도, 예전에 그 문자열을 가지고 놀던 종이 두 장이 남아 있어, 이를 바탕으로 복원을 시도할 수 있게 되었다. 각 종이에는 다음과 같은 내용이 적혀 있다. 같은 문자열이 여러 번 적혀 있을 수 있다.

• (종이 1) 문자열 $S$에서 S 또는 N이 나올 때마다 그 뒤에서 끊어 만든 문자열 조각 $x$개가 임의의 순서로 종이에 적혀 있다. 예를 들어, SUNUPC라는 문자열은 S,UN,UPC로 나눌 수 있으며, 이 세 조각이 임의의 순서로 종이에 적혀 있다.
• (종이 2) 문자열 $S$에서 U 또는 P가 나올 때마다 그 뒤에서 끊어 만든 문자열 조각 $y$개가 임의의 순서로 종이에 적혀 있다. 예를 들어, SUNUPP라는 문자열은 SU,NU,P,P로 나눌 수 있으며, 이 네 조각이 임의의 순서로 종이에 적혀 있다.

모그는 두 종이에 적힌 정보를 바탕으로, 원래의 SNUPC 문자열 $S$를 복원하고자 한다. 하지만 가능한 복원 형태가 매우 다양할 수 있으므로, 복원된 SNUPC 문자열로 가능한 것의 개수를 소수 998ドル,244円,353円(=119\times 2^{23}+1)$으로 나눈 나머지를 구하자. 원본 SNUPC 문자열은 한 개 이상 존재함이 보장된다.

이 때 문자열 조각들을 이어 붙인 순서는 고려하지 않고, 복원된 문자열이 같으면 같은 문자열이다.

입력

이 문제는 여러 개의 테스트 케이스로 이루어져 있다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T\le 10^4)$

각 테스트 케이스의 첫째 줄에 양의 정수 $N$이 주어진다. 이는 원본 SNUPC 문자열의 길이를 뜻한다. $(1\le N\le 10^5)$

각 테스트 케이스의 둘째 줄에 양의 정수 $x, y$가 공백으로 구분되어 주어진다. $(1\le x,y \le N)$

각 테스트 케이스의 셋째 줄에 $x$개의 문자열이 공백으로 구분되어 주어진다. 이는 종이 1에 적혀있는 문자열들을 뜻한다.

각 테스트 케이스의 넷째 줄에 $y$개의 문자열이 공백으로 구분되어 주어진다. 이는 종이 2에 적혀있는 문자열들을 뜻한다.

주어지는 모든 문자열은 알파벳 S,N,U,P,C만으로 이루어져 있다.

모든 테스트 케이스에서 $N$의 합은 10ドル^5$을 넘지 않는다.

출력

각 테스트 케이스에 대한 답을 한 줄에 하나씩 출력한다.

제한

힌트