| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 8 | 7 | 7 | 87.500% |
There are $n$ lights in a row, all initially deactivated. Some lights, when activated, will illuminate themselves and all lights to their left. The others, when activated, will illuminate themselves and all lights to their right.
This image shows the result of activating the fourth light (and nothing else) in the first sample case. The first four lights are illuminated, and everything else is not.
You have already figured out the minimum number of lights that need to be activated to illuminate everything, but now, you're wondering how many good subsets of lights exist.
A subset $S$ of the lights is considered good if when you activate the lights in $S$ (and only the lights in $S$), every light on the row is illuminated.
How many good subsets are there? Since the answer may be large, output it modulo 10ドル^9+7$.
The first line of the input contains a single integer $t$ (1ドル \le t \le 10^4$) --- the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ (1ドル \le n \le 2\cdot 10^5$) --- the number of lights.
The next line of each test case contains a string $s$ consisting of $n$ characters L and R, indicating whether the lights are pointed to the left or right.
It is guaranteed that the sum of $n$ over all test cases does not exceed 2ドル\cdot 10^5$.
For each test case, print a single integer --- the number of good subsets, taken modulo 10ドル^9+7$.
7 6 LRRLRL 1 L 2 RL 2 LR 5 RRRRL 10 LRLRLRLRLR 31 LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
50 1 3 1 24 912 73741817
For the second and fourth test cases, the only way to illuminate everything is to activate every light. Therefore, for these cases, the only good subset is the set containing all lights.
For the third test case, as long as either of the two lights is activated, everything will be illuminated. Therefore, the sets $\{1\},ドル $\{2\},ドル and $\{1, 2\}$ are good.