#P17446. PM8174多米诺电视游戏

PM8174多米诺电视游戏

题目描述

有一个 n×nn\times n 的多米诺骨牌棋盘。第 ii 行第 jj 列的骨牌正面写着数字 ii 和 jj(行列均从 11 开始编号)。玩家必须恰好选择 nn 张骨牌,并且任意两张被选骨牌不能来自同一行,也不能来自同一列。

选择完成后,把所有含有相同数字的骨牌连接起来。最终会形成若干个连通组,一张没有与其他骨牌相连的骨牌也算一个组。

每张骨牌背面还有一个隐藏整数。把所有被选骨牌的隐藏数相乘;如果最终连通组的数量是偶数,再把这个乘积乘以 −1-1。所得数值就是这一种选择的游戏结果。

给定所有骨牌的隐藏数,求所有可能选择的游戏结果之和,对 121547121547 取模。

输入字符 0 到 9 分别表示 00 到 99;字符 A 到 I 分别表示 −1-1 到 −9-9。

输入格式

第一行两个整数 n,mn,m,保证 n=mn=m。

接下来 nn 行,每行一个长度为 mm 的字符串,表示棋盘上的隐藏数。

输出格式

输出所有选择方案的游戏结果之和对 121547121547 取模后的非负余数。

样例

输入

2 2
35
44

输出

8

输入

3 3
12A
A12
2A1

输出

14

数据范围

1≤n=m≤501\le n=m\le50。棋盘只包含字符 0 到 9 和 A 到 I。