Carcassonne

Carcassonne is a tile-based board game for two to five players.
Square tiles are printed by city segments,road segments and field segments.

The rule of the game is to put the tiles alternately. Two tiles share one edge should exactly connect to each other, that is, city segments should be linked to city segments, road to road, and field to field.

To simplify the problem, we only consider putting tiles:
Given n*m tiles. You can rotate each tile, but not flip top to bottom, and not change their order.
How many ways could you rotate them to make them follow the rules mentioned above?

The first line is a number T(1<=T<=50), represents the number of case. The next T blocks follow each indicates a case.
Each case starts with two number N,M(0<N,M<=12)
Then N*M lines follow,each line contains M four-character clockwise.
'C' indicate City.
'R' indicate Road.
'F' indicate Field.

For each case, output the number of ways mod 1,000,000,007.(as shown in the sample output)

3
1 1
RRRR
1 2
RRRF FCCC
8 8
FCFF RRFC FRCR FRFR RCCR FFCC RRFF CRFR
FRRC FRFR CCCR FCFC CRRC CRRR FRCR FRFR
RRCR FRRR CCCR FFFC RRFF RFCR CCFF FCCC
CFCF RRFF CRFR FFRR FRRF CCRR FFFC CRRF
CFRR FFFF FFFF RRFF RRRR RCRR FFCC RFRF
RRCF FRFR FRRR FRFR RCCR RCCC CFFC RFRF
CFCF FRFF RRFF FFFF CFFF CFFF FRFF RFRR
CCRR FCFC FCCC FCCC FFCC FCCF FFCC RFRF

Case 1: 4
Case 2: 1
Case 3: 1048576

The 36th ACM/ICPC Asia Regional Fuzhou Site —— Online Contest