战舰（Battleship）是一款由两名玩家进行的游戏。每名玩家都有自己的网格，且对对手隐藏。每名玩家在自己的网格上秘密放置一些船只。每艘船占据一条水平或垂直的直线，由一个或多个连续的方格组成。船只不能重叠。即使大小相同，所有船只也被视为不同的个体。

放置好船只后，玩家轮流通过呼叫对手网格上的坐标来向对手的船只射击。对手必须诚实地回答该次射击是命中还是未命中。当一艘船的所有方格都被命中时，该船沉没（“你击沉了我的战舰！”）。当一名玩家的所有船只都沉没时，该玩家输掉比赛。

Bob 正在与 Alice 进行一场迷你战舰游戏。常规战舰游戏在 $10 \times 10$ 的网格上使用 5 艘船进行。迷你战舰的规模要小得多，网格不超过 $5 \times 5$，且船只数量可能少于 5 艘。

Bob 想知道，根据他目前所知的信息，Alice 的棋盘上可能存在多少种船只放置方案。如果 Alice 作弊（或者游戏设置本身不可能实现），答案将为 0。

输入格式

输入的第一行包含两个空格分隔的整数 $n$ ($1 \le n \le 5$) 和 $k$ ($1 \le k \le 5$)，分别代表在一个 $n \times n$ 的网格上进行的 $k$ 艘船的迷你战舰游戏。

接下来的 $n$ 行，每行包含一个字符串 $s$ ($|s| = n$)，表示 Bob 目前看到的 Alice 的网格情况。

• 字符 ‘X’ 代表 Bob 的一次未命中射击。
• 字符 ‘O’（字母 O，非数字零）代表 Bob 的一次命中射击。
• 点号 (‘.’) 代表 Bob 尚未进行射击的方格。

接下来的 $k$ 行，每行包含一个整数 $x$ ($1 \le x \le n$)，代表船只的大小。

输出格式

输出一个整数，表示在符合 Bob 所见信息的前提下，将 $k$ 艘不同的船放置在 Alice 网格上的方案总数。

样例

样例输入 1

4 3
....
.OX.
....
O..X
3
2
1

样例输出 1

132

样例输入 2

4 4
.X.X
.XX.
...X
....
1
2
3
4

样例输出 2

6

样例输入 3

2 2
..
..
2
2

样例输出 3

4