TopCoder Statistics - Problem Statement

Problem Statement

For each positive integer k, you have an infinite supply of dominos of shape 1 * k. Each domino can be placed either horizontally or vertically.

You have a rectangular board. Some cells of the board are already covered by 1 * 1 dominos, the rest is empty. You are given the description of the board in the String[] T . The character '.' represents an empty cell, the character '#' a cell that is already covered.

Find the number of different ways in which the entire board can be exactly covered, modulo 10⁹ + 7.

Definition

Class:: DominoPlacement
Method:: countWays
Parameters:: String[]
Returns:: int
Method signature:: int countWays(String[] T)
(be sure your method is public)

Notes

A board is exactly covered if each cell is covered by exactly one domino, and each domino is completely inside the board.
Two coverings of the board are different if there are two (not necessarily distinct) cells P and Q such that in exactly one of the two coverings there is a domino whose ends cover P and Q.

Constraints

All strings in T will have the same length.
Each character of each string in T will be '.' or '#'
The total number of characters in T (i.e., the area of the board) will be between 1 and 300, inclusive.

Examples

{".."}

Returns: 2

One can either use a single 1 * 2 domino or two 1 * 1 dominos, giving 2 different ways.
{".#", ".."}

Returns: 3

If we keep a 1 * 1 domino at the top left cell, we have 2 ways to fill the bottom two empty cells like in the last test. If we place a vertical 1 * 2 domino instead, we must place a 1 * 1 domino at bottom right cell. The total number of ways is therefore 2 + 1 = 3. All three tilings are shown below (with different letters representing different dominos). A# A# A# BC AB BB
{".#.", "#..", "..."}

Returns: 20
{"#######.#####", "...#....#....", "...#....#....", "...#....#....", "...#....#####"}

Returns: 426089093
{"#.##..##..##.#..#..#.##..###...","##...##..##..#.#...#####...###.","..#..###..#.....##.####...##..#","#..#.###.#..#...#....##...#####","..##....#.##.#.#.###..#.#.####.","#.##..##..##.#..#..#.##..###..."}

Returns: 886860454
{".#..#####",".#.##..#.","##..#####",".##....#.","..#.##.#.",".##.###.#",".##.#.#..","####.#.##","####.#.##","####.##..","##.#...#.","##..#..#.","#.###....",".#..#####"}

Returns: 843386712
{".###.#..###..#.#....##...###...#.###.",".........#.#.#...##.....#..#.#.#.##..","#.##..##.#..#.....#.#.##..#..#.##....","...#######..##...#.##......###..#....",".###.#..###..#.#....##...###...#.###."}

Returns: 116253651
{".","#",".",".","#","#","#",".","#","#","#",".",".","#","#",".","#","#","#","#","#",".",".","#",".","#","#",".",".","#",".",".",".",".",".","#",".",".",".","#",".",".",".","#","#","#","#",".","#","#","#","#",".","#","#",".","#",".",".","#","#","#","#","#","#","#","#","#","#","#",".","#","#","#","#","#",".","#","#",".","."}

Returns: 16384
{"####..#...","...##...##","..#..#..#.","##.###..##","#.####...#",".##..####.","......#.#.","..###.##..","#.#.......","####..#..."}

Returns: 159225652
{"##.##.......##...","...#...#.#...#...","...##....##.#.#..","##..#...#......#.",".##..#.....####.#","#.....##..#.....#","..##..##.#.#....#","..#.#####.#.#..#.",".....##..#......#",".#...#...#.#...#.","#.......#...#..##","....##.##.....##.","#.##..#..#.###..#","##.##.......##..."}

Returns: 635406564
{"#..#.....#.#.#....##","#....#..........#.##","#.#..####.####.#....",".......#.#..##..#.#.","#.##.##........#....","............##..#.#.","##..#.#..#...#.....#","#........#.##...#...","...#...#....##.##.##","...#....###.......#.","#..#.....#.#.#....##"}

Returns: 131736292
{".##..","#...#","..##.",".#..#","#...#","###..","##.#.",".#...","...#.","..#.#",".##.."}

Returns: 4492800
{"..##.#..#....#",".#.#...#...##.",".##..........#",".###........#.","#.......###...",".#....#..#..#.","###.#.#####...","....#.#...#...",".##.......#..#",".##.###...#...","....#.......#.",".##.#.##......","............##","....#.##......","....##.#..#...",".##.....###.#.","..#....#....#.","....#..##.#.##",".####...#...#.","#..#....##.#..","..##.#..#....#"}

Returns: 672540306
{"...#.#............#......#....###.........###.######.#..##...###...#."}

Returns: 179869065
{".#....#.#.#..",".###....#....","..........###","#.#....#..#..",".......#.....","..##.#.....#.","....#........","..#........#.",".....#...#...",".##.....#..#.",".............","#........##..","#.##.##..#...","..#..........","........#....",".#....#.#.#.."}

Returns: 163078873
{"......#....##.#.#..#......##.....#.#","#...##..#....#...#.#......#...#...#.","..#........#...........#...#..####.#","......#....##.#.#..#......##.....#.#"}

Returns: 22985525
{".....#..##","#.#...##..",".........#","#.........",".....#..##"}

Returns: 104322938
{".",".",".","#",".",".","#",".","."}

Returns: 16
{"..#..#.#...###.#.","...#...#.##..#...","#................","......#.......##.","..#.#....#...#...","..#..#.#...###.#."}

Returns: 66380185
{"#....#...........","......#.#........","#....#..........."}

