Building mosaics is an art dedicated to the construction of images by assembling small pieces of some material. Lego pieces are all about building things by assembling small pieces, and therefore they present the flexibility and versatility to create wonderful mosaics.

You have been commissioned to build a large lego mosaic. The basic
idea is to use a lego plate and on the top of it attach some lego
bricks. Each lego stud is like a pixel in the image. If we used text
to represent a mosaic, with `’.’` representing a stud without a
brick, `’R’` for a red brick, `’Y’` for a yellow brick and
`’G’` for a green brick, then the mosaic of the image below would
be represented by:

................ ......R......... ................ ..R.R.R.R.R.RRR. ..RRR.R.R.R.R.R. ..R.R.R.R.R.RRR. ..R.R.R.RRR.R... YYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYY ...GGG.GGG.G.G.. .....G.G.G.G.G.. ...GGG.G.G.G.G.. ...G...G.G.G.G.. ...GGG.GGG.G.G.. ................ ................ |

For the construction of the mosaic you have available a very large set
of `1``×``N` bricks. In particular, for the purposes of the
mosaic, you can assume you have an infinite number of 9 different
types of bricks (in any needed color). These are `1``×``1`,
`1``×``2`, `1``×``3`, `1``×``4`, `1``×``6`, `1``×``8`, `1``×``10`, `1``×``12`
and `1``×``16` bricks, and are depicted in the figure on the right.

For aesthetically reasons, you only want to use the bricks in the
horizontal positions, that is, parallel to the bottom of the
plate. This means that when seen from the top, as in the textual
representation above, the width of the bricks is variable, but the
height is always `1`.

When you were starting the construction, you noticed that even with
those constraints, there were several different ways of building the
mosaic. For example, the mosaic below has 16 different ways of using
pieces to obtain the exact same image (with `’B’` meaning a blue brick):

.... YYBB YBBB .... |

Given the description of a lego mosaic, your task is to compute in how
many different ways you can build that mosaic assuming you have an
infinite pool of `1``×``1`, `1``×``2`, `1``×``3`,
`1``×``4`, `1``×``6`, `1``×``8`, `1``×``10`, `1``×``12` and `1``×``16` lego bricks,
in any color. The bricks must be positioned in horizontal positions.

The first line of input contains two integers **R** and **C**,
indicating respectively the number of rows and columns of the mosaic
to be built.

The next **R** lines of input contain each exactly **C**
characters detailing the mosaic to be built. Each character must
either be `’.’` (representing a stud without any brick on top of
it) or a capital letter (from `’A’` to `’Z’`) representing a
stud of a given color. Two bricks with the same letter representing it
have the same color. You can assume that there is at least one brick in the mosaic.

The output should consist of a single integer **W** indicating the
number of ways in which the mosaic can be built, given that you can
only use bricks of type `1``×``1`, `1``×``2`, `1``×``3`, `1``×``4`, `1``×``6`, `1``×``8`,
`1``×``10`, `1``×``12` and `1``×``16` on
horizontal positions. You can assume you always have enough bricks to build
the mosaic using any combination of the bricks you need.

1 ≤ ≤ 1,000R,C | Number of rows and columns of the mosaic |

1 ≤ ≤ 2,000,000,000W | Number of different ways to build the mosaic |

4 4 .... YYBB YBBB ....

16

3 6 GGRRRR GYYRRR GGRRRR

2048

This document was translated from L^{A}T_{E}X byH^{E}V^{E}A.