{"raw_statement":[{"iden":"statement","content":"给定一个 $n×m$ 的格点图，包含 $n$ 行 $m$ 列共 $n×m$ 个顶点，相邻的顶点之间有一条边。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/n56tzo5w.png)\n\n给出了一个 $3×4$ 的格点图的例子。\n\n如果在图中删除部分顶点和其相邻的边，如上图删除第 $2$ 行第 $3$ 列和第 $3$ 行第 $1$ 列的顶点后，如下图所示。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/alcq3m2c.png)\n\n图的生成树指包含图中的所有顶点和其中的一部分边，使得任意两个顶点之间都有由边构成的唯一路径。如果两个生成树包含有不同的边即被认为不同，则上图中共有 $31$ 种不同的生成树，其中 a 边不选有 $10$ 种，a 边选有 $21$ 种。\n\n给出格点图中保留的顶点的信息，请计算该图一共有多少种不同的生成树。"},{"iden":"input","content":"输入的第一行包含两个整数 $n$，$m$，用空格分隔，表示格点图的行数和列数。\n\n接下来 $n$ 行，每行 $m$ 个字母（中间没有分隔字符），每个字母必然是大写 `E` 或大写 `N`，`E` 表示对应的顶点存在，`N` 表示对应的顶点不存在。保证存在至少一个顶点。"},{"iden":"output","content":"输出一行，包含一个整数，表示生成树的个数。答案可能很大，你只需要计算答案除以 $1000000007$（即 $10^9+7$） 的余数即可。"},{"iden":"note","content":"对于 $10\\%$ 的数据，$1\\le n\\le2$。\n\n对于 $30\\%$ 的数据，$1\\le n\\le3$。\n\n对于 $40\\%$ 的数据，$1\\le n\\le4$。\n\n对于 $50\\%$ 的数据，$1\\le n\\le5$。\n\n另有 $20\\%$ 的数据，$1\\le n\\times m\\le12$。\n\n另有 $10\\%$ 的数据，$1\\le m\\le15$。\n\n对于 $100\\%$ 的数据，$1\\le n\\le6，1\\le m\\le10^5$。"}],"translated_statement":null,"sample_group":[["3 4\nEEEE\nEENE\nNEEE","31"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}