Returns: 693496844
{".............#..##...#....#....#......#.#.....#...#..##....#..",".##.##....#.....#...#.#....#...#....#.....#..###....#.#.#..#..","..#.#.....#.#.......#..#......#.....##...#.#..##.#..#.........",".............#..##...#....#....#......#.#.....#...#..##....#.."}

Returns: 584201107
{"....#.#......",".#..#........","##....#......","....#.#......"}

Returns: 685675491
{"....#...#.#.............",".......#........##......",".....#.#................","..........#....#..#.....",".....#.##..#........#.#.",".#.....#.#............#.","....#...#.#............."}

Returns: 953339831
{"..##.....",".........","..##.....",".........",".#..#...#",".......#.",".....#...","#...#....",".........","..##....."}

Returns: 126738837
{".........#.#..","......#.......",".....#..#.....","..............","..............",".#...#........","..#...........",".#..##........",".....##.......","..#.....##....",".........#.#.."}

Returns: 831888675
{".",".",".",".",".","#","."}

Returns: 16
{"............#.......#..#...#........#...#..................#.......#......#.....................#........#........#.......#........##."}

Returns: 621940455
{"...................................","...................................","............#.....##......#........",".#..........#............#.........","............#...........#.....#...#","#............#........#...#..#.#...","..................................."}

Returns: 33170905
{"..#....#.##.","............",".......#....",".#..........","..#........#","#.......#...",".........#.#",".#..........","#..#...#....","....##......",".#....#.....","..#.........","......#.....","#...........","............","............","..#....#.##."}

Returns: 143643148
{".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."}

Returns: 33554432
{"....","....","....","....","....","....","....","....","....","....","....","....","....","....","....","....","....","....","...."}

Returns: 536126084
{".......................",".......................",".......................",".......................",".......................",".......................",".......................",".......................",".......................",".......................",".......................","......................."}

Returns: 138810801
{".......................",".......................",".......................",".......................",".......................",".......................",".......................",".......................",".......................",".......................",".......................","......................."}

Returns: 138810801
{"...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","...","..."}

Returns: 523514052
{"...#..##.##.###.#","..#...#.####...##","#..########...###",".#..#.#.##.###.##","##.........###.#.","####.#####.##....","...#..##.###.####","#.#...#....#..#.#","###.#...#.###....","#....##...#....##","#####....##..#...","...#..#..###.####","..##...#.#..#..##","..#..#.##.#.#.###","#.#.##....##..#.#","..###..##..##.#..","...#..##.##.###.#"}

Returns: 466605518
{"##...##...##...##","##...###...##....","##.##..#..#....#.","....####.#.####..","##...#.#######.#.",".#...#..#..##.###",".....###.#.......","#..#######.###...","#..#.###.....##..","##.....########.#","##.#.#.#..####.##","#....#.##...##...","#...#.#.#####....",".##.#.....#..#..#",".##..#######.....","#..##..#..##.####","##...##...##...##"}

Returns: 120556781
{"...###..#####...#",".#..##.#.#..#..##","#..#...#.#..#...#","....###..###...##",".#..#####.#...##.","##..#..#......#..","#.#..##..#....###","..#..##.####..##.","..##.#.###.####.#","#....#...##.#..##",".#...#...#.#...##","###.##.###..#....","#...#.#.##..##.##",".#..##.####..##.#",".#.#.###..#.#..#.",".#.##...###.#..#.","...###..#####...#"}

Returns: 306626254
{"##.##..##.##.###.","###..#...#..##.#.",".#..###.#..#..##.","..##...##.#...##.","#..###.#.####.##.","##..##.###..#..#.",".#.#..#...#..#...",".#.#.###..####...","#..#...##...#..#.","..#..#....#.....#","#.#.#..##.#.#..##","#.##.##..#.##.###",".#.#...#...#.....","##.#####.......#.","##..#..#..#.##.#.","..#.....##.#..##.","##.##..##.##.###."}

Returns: 660068704
{"..#..###.#####...",".###.....#.#.###.",".#####.#.##.#.#.#","#.#.#.#.##.##....","###.####.##.#..#.","##..##.#.#.##.##.","..#####.#.##.#.##","####..##..##.###.","...##.##.#..##...","#..#.#.#.##....##","#..#..#.#.#.####.",".#.....#####.....",".#.#.#.#.#.#.##..",".#.##.##.##.#.###","#...#..#.#...#.##","....#.####.#...#.","..#..###.#####..."}

Returns: 541721477
{"#.##..#.#...####.","#.##..#.###..####",".###.##..#..#.###","..####.###....#.#","##.#..#..#....##.","#..#######..#.###","#.....#...##.....","#.##..#.##..#.#..","#.#.#.##.####....",".........#.#.#...","#..##.#.#...##.##","...#####.#.##..##",".#.##.#.#.##.####",".#.#......######.",".##.....######.#.","..#..#.#.####.#..","#.##..#.#...####."}

Returns: 707414333
{"###.##....#.#....",".###.#...###.#..#","###.#.###..#...#.","#.#..##..##......",".#####.###..###..","..###.#.##.#..#.#",".###.##..#.#..###",".#...###.#.##....","##..#...##.##..#.","..##..##..##....#",".#..#.#.#.#..####","#..##.#.##..#.#..","#.####.######.#..","#........###..###",".#.......#...#...","#.....###..###...","###.##....#.#...."}

Returns: 560810718
{"#.#.....#.###.##.","##.#...####......","#####...##..###.#",".#.......##.#####",".##.....#...#.##.","...#.#.#.#......#","#.#..##.#...#.#..",".###.#####....##.",".#..#.##.##.#....",".############.##.","..#.#####...#.##.","#..##..##.##.#.##",".#.##.#.##..#....",".#.#.#.#....##..#","##.##.#....##....","##........##...##","#.#.....#.###.##."}

