Brain fold (Hard)

Shandyna loves nerd sniping. (Relevant xkcd) Don't worry, she only does it in safe environments.

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?

The first line of the input contains an integer $t = 100$, 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 $n$ ($1 \le n \le 10^5$), 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 that pick up the top, bottom, left, and right side, respectively. So T is the fold that places the top side over the bottom side.

The last line describes the cut. The cut never passes through a corner of the square. The number of pieces does not depend on the exact points where the cut meets the sides, so the cut is given only by the labels of the two sides it intersects. For example, TR is a cut that intersects the top and right sides of the folded paper.

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

The second test case is shown in the figure below.