SNUPC 문자열 (Hard)

시간 제한5초메모리 제한1024 MB

요약
S,N,U,P,C로만 이루어진 길이 N의 미지의 문자열에서 S나 N 앞, U나 P 앞에서 자른 조각들의 두 집합이 주어질 때, 두 집합을 모두 만들어 내는 서로 다른 문자열의 개수를 센다.
난이도

어려움10점 중 8점

유형
문자열, 동적 계획법, 조합론, 해시맵
정답자
아직 제출이 없습니다

문제

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

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

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

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

입력

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

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

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

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

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

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

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

모든 테스트 케이스에서 NN의 합은 10510^5을 넘지 않는다.

출력

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

예제1

  1. 예제 1

    입력
    2
6
3 4
S UN UPC
SU NU P C
5
4 2
US S U S
SSU SU
    예상 출력
    1
2