Returns: 967072024
{"###.#.####..#.##.","..##...#.###..#..","#.###.#.....####.","#.#.##.#.##.....#","#.##.#.#...##..##","#.##..##..#.##..#","..#####.#..#....#","..##.######.###..","###......#.....#.","...#..#.#...####.","#..#.#.#.#.....##",".#.####....##.#..",".##.#......#.#...","##.#.####...#####","##..##.####.####.","...#...#####.#..#","###.#.####..#.##."}

Returns: 336999139
{"#..##.#.##.#...##",".#.#.......#.###.","##.##.##.####.###","#.#.##.###....##.","#.##.##.#.....#..",".####.##.###.#..#",".#..#####..#####.","..#..#.#.##....#.",".#.#.#...##.##..#","...#.##.##.#.....",".....##....#.###.",".#.#.###.#..##..#","....#..#.......##","#...#.#.##..##...",".#....#####.##.#.","#####.###.##.#..#","#..##.#.##.#...##"}

Returns: 475323904
{"..#.#...#####.##.","##...#.#########.","##...##.####.#...","#.##..##.#..##.##","..#...##..###..#.","##.#...#.##...#..","##.....##.#.#.###","##.###.##....#...","...###...#####...",".#.#....#.#..#...","....#.##..#..#...",".#######...#.#.#.",".#.#...##...##.#.","#.#..###...#.#..#","..#.##.######.###","#.#.#...#.###.###","..#.#...#####.##."}

Returns: 55978255
{"#..#........###.#",".##..#.#####...#.","##..#####..##...#","....#.#.##....#..",".##.#..##.#....##","#..##...##....#.#","###.########.####","...##.##.#..##.#.","#.#..####.#.##.##","#.#.##..#..#.##.#",".#.###.##.#.#....","..##.###...###.##","###..##..#.#.....","##.#.###......#.#","#.....#....#..##.","....##.#####.##..","#..#........###.#"}

Returns: 695193577
{"#####..###.....#.",".####.##..#.##...",".##..#.##...###..","#.#..#....##.##.#","#.#.#.#.....##..#",".#....#.##.##.###","..##.#.##.#####..",".###.#.#.##..###.","##.##..#..#..####","#.#..#..##..####.","##.#..##..#...#.#",".......###.....##","#..#.#....#.##..#","#.#..##.....###.#","....#...##..##...","#..#..#.#.#..##.#","#####..###.....#."}

Returns: 74075695
{"..#####...#.#.###","#.#.##.#...#####.",".#.#.##.##....###",".###.###.#.######",".#.#..#...###.###","....#...#.####...","##..#.....##..#.#","..####..#..#..##.","...##..#.####....","#......##...##..#","#.....#..#####..#",".#.#.#.#..#.#..#.","##.#..#....####..","#####.....##..##.","..######..#.##.##",".###.....###.##..","..#####...#.#.###"}

Returns: 168830230
{"#..#####.#..#..##","..##.....####.##.","####.#.#.#.#.#.#.",".#.#.#.###.###.##","....#...#####.##.","..##.###..#...##.",".###..#...##..###","###.#....#.#...##",".#..#..#...#....#",".....#.........#.",".#.#.#..###.##.##","####.#.##.....#.#",".##.....#..#..###","........####.#.#.",".#....#.#.#..##.#","..##.##.#........","#..#####.#..#..##"}

Returns: 761190794
{"#.#.##..#.#..#..#",".#...#.#...#.....","......#.#......##","..###...#...#...#","#....##.##.##...#",".....##..#....#..","..#.....#...##...","..#....##...#.#..","..#...#...#....#.",".........###..###","...#.......##.#.#","...#.#..###.##...","#.......#..##....","##.#....##..#....","#....#.#.#.......","...#..#..#.###.#.","#.#.##..#.#..#..#"}

Returns: 33155118
{".###..#.#.....#..",".#..#...#...#....","##.....#..#.####.","#......##..#.....","#....###.......##",".#.#...#...#.....","..........#..#..#","#....###.#..#.#.#","..#.#.##.#.#..##.",".........##.####.","..#..#...####.#..","....###....##....","#.##..#..#.#...#.","...#.#####.#..#..","....#....##...#..","#...#....#.......",".###..#.#.....#.."}

Returns: 357463056
{"##..#.......##...",".....#..#...#.###","......#...#.###.#","..##.#....#.#..#.","#..#...##........","..##............#","...#.....###...#.",".##.###.#...#.###","##.##......#..#..","...##...#.....#.#",".#.#....###.#..#.",".#....#..##...#..","..#........#.....","..#...#.#..#.....","##.#..#.#...#..#.",".###......##...#.","##..#.......##..."}

Returns: 625720896
{"...#...#......#..",".....#.#.#####..#","##.##.....#....#.","#.####..#.......#","....#..#.#...#...","#...#.....#......",".##...#...#......","..#.###...##...#.",".###.......#..##.","#...#.##..##..#..","....##..#......#.","#....##.##...###.","#..##.##..#.##.##","..##.....#.#....#","#.###.##.....#...","#....##..#.....##","...#...#......#.."}

Returns: 270797425
{"#..#.###..##.#...","..#.##..#.##.....","...#..#..##.....#",".....###......##.",".#...#.###...##..","....#....#.#.....",".###......#.##.#.","......#.....##...","#.#.#..#........#","....#....##..#.#.","##..##.#...#.#..#","#..##..#.##......",".#..#..#...#..##.","#.....####.#..#..","#.##....###.#...#",".....##..#.....#.","#..#.###..##.#..."}

