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 |

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.

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.

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

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

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

Subtask | Score |
---|---|

1 | 0 |

2 | 14 |

3 | 17 |

4 | 10 |

5 | 26 |

6 | 33 |