空袭，又名空中打击，是在复杂地形中常见的一种远距支援打击手段。通常由侦察兵对目标进行指示，之后最近的友方空中支援机将会发射一枚导弹打击目标。空袭拥有灵活性强，杀伤力大，丢失率严重等特点。导弹从发射到命中需要一定的时间，因此对于移动单位而言打中非常困难。因此，有经验的友军空中支援部队将会预判目标单位的移动方式，并对估计到达时的位置(而不是目标的当前位置)进行打击。现在我军侦察兵 GloryKen 正在练习如何空袭打击一只“嗜血猎食者”（又称“三级狗”）。这种敌方单位移动速度快且不规律，通常是侦察兵的天敌，但空袭只需一发即可消灭一只“三级狗”。地形可以看作是 $N \times M$ 的网格，有些格子有障碍无法通行。在空地上有一个敌方单位“三级狗”。在接下来的一段时间内，侦察兵 GloryKen 将会对它进行若干次空袭。具体过程可以按回合制来描述。三级狗的初始位置在坐标 $(x,y)$，面向上下左右的某个方向。

每个回合由如下几个阶段组成。

1. GloryKen发出一次“空袭指示”，友军空中支援部队立即发射一枚导弹。这颗导弹将会在 $a_i$ 个回合之后命中三级狗当前位置前方 $a_i$ 格的格子（这里的“前方”是指三级狗当前面向的方向。）。如果这个位置在地图外，那么此次空袭失效。
2. 三级狗进行一次“移动”。它可以向上下左右移动一格（不能越界，也不能到达有障碍存在的格子），也可以选择呆在当前的格子。如果进行移动，它的朝向将会变为移动的方向，否则它的朝向不变。
3. 之前所有预定于该回合到达的导弹全部同时到达在预定的位置，如果三级狗被导弹命中，它将立即死亡。导弹不会对地形造成影响，即不会破坏障碍，也不会制造障碍。

现在，GloryKen想知道，$T$ 个回合的空袭之后，如果这只三级狗还存活，它的位置可能在哪里。于是，你需要求出，对于每一个格子，这只三级狗有多少种方案能够在第 $T$ 回合恰好到达这个格子，并且存活。两个方案不同，当且仅当某个回合三级狗的移动选择不同。

输入格式

第一行三个数，$N$，$M$，$T$，表示网格大小以及回合数。接下来 $N$ 行，每行 $M$ 个字符，描述整张地图：

• .表示一个空地;
• *表示一个障碍;
• 一个数字(0,1,2,3其中之一)表示三级狗的位置，全图只有一个数字，且出现数字的位置是空地。这个数字说明了

三级狗的朝向：

• 0 表示沿该方向走 1 步会导致 $x$ 坐标 $+1$
• 1 表示沿该方向走 1 步会导致 $y$ 坐标 $+1$
• 2 表示沿该方向走 1 步会导致 $x$ 坐标 $-1$
• 3 表示沿该方向走 1 步会导致 $y$ 坐标 $-1$

接下来 $T-1$ 行，每行一个数 $a_i$，表示空袭导弹将会在 $a_i$ 回合之后命中三级狗当前位置前方 $a_i$ 格的格子。显然第 $T$ 回合的空袭是没有意义的，因此输入不包含第 $T$ 回合空袭的信息。

输出格式

共 $N$ 行，每行 $M$ 个数，相邻两个数之间用一个空格分隔，表示三级狗恰好在第 $T$ 回合到达这个格子并且存活的方案数(虽然有障碍的点答案一定是 $0$，但是为了整齐也请你输出这个值)。为了避免高精度，请将所有的答案对 $1\,000\,000\,007$ 取模后再输出。

样例数据

样例输入

3 2 2
1.
*.
..
1

样例输出

2 0
0 1
0 0

样例解释

初始时三级狗在(1,1)，向右。第一回合第一阶段：空袭将在1回合后(第2回合)打击三级狗面前的1格(即(1,2)格子 )。第一回合第二阶段：三级狗可以选择不动 (1, 1, 右) 或者向前 (1, 2, 右)。第一回合第三阶段：没有导弹到达。

第二回合第一阶段：这是最后一回合，空袭没有意义。第二回合第二阶段：三级狗移动。如果之前选择不动 (1, 1, 右)，三级狗可以选择继续不动 (1, 1, 右) 或者向前(1, 2, 右)。如果之前选择向前 (1, 2, 右)，三级狗可以选择不动(1, 2,右)或者向左 (1, 1, 左) 或者向下 (2, 2, 下)。第二回合第三阶段：空袭在 (1, 2) 到达，如果此时三级狗在 (1, 2)，它将被杀死。

综上，三级狗有两种方案在第二回合结束时在(1,1)并存活，有1种方案在第二回合结束时在(2,2)存活。

子任务

对于 $100\%$ 的数据，$1 \le N,M \le 20$，$1 \le a_i \le 12$，$1 \le T \le 50$