Returns: 958775587
{"..........#..##..","#.##..##.#....#..",".##.#.##.........",".##.##....#....#.","#...###.#.#....#.","#..#.##...#...###",".#..####..##..#..","...##..##.#.##..#","...#............#","#.##....##......#","####.#.#.###.#..#",".#.####.##.###...",".#...#....##.#.#.","..#.....#........","#....#..#.#....##","#.......##....#.#","..........#..##.."}

Returns: 521758034
{"....##...##.##.##","..#.....#.#..#.#.",".#..##.#.....#...","..#......##.#.##.","#.......#........","....##.#.##.#....","..###..#..#..#..#","######.....#.#.##",".#.#..#..##...#.#","#.....#.##.##.#..",".#.#.#...#......#","#.##...#...#.#...",".#.......#.#.##.#","....#.#....##....",".#....#.#..#....#","###...##....#....","....##...##.##.##"}

Returns: 543889464
{"#.###..##...##.##","#.#.....#..#.#...","...#.##....####..","...#...#..#....#.",".#.##.###.##.#...",".#.....##..#.##.#","..#.#.#..#.#.###.","#.##.......##..#.","##....#....#..##.","#.#..#..#..##..#.",".##.......#......","##.##............","....###........#.","..####...#####..#","#....##..#.....#.","......#..#..##...","#.###..##...##.##"}

Returns: 395404613
{".#...###..##.#...",".#..#...#.......#","###....#...#.#..#",".##....#.##..#.#.","#.....###.#......",".##.....####...#.","#...#.##.#..#...#",".##.#.#.###..#...",".####.##......#..","###.###....##...#","#...#...#........","#.......#.#.###..","###.#......#.....",".....#....#.###.#","#...##...........","#.#.##.##.#.#..##",".#...###..##.#..."}

Returns: 866273226
{"#....#....##..##.","...#....#..#.#...","....###.....#....","#....#.#...#.#...",".....#..#....#...","....#...##..#....","...#.#..###.#.##.","#.............#..","......#..........","#.##...#...##.##.",".##..........#..#",".#...#...##.###.#","#..##..#.#...####","#...#.#...##...#.","##...#......#.##.","#.............#..","#....#....##..##."}

Returns: 230658952
{".#...#.....#.##.#",".....#...##...#.#","##..#..#......###","##.##.........#..",".....##.##.......","..#.....#.#.#....","...###.......#.#.",".#.#.....##....#.","#.#.####......##.","..##.#.#....##...","....#....#.#..#.#","#....###.........","..##.#.#......#..","..##....###.#.#..",".#...#....#......","###.##.####.#.#.#",".#...#.....#.##.#"}

Returns: 276879956
{".##.............#","#...#..#...#.....","#...####.#.......","..#.....#....#.#.","....#...#.#......",".#.##.###...#..#.","...#........#.#.#",".......#.#...##.#","#....#.#....#.#.#","##.....##.##.#.#.","##..##..##...#..#","..#..#...##.....#","...#......##..#..",".###....###...#..","..#........##....","#.#...###.#...#.#",".##.............#"}

Returns: 955078269
{"##..#...#....#...",".##........#.###.","#....#.......##..","##...#.#....#.###","###...#...#.##.#.",".##.#...#......#.","..#.#....###.#.##","...#...##.#.#....",".........##.###.#","...#......#.##.##","....#####...###..",".#.#####..#..#..#","..#..#..#..#...#.","....#....##.#....",".#...#..#.#.#..#.",".#....#...#.....#","##..#...#....#..."}

Returns: 765494971
{"#.###.##.##.##..#","###.....#.#....#.","....###..#...#...",".......#....##..#","..#..#.#...#.#...","#..#..#.#........",".##.#.#.#.#.....#","...###..#..#..##.",".#.......###.##.#",".##...#..###....#","..#......#.###.##","...#.###......#..",".##..#.#.#.#....#","#.#..#.........##","......##.#.......","......#..........","#.###.##.##.##..#"}

Returns: 331350785
{"....#..#.#...#.#.","..#.##.....##..#.",".#.......##.##...","#..##...#....#...","....#.......#.##.",".#.##.........#.#",".......##.#...#..",".#..##..#..#..#.#","..##...#.#..#....",".#....##..#..##.#","#........##.#....","#....#...........",".....#.......#.#.",".......#.........","....##....#......","#...##..#..#....#","....#..#.#...#.#."}

Returns: 399246334
{"#..#.##....#.#...","....###.......#.#",".#...#.#...#....#",".#.....#.#.#...#.",".##....#....#..#.",".....##........##","......##.........",".#....##.....#.##",".#.......##......","...###.##.#.....#",".#......#..#.##..","#...###..#...#...","....##...#.....#.","..#....#.#.......",".#...#........#..",".......#........#","#..#.##....#.#..."}

Returns: 953937438
{".......#.#......#",".#......#...#.#..","##...#...#..#....",".#.......##.#..#.","......#......#.##",".#.............#.",".#...#.#.....#...","##...##..........",".....#....#..##..","#.........#......",".......#...##....",".#...#.....##....","#..##.#.......#.#",".#....#...#......",".............#...",".......#..#...#..",".......#.#......#"}

Returns: 455778101
{"..#..............","...#...###.#.#...","#..#.#....#......","...#.#......#....","..#.........#..##","#.......#..#.....","..#.#..#.#.......","..#............#.",".#......#........","......#..........","#......#....##.#.",".#.....#..#.##...","....##..#..#.....","....##...#.#.##..","...#......#.####.",".#.#.......#..#..","..#.............."}

