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