Brain fold (Hard)

Shandyna는 nerd sniping을 좋아한다. (관련 xkcd) 걱정하지 마라. 그녀는 안전한 환경에서만 그렇게 한다.

지난번에는 한꺼번에 다섯 명을 sniping했다. 내가 그들을 봤을 때, 그들은 여전히 그 자리에 앉아 접힌 종이를 상상하려고 애쓰고 있었다.

직사각형 종이가 한 장 있다. 이 종이를 반으로 여러 번 접는다. 접을 때마다 한쪽 면을 집어서 반대쪽 면 위에 올린다. 집을 수 있는 면은 네 개이므로 한 번의 접기에 방법이 네 가지 있다. (가로로 접는 방법이 두 가지, 세로로 접는 방법이 두 가지이다.)

마지막 접기를 마친 뒤 직선 하나를 골라 접힌 종이의 모든 층을 관통하도록 자른다. 최종적으로 종이는 몇 조각이 되는가?

첫 줄에는 테스트 케이스의 개수 $t = 100$이 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.

각 테스트 케이스는 세 줄로 이루어진다.

첫 줄에는 접기 횟수 $n$ ($1 \le n \le 10^5$)이 주어진다.

둘째 줄에는 접는 순서대로 $n$개의 문자가 주어진다. T, B, L, R은 각각 위, 아래, 왼쪽, 오른쪽 면을 집어서 접는 것을 뜻한다. 즉 T는 위쪽 면을 아래쪽 면 위에 올려 접는 것이다.

마지막 줄은 자르는 선을 나타낸다. 자르는 선은 정사각형의 꼭짓점을 지나지 않는다. 조각의 개수는 선이 변과 정확히 만나는 점에 따라 달라지지 않으므로, 자르는 선은 교차하는 두 변의 이름으로만 주어진다. 예를 들어 TR은 접힌 종이의 위쪽 변과 오른쪽 변을 지나는 선이다.

각 테스트 케이스마다 한 줄에 $x$를 $10^9 + 7$로 나눈 나머지를 출력한다. 여기서 $x$는 자른 뒤 남는 종이 조각의 개수이다.

두 번째 테스트 케이스는 아래 그림과 같다.