Returns: 116226925
{"..#............##",".........###...#.",".#....#..#....#..","........##...##.#","..#..#.#.........","##..#.#.##.....#.",".#...#...#.#.....",".#........#....##","##..#............","..#.###..#.#...##","..##..#........#.",".#.##...#......#.","...#.......#.....","#.#.###.......#..","..#......##..#.##","..###...........#","..#............##"}

Returns: 858630756
{".........##.....#",".........#....#..",".##......#....#.#",".###..##.#.##....",".....#......#..#.","#.#...#.........#",".....#.....##....",".###.#.......#.##","##.......#.#.....",".#......##..##...","#.#....##........",".....##..#....#..",".#..###....##.###",".......#..##....#","...##.#..##.###..","#.#..#....##....#",".........##.....#"}

Returns: 688669305
{".#.#......#..##..","#...............#","..#.##..##...#...",".......#....#....","..#.....#........","....#....#...##.#",".#..##......#.#..","#.#.#..##.......#","#..#.##..........",".#...#.##.#......",".....#....##.#...","......#.#..#.#.##",".#....#...#..#...","...#..#......#...","#..#.##.....#.#..","...#....#.#......",".#.#......#..##.."}

Returns: 211303695
{".#...##...##.#...","....#....#.#...#.","....#.#..#..#....",".#..#............",".#..#............","...##..#..#...##.","##.##....##......",".##.......#.##...","....#.#...##...#.","........#...#...#","....##.........#.","###..........#..#","#.....#.#...#.#..",".#.#...#.....#...","##...##.......###","...##..#....#..##",".#...##...##.#..."}

Returns: 475449139
{"..#....#.........","........#...#....",".####.#.#.###...#","......##....#....",".....#.........#.","...#...........##","#............#..#",".#..##.#..###.#..","#.##..#.....#.#.#","........#.##.....",".##...###..#.....",".#.##...#........","#.#......##.##...","...............#.","...#.....#..##...","....#####........","..#....#........."}

Returns: 659799268
{"##...#.#.........","......#.....#...#","#.........###.#..",".##...##.#.##..##",".##...........#..","..#..#.#.##...#.#","#........#..#.#..",".##...##.....#..#","#........#....###","#..#.##.......#..","....#..#...#...#.","#....##...#..#...","......#..#.......","..#..#...........",".......#..#......",".#.#...#...#..##.","##...#.#........."}

Returns: 700850599
{"..##.##..#.......","...##....#.#..#..","#..#....#..#....#","#.....#.....#....",".....#.#.#.#....#","....##.###...#...","..#........#.....","............#....","#...#..#.....#...","#..#...#...#.#...","......##.#....##.","#......#.#..#....","...#.##...#..#...",".....#...#.......","....#.#..#.......",".#.....##...####.","..##.##..#......."}

Returns: 250475099
{".......#.........","#...#...#....#...","...#....#...##.#.",".###..#....#...#.","..###.....#.#....",".#.#.###.#.....#.","...#...#..#..#...","..##...#....#..##","#.#.........#.#..","......#..........","#.........##...##","#....#......###..","..#...#....###..#","#..#.#...#.#.#...","...#..#..........","....#....#.......",".......#........."}

Returns: 120645246
{".......#...#.....",".......###.#.#...","..##........##...","......#...#..#...","#....#.....#.#..#","...#....###......","#..##.#.#........",".#...#.##..###...","....##.#...###...","...#.......#..#..",".............#...","###..........##..","..#.....#.###..##",".........#.##..#.",".#.......#.....##",".##...#.#..#..#..",".......#...#....."}

Returns: 949683703
{"#......##.......#","...#...##........",".#..#...#.....#..","......#..#.#.....","#....#......#....",".#..##.##.....##.",".............#..#","...#.##......#...","..#..#.#.##...#.#","...#.#.#...#.....",".#.#..#....#..###","####..#...##.##..","#...#...#........","..##.#..#...#...#","##..#...#..#..#..","#....#...........","#......##.......#"}

Returns: 491230300
{"...#.#.........##","...###...#.#..#..","..##.....#...##.#","........#.....#..",".#..#......#....#","#....#.#.#.#.....","#..#.#.#.........",".#.#..##......###","......#.#........","#.##........##...","#.....#...##..##.","..#.....#......##",".........#..#..#.","#.#....#.........","...##............","...###..##...####","...#.#.........##"}

Returns: 434338811
{"#...........#..#.",".....#......##..#","##....#...#...#.#",".#.....#.........","#..#....##...##.#",".##....##..#..#..","#...####..#.#.#..","##..............#","#..#.........#...","#..#..##.#......#","#...##..#.......#",".....#..#.##...#.","...#.#.#......#.#","#.......#.#.#..#.",".#..#......#....#",".............####","#...........#..#."}

Returns: 707310325
{"....#....##..#..#","........#........",".#......#..#....#","###..#.#..#.....#",".#......#.#..#...","##...#.#.....##..","#.........##.....","#................","..........#.##...","....#....#...#.#.",".......#....#..##","...#..#..#.......","#...#...###..#..#","...##......#....#","#.#.#...#........",".......#.....#.#.","....#....##..#..#"}

Returns: 922246514
{"..#.#.#...#.#....",".................","...###..#.#......","..#......#.....##","#....#..#.#.#....","##..##...........",".#........#......","#.#....#....#....",".....#.....##....","..##.....#.#..#.#",".....#.#.........","..........#...##.",".......#........#",".#...#..#.#.#...#","......#.......#.#","#...........##...","..#.#.#...#.#...."}

