Illuminated Lights II

한 줄에 $n$개의 조명이 있으며, 처음에는 모두 꺼져 있다. 켜지면 자기 자신과 왼쪽의 모든 조명을 밝히는 조명이 있고, 켜지면 자기 자신과 오른쪽의 모든 조명을 밝히는 조명이 있다.

아래 그림은 첫 번째 예제에서 4번 조명만 켰을 때의 결과다. 1번부터 4번까지 조명이 밝혀지고, 나머지는 밝혀지지 않는다.

모든 조명을 밝히는 데 필요한 최소 조명 수는 이전 문제에서 이미 구했다. 이번에는 좋은 부분집합이 몇 개인지 센다.

조명의 부분집합 $S$에 대해, $S$에 속한 조명만 켰을 때 한 줄의 모든 조명이 밝혀지면 $S$를 좋은 부분집합이라고 한다. 좋은 부분집합의 개수를 구하라. 개수가 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10^4$)가 주어진다. 각 테스트 케이스의 첫 줄에는 조명의 수 $n$ ($1 \le n \le 2\cdot 10^5$)이 주어진다. 다음 줄에는 길이 $n$의 문자열 $s$가 주어지며, 각 문자는 L 또는 R이다. L은 왼쪽을 가리키는 조명, R은 오른쪽을 가리키는 조명이다.

모든 테스트 케이스의 $n$ 합은 $2\cdot 10^5$를 넘지 않는다.

각 테스트 케이스마다 좋은 부분집합의 개수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.

두 번째와 네 번째 테스트 케이스에서는 모든 조명을 켜야만 전체를 밝힐 수 있다. 따라서 이 경우 좋은 부분집합은 모든 조명을 담은 집합 하나뿐이다.

세 번째 테스트 케이스에서는 두 조명 중 하나라도 켜면 전체가 밝혀진다. 따라서 $\{1\}$, $\{2\}$, $\{1, 2\}$가 좋은 부분집합이다.