Background

Peter’s girlfriend’s birthday is coming, and he designed a set of colored lights as a surprise. A set consists of a row of $N$ independent bulbs, controlled by $M$ switches. Mathematically, each bulb has exactly two states, on or off, so there are $2^N$ possible patterns. Due to technical reasons, the bulbs controlled by each switch have no particular pattern: when a switch is pressed, it toggles the state of every bulb it controls (on becomes off, off becomes on). Given the set of bulbs each switch controls, can you compute how many distinct lighting patterns can be displayed?

Note: Initially, all bulbs are off.

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