作者： chenchen

Farmer John's pasture can be regarded as a large 2D grid of square "cells" (picture a huge chessboard) labeled by the ordered pairs (i,j) for each 1≤i≤N, 1≤j≤N (1≤N≤150). Some of the cells contain grass.

A nonempty subset of grid cells is called "balanced" if the following conditions hold:

1.All cells in the subset contain grass.
2.The subset is 4-connected. In other words, there exists a path from any cell in the subset to any other cell in the subset such that every two consecutive cells of the path are horizontally or vertically adjacent.
3.If cells (x₁,y) and (x₂,y) (x₁≤x₂) are part of the subset, then all cells (x,y) with x1≤x≤x2 are also part of the subset.
4.If cells (x,y1) and (x,y₂) (y₁≤y₂) are part of the subset, then all cells (x,y) with y₁≤y≤y₂ are also part of the subset.
Count the number of balanced subsets modulo 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.
The next N lines each contain a string of N characters. The j-th character of the i-th line from the top is equal to G if the cell at (i,j) contains grass, or . otherwise.

OUTPUT FORMAT (print output to the terminal / stdout):

The number of balanced subsets modulo 10⁹+7.

SAMPLE INPUT:

2
GG
GG

SAMPLE OUTPUT:

13
For this test case, all 4-connected subsets are balanced.

G. .G .. .. GG .G .. G. GG .G G. GG GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG

SAMPLE INPUT:

4
GGGG
GGGG
GG.G
GGGG

SAMPLE OUTPUT:

642
Here is an example of a subset that satisfies the second condition (it is 4-connected) but does not satisfy the third condition:

GG..
.G..
GG..
....

SCORING:

Test cases 1-4 satisfy N≤4.
Test cases 5-10 satisfy N≤20.
Test cases 11-20 satisfy no additional constraints.
Problem credits: Benjamin Qi

Consider a network of N (2≤N≤100) nodes labeled 1…N. Each node is designated as a sender, a receiver, or neither. The number of senders, S, is equal to the number of receivers (S≥1).

The connections between the nodes in this network can be described by a list of directed edges each of the form i→j, meaning that node i may route to node j. Interestingly, all of these edges satisfy the property that i<j, aside from K that satisfy i>j (0≤K≤2). There are no self-loops (edges of the form i→i).

The description of a "routing scheme" consists of a set of S directed paths from senders to receivers such that no two of these paths share an endpoint. That is, the paths connect distinct senders to distinct receivers. A path from a sender s to a receiver r can be described as a sequence of nodes

s=v₀→v₁→v₂→⋯→v_e=r

such that the directed edges v_i→v_i+1 exist for all 0≤i<e. A node may appear more than once within the same path.

Count the number of distinct routing schemes such that every directed edge is traversed exactly once. Since the answer may be very large, report it modulo
10⁹+7. It is guaranteed that there is at least one routing scheme satisfying these constraints.

Each input contains T (1≤T≤20) test cases that should be solved independently. It is guaranteed that the sum of N2 over all test cases does not exceed 2⋅10⁴.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of the input contains T, the number of test cases.

The first line of each test case contains the integers N and K. Note that S is not explicitly given within the input.

The second line of each test case contains a string of length N. The i-th character of the string is equal to S if the i-th node is a sender, R if the i-th node is a receiver, or . if the i-th node is neither. The number of Rs in this string is equal to the number of Ss, and there is at least one S.

The next N lines of each test case each contain a bit string of N zeros and ones. The j-th bit of the i-th line is equal to 1 if there exists a directed edge from node i to node j, and 0 otherwise. As there are no self-loops, the main diagonal of the matrix consists solely of zeros. Furthermore, there are exactly K ones below the main diagonal.

Consecutive test cases are separated by newlines for readability.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, the number of routing schemes such that every edge is traversed exactly once, modulo 10⁹+7. It is guaranteed that there is at least one valid routing scheme for each test case.

SAMPLE INPUT:

2

8 0
SS....RR
00100000
00100000
00011000
00000100
00000100
00000011
00000000
00000000

13 0
SSS.RRRSS.RR.
0001000000000
0001000000000
0001000000000
0000111000000
0000000000000
0000000000000
0000000000000
0000000001000
0000000001000
0000000000110
0000000000000
0000000000000
0000000000000

SAMPLE OUTPUT:

4
12
For the first test case, the edges are 1→3,2→3,3→4,3→5,4→6,5→6,6→7,6→8.

There are four possible routing schemes:

1→3→4→6→7,2→3→5→6→8
1→3→5→6→7,2→3→4→6→8
1→3→4→6→8,2→3→5→6→7
1→3→5→6→8,2→3→4→6→7
For the second test case, the edges are 1→4,2→4,3→4,4→5,4→6,4→7,8→10,9→10,10→11,10→12.

One possible routing scheme consists of the following paths:

1→4→5
2→4→7
3→4→6
8→10→12
9→10→11
In general, senders {1,2,3} can route to some permutation of receivers {5,6,7} and senders {8,9} can route to some permutation of receivers {11,12}, giving an answer of 6⋅2=12.

SAMPLE INPUT:

2

5 1
SS.RR
00101
00100
10010
00000
00000

6 2
S....R
001000
000100
010001
000010
001000
000000

SAMPLE OUTPUT:

3
1
For the first test case, the edges are 1→3,1→5,2→3,3→1,3→4.

There are three possible routing schemes:

1→3→1→5, 2→3→4
1→3→4, 2→3→1→5
1→5, 2→3→1→3→4
For the second test case, the edges are 1→3,2→4,3→2,3→6,4→5,5→3.

There is only one possible routing scheme: 1→3→2→4→5→3→6.

SAMPLE INPUT:

5

3 2
RS.
010
101
100

4 2
.R.S
0100
0010
1000
0100

4 2
.SR.
0000
0011
0100
0010

5 2
.SSRR
01000
10101
01010
00000
00000

6 2
SS..RR
001010
000010
000010
000010
100101
000000

SAMPLE OUTPUT:

2
1
2
6
24

Some additional small test cases.

SCORING:

Test cases 4-5 satisfy N≤6.
Test cases 6-7 satisfy K=0.
Test cases 8-12 satisfy K=1.
Test cases 13-24 satisfy K=2.

Problem credits: Benjamin Qi

There are N cows participating in delegation selection (1≤N≤2⋅10⁵). They are standing in a line, and cow i has breed b_i.

The delegation will consist of a contiguous interval of at least three cows - that is, cows l…r for integers l and r satisfying 1≤l<r≤N and r−l≥2. Three of the cows in the chosen interval are marked as delegation leaders. For legal reasons, the two outermost cows of the chosen interval must be leaders. Moreover, to avoid intra-breed conflict, every leader must be of a different breed from the rest of the delegation (leaders or not).

Help the UCFJ determine (for tax reasons) the number of ways they might choose a delegation to send to the IOI. Two delegations are considered different if they have different members or different leaders.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.
The second line contains N integersb₁,b₂,…,b_N, each in the range [1,N].

OUTPUT FORMAT (print output to the terminal / stdout):

The number of possible delegations, on a single line.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

7
1 2 3 4 3 2 5

SAMPLE OUTPUT:

9
Each delegation corresponds to one of the following triples of leaders:

(1,2,3),(1,2,4),(1,3,4),(1,4,7),(2,3,4),(4,5,6),(4,5,7),(4,6,7),(5,6,7).

SCORING:

Test cases 1-2 satisfy N≤50.
Test cases 3-4 satisfy N≤500.
Test cases 5-8 satisfy N≤5000.
Test cases 9-20 satisfy no additional constraints.
Problem credits: Benjamin Qi