monopoly

Problem Description

Bored cats play board games. Rar the cat is a bored cat. Monopoly is a board game. Therefore, Rar the cat plays monopoly when he is bored.

But what if Rar the cat gets bored with playing board games? He turns it into a programming problem!

Given a monopoly board of size N squares by N squares, he wants to know the number of ways to land on a certain square of the board during the first round around the board, without passing the start square again. (This means that landing on a square after passing one full round is NOT counted.) In order for a player to advance to another square, the player has to roll a 6 sided dice which has values of 1 to 6, the player will then advance the corresponding number of squares. (Eg. If the dice roll is 3, the player will advance 3 squares from A0 to A3) Monopoly boards have 4 sides, with the first side labelled A, second side labelled B, third side labelled C and the last remaining slide labelled D. The 'GO!' start square where all players start would be labelled A0. The first square after that would be A1, then A2 ... A(N-1). The corners would have 2 different labels, A(N-1) would be the same as B0, B(N-1) would be the same as C0 and C(N-1) would be the same as D0.

 N = 5 monopoly board labels:
 
| A0/D4 |  A1  |  A2  |  A3  | A4/B0 |
|  D3   |                    |   B1  |
|  D2   |                    |   B2  |
|  D1   |                    |   B3  |
| C4/D0 |  C3  |  C2  |  C1  | B4/C0 |
 

Input

The first line of input would be a single integer, TC, denoting the number of testcases that follows.

Subsequent TC lines of input would consist of 3 part each: N, S and X. N is an integer denoting the number of squares per side for the monopoly board of that testcase, S is either 'A', 'B', 'C' or 'D' where as X is an non-negative integer < N. S and X together describes the square Rar the Cat is referring to for that particular testcase.

Output

For each testcase, output an single integer on a single line which denotes the number of ways to land on that particular square Rar the Cat is referring to, modded by 1000000007 (remainder when divided by 1000000007).

Do note that you should mod 1000000007 at every intermediate step (multiplication or addition) in order to prevent overflow, since ((A % M) + (B % M))% M = (A + B) % M and ((A % M) * (B % M))% M = (A * B) % M. You may seek clarification regarding this if you do not understand.

Limits

Subtask 1 (14%): N = 5, TC = 100000

Subtask 2 (17%): 2 ≤ N ≤ 1000, TC = 10

Subtask 3 (10%): 2 ≤ N ≤ 1000, TC = 100000

Subtask 4 (26%): 2 ≤ N ≤ 100000, TC = 10

Subtask 5 (33%): 2 ≤ N ≤ 100000, TC = 100000

Subtask 6 (0%): As per sample testcases

Sample Testcase 1

Input:

20
5 A 0
5 A 1
5 A 2
5 A 3
5 A 4
5 B 0
5 B 1
5 B 2
5 B 3
5 B 4
5 C 0
5 C 1
5 C 2
5 C 3
5 C 4
5 D 0
5 D 1
5 D 2
5 D 3
5 D 4

Output:

1
1
2
4
8
8
16
32
63
125
125
248
492
976
1936
1936
3840
7617
15109
1

Sample Testcase 2

Input:

10
365 C 273
827 A 826
2 D 0
999 B 717
812 C 309
315 B 116
111 D 0
37 A 0
87 A 53
682 D 572

Output:

94201505
487685260
4
461898741
351974960
253165884
283609775
1
812746348
939142440