Returns: 166731456
{"........#........","....#........##..",".........#.......",".............#...","...#.......#..##.","..#.#.#.....#....","........#.....##.",".......#......##.",".............#...",".#.#..#..#..#....",".###...#.......##","##....#..........","....#............","#........#.#.#...",".....##....#...#.",".................","........#........"}

Returns: 869720392
{".......#.....##.#","###..........#..#","................#","........#..###.#.","#..........###...","...#...##..#..#..","#.#.....#....##..",".................",".......##...#.#..",".#....#.#.#......","..........##.#...","##........#.##...","......#...#......","......#.....#....","...#.......#.....",".........#......#",".......#.....##.#"}

Returns: 132155034
{".....#..##...#...","....#............","..#...#......#...","..........###....","#..#...##.......#","......#......#...","....##..#.#......",".......#..#..#...","..#.......#.....#",".......#.........","##.#....#.#...#..","....##.....#....#","..............#..","..............#..","....#.#.#........","...#......#.#....",".....#..##...#..."}

Returns: 626224380
{"....#..#..#.##.#.","..#....#..##.#.#.","##..#...#..###...",".......#........#","#..#.....#.#.#...","#.....#..........",".#.....#......#.#","......#..........","....##.#..#..#...","....#..#..#......","....#............",".......#...#.....","...##..###......#","...#.#..#.#...##.","...........#.....",".#..#............","....#..#..#.##.#."}

Returns: 142891928
{".#....##....#.#..","....###..........",".#.#.........##.#","...##............","##.......#.......","...#.....#.#...#.","#.#.#............",".##...#..........",".#...............","...#.........#...","...#...........#.","........#...#...#","......#.#....##..","........##.......","...#..##.#.#..#..","#.....#...#.....#",".#....##....#.#.."}

Returns: 671786159
{"..##............#","..#..#....#.....#","#.##..#......###.",".#..#............","........##.....#.","##...#...#..#...#","...#......#......",".#.#..........#..","....##...........","#.#..##....#.##..","....#.#.#..#.....",".................","##.....#....#..##","..............###",".#.#..##.#......#","........##.......","..##............#"}

Returns: 215731712
{"..#..........#...","...#...#.#.......",".#.....#....##...","#...#.##.........","....#....#.#.....","...........#.....","......#....##....","....#...........#","...........#.....","......#..........","..........#......",".........#...##..","............#..#.","....#.##.#..#....","...........#.....",".................","..#..........#..."}

Returns: 118896097
{"...#..#..........","..#.#.......#....",".#...#...........","#.......#........",".#....#..#.#.....","....#.....#.....#","...##.....#..#...","...#....#..##....",".....#...........","...........#.#.#.","..###.......###..","..........##.#...",".........#..#....","....#.........#..",".#........#.##..#","..........#.###..","...#..#.........."}

Returns: 227029805
{"#.......#........","....#...#.##.#...","....#.#....##...#","...#..#.#.....#.#",".#...........#...",".#...#..#........","...........####..","#..#....###......","...#...#....#...#","........#........","..#..............","..#.#............","......##..#......","...#.............",".##.#........#...","...#...#.#.......","#.......#........"}

Returns: 896162596
{"........##.....#.","......#.#...#..#.","#.##..#.....##...",".....#......#....","#............#...",".............#...",".................","....##....###....",".#.........##....","..##....##..#....","#.........#......","##.........#.....",".........#.###.#.",".#..#....#...##..","..##.....#.......","...#.............","........##.....#."}

Returns: 668787388
{".##.....#.#....#.",".#......#........","...........#....#","..#.............#","#..#..#....#...#.",".........#......#","....#.#..........","##.#...#.........","..#..............","..#......#.......",".#.............#.","....#.#...#.#....","...........###...","#.#..............",".....#....#..##..","#.##..#.#..#.#...",".##.....#.#....#."}

Returns: 635430847
{"...#...##.......#",".........#..#.#..",".#....#..........","..##...#.....#...","...#..#.....#..#.",".#...#.#.....#...",".................","...#...#..#......","#..#..#....#.....","......#...#..#.#.","....##...#..#....","...........#..#..","#...#.......#....",".#.............#.","..#............#.","##......#...#....","...#...##.......#"}

Returns: 391324665
{".#......##..#....",".................",".#............#..","..#.###....#.#.##","..#...#......#..#","..#.........#....","..#..#.....#.....","......#.....##.#.","..#.....###...#..","......#....#.....","#.........#......","#...........##..#",".#...###.....#...","#...........#...#","....#.........#.#",".........#....#..",".#......##..#...."}

Returns: 34069727
{"..#..............",".................","....#............","...#.............",".............#...","#....#...........",".....#...........","...........#.....","..........#.....#",".................","...#.............","#..#.............",".................","......#..........","...#............#","..#......#.......","..#.............."}

Returns: 325664328
{"..#..............",".................","...##.......#....",".#..#....#.....#.","#................","#.......#........",".................",".........#.#.....",".................",".......#.........","..........#.#....",".................","..##.............",".................","...............#.",".#..#............","..#.............."}

Returns: 203224955
{"............#....","............#....",".............#...","................#","................#","...............#.","....#.....#......","#........#...#..#","......#..##......","...#.#.....##....",".........#.......",".................","...............#.","..............#..","..............#..",".................","............#...."}

Returns: 887243187
{"#................","....#.#..........","...#.............","....#..#.........",".##.#......#.....",".#........#....#.","..#..#...........",".#.#.#...........",".................","................#","...........#..#..","..#..............",".....#...#...#...",".#...#...#.......",".....#.#..#.....#",".........##..#...","#................"}

