#4626. [BeiJing2016]空袭

内存限制:256 MiB 时间限制:1 Sec

题目描述

空袭,又名空中打击,是在复杂地形中常见的一种远距支援打击手段。通常由侦察兵对目标进行指示,之后最近的
友方空中支援机将会发射一枚导弹打击目标。空袭拥有灵活性强,杀伤力大,丢失率严重等特点。导弹从发射到命
中需要一定的时间,因此对于移动单位而言打中非常困难。因此,有经验的友军空中支援部队将会预判目标单位的
移动方式,并对估计到达时的位置(而不是目标的当前位置)进行打击。现在我军侦察兵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)
存活。

数据范围与提示