题目描述

有一个 $n\times n$ 的多米诺骨牌棋盘。第 $i$ 行第 $j$ 列的骨牌正面写着数字 $i$ 和 $j$（行列均从 $1$ 开始编号）。玩家必须恰好选择 $n$ 张骨牌，并且任意两张被选骨牌不能来自同一行，也不能来自同一列。

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

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

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

输入字符 0 到 9 分别表示 $0$ 到 $9$；字符 A 到 I 分别表示 $-1$ 到 $-9$。

输入格式

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

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示棋盘上的隐藏数。

输出格式

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

样例

输入

2 2
35
44

输出

8

输入

3 3
12A
A12
2A1

输出

14

数据范围

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