Returns: 223895326
{".................",".........#....#..","#................",".#.#.#...........",".................","......#.#....#...","......#.#....#...","................#","....#......#.....","..#.#..#...#..##.","#.....##.....#...",".....#..#........",".##...#..........",".#...........##..","..........#......","...#........#.#..","................."}

Returns: 501699010
{"....#...........#","........#........",".................","#......#.......#.","#................",".#..........#..#.",".................",".....#...........","#...#.....#....##","....#.#..........","...#.......#...#.",".##....#....#...#","...............#.","..............#.#",".................","#...............#","....#...........#"}

Returns: 643605683
{".....#...........",".#...#.....#.....",".........#.......",".....#......#...#","........#........","#....#...........",".................","............#....","...#.#......#....",".................",".................",".....#.#.........","..........#......",".................",".................","..........#......",".....#..........."}

Returns: 654932597
{"#.....###........",".#.......#...#.#.","................#","..............###",".................",".............#...","..#..............","...#.#...........",".............#..#","..............##.","................#","..#.....#........",".................","....#.........#..",".......#.........",".................","#.....###........"}

Returns: 405487068
{"....#..#.........","................#",".......#.......#.","...#.##..........","#................","...#....#..#.....","........#........",".#...............",".................","....#.....#.....#","......#..#......#",".......#.........",".................",".................",".....#...........",".#...............","....#..#........."}

Returns: 646955261
{".................",".###.............","............##.#.",".................","..#.........#....",".................",".........#.......","..........#......","..#.........#....","..........#......",".....##......#...",".................","..#......#.....#.",".................","#.##.............","......#.........#","................."}

Returns: 108360004
{"..#..............",".#...............","....#............",".................","........#........","..............#..",".................","..#..............",".........##...#..","..#.........#....","#................","..............#..","..#..............",".#...............","...#.........#...",".........#.......","..#.............."}

Returns: 942027630
{".........#...#...",".................",".................","...##..#.........",".........#.......","...........#....#","#......#......##.",".....#...........","..#..............",".#..........#....",".................","#..............#.","....#............","#..............##","....#......#.....","....#.#..........",".........#...#..."}

Returns: 460285289
{"..#..............","#.....#..........",".......#.........",".......####.....#",".........#.......","...#.............","...#.............","............#....",".#.......##....##",".................","........#.....#..",".........#...#..#","..........#......",".#...............","...............#.",".....#...........","..#.............."}

Returns: 796768940
{"............#....",".....#...###.#...","......#..........","....#............","....#............",".......#.#....#..","..............#..","#......#.....#...",".........#...#...",".#.....#.....#...","..#..#.......#...",".....#........#.#","..#.........#....","#..........#.....","............#.#..","..#...#.........#","............#...."}

Returns: 247031419
{".....#....#......",".................","..#...#.......##.",".........#.......","..........#....#.","......#..........","..##....#........","...............#.","........##.###...","..............#..","...#.......#....#","......#..........",".................",".................",".........#.......","..............#..",".....#....#......"}

Returns: 206848855
{".................",".......#.........","......#.....#.#..","............#....",".................",".................",".#....#.#.......#",".................",".................",".......#..#...##.","...............#.",".................","........#......#.",".................",".......#.#.......","........#........","................."}

Returns: 753004263
{".................",".................",".................",".............#...",".......#.........",".#.............#.",".................","....#............","..............#..",".................","...............#.",".................",".................",".................",".....#...........",".................","................."}

Returns: 56189175
{"#................",".................",".#...............","............#....","...........#..#..","..............#..",".................",".............#...","........#........",".................",".....#....#......",".................","..........#......",".................",".................",".....#...........","#................"}

Returns: 531607743
{".................","....#........#...","..........#.....#",".................","........#........",".................",".................",".................",".................","...........#....#",".................",".................","............#....",".................",".................",".................","................."}

Returns: 788565325
{"...#..#.....##...","..#.......#..#...",".................",".................",".........#.......","............#....",".................",".................",".........#.......","...#..#..........","......#..........",".................",".................","..........#......","........#........","#..#..........#..","...#..#.....##..."}

Returns: 463155967
{".................",".................","..........#......",".......#......#..",".#...............","....#.........#..",".................","#.....#..........","........#....#...",".................",".................","..............#..","...#......#......","..........#......","#................","..#....#....#..#.","................."}

Returns: 447625909
{"...............#.",".................","....#............",".............#...","........#........",".................",".#...............","...........##..#.",".#...............","..........#......",".#.#...#.........","...........#.....",".......#.........",".................",".................",".................","...............#."}

Returns: 479873879
{"...#....#..#.....","...#.............","........#........","...#.............",".................",".................",".........#.......","..#....#........#",".................",".................","......#...#......","............#....",".................",".................",".................",".................","...#....#..#....."}

Returns: 150551315
{"..#.......###....","............#....",".#....#..........","..............#..","#................",".................",".................",".................",".................","..............#..","..............#..",".................",".....#.....#.....","..#........#...#.","................#",".................","..#.......###...."}

Returns: 91119026
{".................","....#............",".................","...........#.#.#.",".................",".#...#...........",".................",".#.#.............","#................",".........#....#..",".................","............#....","......#.....#....",".................","......#..........",".#.....#.........","................."}

Returns: 22879168
{".................","........#........","...#.............",".................",".................",".#............#..","#........#.......","..............#..",".................",".................","...............#.",".................","..#...#..........",".................",".................",".....#...#..#....","................."}

