34565번 - 향유회 문자열

문제

두 문자열 $A,ドル $B$에 대해 $A+B$를 $A$와 $B$를 이어 붙인 문자열이라고 하자. 이때 다음과 같은 규칙으로 만들 수 있는 문자열을 향유회 문자열이라고 한다.

• 빈 문자열은 향유회 문자열이다.
• $A,ドル $B$가 향유회 문자열이라면, H$+,円A,円+$Y$+,円B,円+$H도 향유회 문자열이다.
• $A,ドル $B$가 향유회 문자열이라면, $A+B$도 향유회 문자열이다.

H, Y, ?로 이뤄진 문자열 $S$이 주어진다. $S$의 ?를 각각 H또는 Y로 바꿔 만들 수 있는 향유회 문자열의 개수를 10ドル^9+7$로 나눈 나머지를 구하여라.

입력

첫째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$가 주어진다. $(1 \leq T \leq 1\ 000)$

각 테스트 케이스의 첫째 줄에 문자열의 길이를 나타내는 정수 $N$이 주어진다. $(1 \leq N \leq 5\ 000)$

각 테스트 케이스의 둘째 줄에 H, Y, ?로 이뤄진 문자열 $S$가 주어진다. $(|S|=N)$

모든 테스트 케이스에서 $N$의 합은 5ドル\ 000$ 이하이다.

출력

각 테스트 케이스마다 정답을 출력한다.

제한

힌트