题目描述

Peter 女朋友的生日快到了，他亲自设计了一组彩灯，想给女朋友一个惊喜。已知一组彩灯是由一排 $N$ 个独立的灯泡构成的，并且有 $M$ 个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有 $2^N$ 个样式。由于技术上的问题，Peter 设计的每个开关控制的彩灯没有什么规律，当一个开关被按下的时候，它会把所有它控制的彩灯改变状态（即亮变成不亮，不亮变成亮）。假如告诉你他设计的每个开关所控制的彩灯范围，你能否帮他计算出这些彩灯有多少种样式可以展示给他的女朋友？

注： 开始时所有彩灯都是不亮的状态。

输入格式

每组测试数据第一行为两个整数 $N$ 和 $M$，用空格隔开。紧接着是有 $M$ 行，每行都是一个长度为 $N$ 的字符串，表示一个开关控制彩灯的范围（$N$ 盏灯），如果第 $i$ 个字母是大写字母 O，则表示这个开关控制第 $i$ 盏灯，如果第 $i$ 个字母是大写字母 X，则表示这个开关不控制此灯。

输出格式

输出这些开关和彩灯可以变换出来的样式数目。由于这个值可能会很大，请求出它对于整数 $2008$ 的余数。

2 3
OO
XO
OX

4

提示

可见样例中第一个开关控制了所有的彩灯，而后两个开关分别控制了第一个和第二个彩灯，这样我们可以只用后两个开关控制彩灯，可以变换出来所有的 $2^2$ 个状态。

对于 $30\%$ 的数据，$N$ 和 $M$ 不超过 $15$。

另外有 $40\%$ 的数据，$N$ 和 $M$ 有一个为 $50$。

对于 $100\%$ 的数据，$N$ 和 $M$ 不超过 $50$。