Ballroom floor covering: hints, no solution

A ballroom floor plan is a grid given as a list of equal-length strings. A dot is an open cell that must be covered and a hash is a blocked cell that must stay uncovered. The floor is covered with straight tiles of two kinds: a tile is either 1 cell wide and 2 cells long or 1 cell wide and 3 cells long, and each may be laid horizontally or vertically. Tiles cover only open cells and never overlap.

Count the ways to cover every open cell exactly. Two coverings are different when some tile differs in position or length. Return the count modulo 1000000007. A floor with no open cell has exactly one covering, the empty one. Floors can have up to 12 rows and 7 columns, so trying tile placements one by one cannot finish in time.

Examples

Input

floor = ["...", "..."]

Output

4

Note

Two horizontal 3-tiles; three vertical 2-tiles; or two stacked horizontal 2-tiles beside a vertical 2-tile, which can sit on either side.

Input

floor = ["..#", "..."]

Output

1

Note

The bottom row takes a 3-tile and the top row a 2-tile; no other layout covers the five open cells.

Constraints

• 1 <= number of rows <= 12 and 1 <= row length <= 7
• Every cell is a dot or a hash
• Return the count modulo 1000000007

Hint 1: a nudge

Scanning the floor row by row, which information about the cells below the current row do you need to remember, and how much can it differ between columns?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing