문제

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

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

모그는 두 종이에 적힌 정보를 바탕으로, 원래의 SNUPC 문자열 를 복원하고자 한다. 하지만 가능한 복원 형태가 매우 다양할 수 있으므로, 복원된 SNUPC 문자열로 가능한 것의 개수를 소수 으로 나눈 나머지를 출력하자. 원본 SNUPC 문자열은 한 개 이상 존재함이 보장된다.

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

입력

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

첫째 줄에 테스트 케이스의 개수 가 주어진다.

각 테스트 케이스의 첫째 줄에 양의 정수 이 주어진다. 이는 원본 SNUPC 문자열의 길이를 뜻한다.

각 테스트 케이스의 둘째 줄에 양의 정수 가 공백으로 구분되어 주어진다.

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

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

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

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

출력

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

노트

첫 번째 테스트 케이스에서 원본 SNUPC 문자열은 SUNUPC만 가능하다.

두 번째 테스트 케이스에서 원본 SNUPC 문자열은 SSUSU, SUSSU가 가능하다.