Output Format

Output the number of distinct patterns obtainable by these switches and bulbs. Since this number can be large, output it modulo the integer $2008$.

2 3
OO
XO
OX

4

Hint

As seen in the sample, the first switch controls all bulbs, while the next two switches control the first and second bulbs respectively. In this case, using only the latter two switches suffices to obtain all $2^2$ states.

Constraints:

• For $30\%$ of the testdata, $N$ and $M$ do not exceed $15$.
• Additionally, for $40\%$ of the testdata, one of $N$ and $M$ equals $50$.
• For $100\%$ of the testdata, $N$ and $M$ do not exceed $50$.

Translated by ChatGPT 5