Returns: 665393791
{".................",".....#...........",".................",".................",".................",".................",".................",".................","..#..............",".............#...","..#......#.......",".................",".........#.......",".#.............#.",".................","#........#.......","................."}

Returns: 279607877
{"............#....","................#",".............#...","..#..#...........",".................",".....#...........","#................",".................",".................",".................",".................",".................","......#..........",".................","....#...#........",".........#.......","............#...."}

Returns: 382413535
{".................",".................","....#............",".................","#................","......#.#........","........#........",".............#...",".................","....#........#...",".................",".................",".............#...",".................",".....#...........","..#...#..........","................."}

Returns: 767493574
{".........#.......","........#........","...............#.",".................",".................","......#..#..#....",".................",".................","...#.............","...#.....#.......",".............#...",".................","....#.........#..","....#....#.......","...............##",".................",".........#......."}

Returns: 35838147
{"...........#..#..",".................",".................",".................","#................",".................",".................",".................",".................",".................",".................",".................",".................","...............#.","...............#.",".................","...........#..#.."}

Returns: 425993055
{".................",".................",".................","...............#.",".................",".................",".................",".................",".................",".................",".................",".................","...........#.#...",".................",".................","..............#..","................."}

Returns: 436272254
{".#...............",".................",".................",".................",".........#.......",".................","................#","....#............",".................",".................",".................",".................",".................",".................",".................",".................",".#..............."}

Returns: 953420257
{".................","....#............","...........#.....",".................","#................",".................",".....#...........",".................","..............#..",".................",".................",".................","......#..........",".................",".................","##.......#.......","................."}

Returns: 127383798
{".................",".................","......#..........",".................",".................","....#............",".................",".................",".................",".................",".............#...",".................",".................","........#........",".................","...#.............","................."}

Returns: 933070925
{".................",".................",".................",".................","....#............","............#....",".................","........#........","............#....",".......#.........",".................",".................",".................",".................",".................","...........#.....","................."}

Returns: 457334257
{".................","......#..........",".................",".................","#................",".................",".................",".................",".#...............",".................",".................",".................",".................",".#...............",".................",".................","................."}

Returns: 485165447
{".................",".................","..#..............",".........#.......",".................","...#.............",".................","......#..........",".................",".................",".................",".................",".................",".................",".........#.......",".................","................."}

Returns: 412218182
{".................",".#.#.............","..........#......",".................",".................",".................",".................","#................","...#.............",".................",".................",".................",".#...............",".................",".................",".................","................."}

Returns: 710384942
{".................",".................","........#........",".................","..............#.#",".................",".................",".................",".................","......#..........",".................","..........#......",".................",".................",".................","................#","................."}

Returns: 276413261
{".................",".................",".................",".................",".................",".................","...#.............",".................",".................",".................",".................",".................",".................",".................","....#............",".................","................."}

Returns: 78018183
{".................","....#..........#.",".................","..........#......",".................",".................",".................",".................",".................",".................",".................","..#..............",".#...............",".................",".................","..#..............","................."}

Returns: 182017448
{".................",".................",".......#.........",".....#...........",".................","..#..............",".................",".................",".................",".................","...............#.",".................",".................","....#............",".................",".................","................."}

Returns: 276299645
{"............#....",".#...............",".................",".................",".................",".................",".................",".................",".................","........#.......#",".................",".................",".................",".................","..#..............","..........#......","............#...."}

Returns: 626837801
{".................",".................",".................",".................",".................",".................","................#",".................",".................",".................",".................",".................",".................",".................",".................",".................","................."}

Returns: 570597158
{".................","........#........",".................",".................",".................",".................",".................","............#....",".................",".................",".................","....#............",".................",".................",".................",".................","................."}

Returns: 63222409
{".................",".................","........#........",".................",".................",".................",".................",".................",".................",".#...............",".................",".................",".................",".................",".................",".................","................."}

Returns: 494865772
{"...............#.",".................",".................",".................",".................","#................",".................",".................",".................",".................",".................",".................",".................",".................",".................","#................","...............#."}

Returns: 182349425
{".................",".................",".................",".................",".................",".................",".................",".....#...........",".................",".................",".................",".................",".................",".................",".................",".................","................."}

Returns: 77153053
{".................",".................",".................","........#........","..........#......",".................","......#..........",".................",".................",".................",".................",".................",".................",".................",".................",".................","................."}

Returns: 892464673
{".................",".................","........#........",".................",".................",".................","........#........",".................",".................",".................",".................",".................",".................",".......#.........",".................","..#..............","................."}

Returns: 623696244
{".................",".................",".................",".................","...........#.....","..#..............",".....#...........",".................",".................",".................",".................",".................",".................",".................",".................",".................","................."}

Returns: 703723313
{"....#............",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................","....#............"}

Returns: 602114693
{".................",".................",".................",".................",".................","....#............",".................",".................","................#",".................",".................",".................",".........#.......","..#..............",".................",".................","................."}

Returns: 268818515
{".................","....#............",".................","..........#......","...#.............",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................","................."}

Returns: 506895837
{".................",".................","#................",".................",".................",".................",".................",".................",".......#.........",".......#.........",".................",".................","...#.............","...........#.....",".................",".................","................."}

Returns: 762345243
{".................",".................","...............#.",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................","................."}

Returns: 986392096
{".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................","................."}

Returns: 484752458
{"........#........",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................","........#........"}

Returns: 244479003
{".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................","#................",".....#...........","..........#......","................."}

Returns: 675097200
{".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................",".................","................."}

Returns: 484752458

Statistics

Problem Statement for "DominoPlacement"

Problem Statement

Definition

Notes

Constraints

Examples