题目描述

Lavender、Caryophyllus、Jasmine、Dianthus现在在玩一款名叫“赛艇”的游戏。

这个游戏的规则是这样的：

1. 玩家自由组成两队，一个人当赛艇的艇长，另一个人当侦察兵；
2. 每次游戏开始时，双方均拥有由系统生成的某张地图，该地图以01矩阵的形式表示，1表示有障碍物，无法通行，0表示水域空旷，可以通行；
3. 第一回合，双方的赛艇艇长都要在地图上指定一个出发点，该出发点不能是障碍物，也就是只能为0；
4. 在每个回合中，艇长可以指挥自己的赛艇向上/下/左/右四个方向的某一方向的空旷水域移动一个单位的距离，也就是说只能移向四个方向上的某个0上（当然，不能移动出地图之外）；在该操作完成之后，必须向对方说出自己在该回合移动的方向；
5. 双方的侦察兵负责记录每一回合对方赛艇的移动方向，并负责推断此时对方赛艇可能的位置；如果某方的侦察兵推测出对方赛艇此时的精确位置，那么可以向其发射导弹，该侦察兵所在的一方胜利；

现在，Jasmine记录了一些对方赛艇的路径，她想确定一下此时对方所有可能的位置共有几种。由于她不是很擅长计算，所以这个任务就交给你了。

输入格式

输入第一行包含三个正整数 $n$，$m$，$k$，分别表示地图为 $n$ 行 $m$ 列，当前游戏已经进行了 $k$ 轮。保证 $2\le n,m \le 1500$，$1\le k\le 5\times 10^6$。

输入第二行到第 $n+1$ 行为一个 $n$ 行 $m$ 列的 01 矩阵，无任何分隔符号，表示地图的具体信息，具体含义如上所示。

输入的最后一行为一个长度为 $k$ 的字符串 $s$，仅由字母 w、a、s、d 构成，从前往后第 $i$ 个字符 $s_i$ 表示对方在第 $i$ 轮中，对方赛艇向上/左/下/右移动一个单位距离。

输出格式

输出一行一个正整数，表示在第 $k$ 轮游戏回合的时候，对方赛艇可能的位置的种数。对于所有输入数据，保证有合法解。

5 6 5
000000
001001
000100
001000
000001
dwdaa

4

提示

样例解释

上图显示了路径序列可视化之后的结果，下图用蓝色标出了此时对方赛艇可能的位置。

版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。