火树银花-困难版

题目描述

为了庆祝马上到来的中秋假期，学校购入了一批灯带。已知一组彩灯是由一排 $n$ 个独立的灯泡构成的，并且有 $m$ 个开关控制它们。

从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有 $2^n$ 个样式。开关每按一下可以改变灯的状态。

假如告诉你每个开关所控制的彩灯范围，也就是每个开关能控制哪些灯泡，你能否帮学校计算一下，这些开关随意按下多次，一共能展现出多少种不同的灯光形态。

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

输入格式

第一行为两个整数 $n$ 和 $m$，用空格隔开。代表这条灯带上彩灯的个数，以及开关的个数。（$1\leq n,m \leq 50$）

接下来有 $m$ 行，每行都是一个长度为 $n$ 的字符串，表示一个开关控制彩灯的范围（$n$ 盏灯），如果第 $i$ 个字母是大写字母 O，则表示这个开关控制第 $i$ 盏灯，如果第 $i$ 个字母是大写字母 X，则表示这个开关不控制此灯。

输出格式

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

输入输出样例 #1

样例输入 #1

2 3
OO
XO
OX

样例输出 #1

4

样例解释

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