Limits 1s, 512 MB

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 tt (t=100t = 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 nn (1n1051 ≤ n ≤ 10^5) 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.

In this version of the problem each cut can be made horizontally or vertically. That is, the two letters that describe each cut are either T+B or L+R.

Output

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

Sample

InputOutput
1

2
LB
TB
3

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.

Submit

Login to submit.

Statistics

70% Solution Ratio
mashfiqur404Earliest, Oct '19
mdshadeshFastest, 0.0s
mdshadeshLightest, 5.5 kB
user.2599Shortest, 3122B
Toph uses cookies. By continuing you agree to our Cookie Policy.