4626 - [BeiJing2016]空袭
空袭，又名空中打击，是在复杂地形中常见的一种远距支援打击手段。通常由侦察兵对目标进行指示，之后最近的 友方空中支援机将会发射一枚导弹打击目标。空袭拥有灵活性强，杀伤力大，丢失率严重等特点。导弹从发射到命 中需要一定的时间，因此对于移动单位而言打中非常困难。因此，有经验的友军空中支援部队将会预判目标单位的 移动方式，并对估计到达时的位置(而不是目标的当前位置)进行打击。现在我军侦察兵GloryKen正在练习如何空袭 打击一只“嗜血猎食者”（又称“三级狗”）。这种敌方单位移动速度快且不规律，通常是侦察兵的天敌，但空袭 只需一发即可消灭一只“三级狗”。地形可以看作是N×M的网格，有些格子有障碍无法通行。在空地上有一个敌方 单位“三级狗”。在接下来的一段时间内，侦察兵GloryKen将会对它进行若干次空袭。具体过程可以按回合制来描 述。三级狗的初始位置在坐标(x,y)，面向上下左右的某个方向。 每个回合由如下几个阶段组成。
- GloryKen发出一次“空袭指示”，友军空中支援部队立即发射一枚导弹。这颗导弹将会在ai个回合之后命中三 级狗当前位置前方ai格的格子（这里的“前方”是指三级狗当前面向的方向。）。如果这个位置在地图外，那么此 次空袭失效。
- 三级狗进行一次“移动”。它可以向上下左右移动一格（不能越界，也不能到达有障碍存在的格子），也可以 选择呆在当前的格子。如果进行移动，它的朝向将会变为移动的方向，否则它的朝向不变。
- 之前所有预定于该回合到达的导弹全部同时到达在预定的位置，如果三级狗被导弹命中，它将立即死亡。导弹 不会对地形造成影响，即不会破坏障碍，也不会制造障碍。 现在，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行，每行一个数ai，表示空袭导弹将会在ai回合之后命中三级狗当前位置前方ai格的格子。显然第T回合 的空袭是没有意义的，因此输入不包含第T回合空袭的信息。 1≤N,M≤20，1≤ai≤12，1≤T≤50
输出
共N行，每行M个数，相邻两个数之间用一个空格分隔，表示三级狗恰好在第T回合到达这个格子并且存活的方案数( 虽然有障碍的点答案一定是0，但是为了整齐也请你输出这个值)。为了避免高精度，请将所有的答案对1000000007 取模后再输出。
样例
输入
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) 存活。