# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Brain Fold (Hard)

Shandyna loves nerd sniping.

(Don’t worry, she only does it in safe enviroments.)

Last time she got five of them at once. When I saw them, they were still sitting around, trying to imagine a folded sheet of paper.

You have a rectangular piece of paper. You fold it in half several times. For each fold, you pick up one side and place it over the opposite side. There are four sides to pick, so there are four ways to perform each fold. (Two of the folds are horizontal and two are vertical.)

Once you finish the last fold, you pick a straight line and cut along it, through all layers of the folded paper. How many pieces of paper will you have at the end?

### Input

The first line of the input file contains an integer **t** (t = 100) specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of three lines.

The first line contains a number **n** (1 ≤ n ≤ 105) denoting the number of folds.

The second line consists of n characters specifying the folds in the order they are applied: T, B, L and R represent folds for which you pick up the top, bottom, left, and right side, respectively. (Hence, T represents the fold that places the top side over the bottom side.)

The last line describes the cut. To make your life easier, the cut will never pass through a corner of the square. As it can be shown that the number of pieces does not depend on the exact points where the cut intersects the sides of the square, we can specify the cut simply by giving the labels of the two sides it intersects. For example, TR is a cut that intersects the top and the right side of the folded paper.

### Output

For each test case, output a single line containing x modulo 10^{9} + 7, where x is the number of paper pieces we’re left with after cutting the paper.

### Samples

Input | Output |
---|---|

2 2 LB TB 2 RB LT | 3 5 |

The second test case is shown in the figure below.

This IPSC problem is licensed under the CC BY-SA 3.0 license. The problem statement has been modified slightly to adhere to Toph’s style guide.

You can find the original problem in the IPSC archive.

The image in this problem statement is from Xkcd.

Login to submit