Description

Lavender, Caryophyllus, Jasmine, and Dianthus are now playing a game called "Rowing".

The rules of this game are as follows:

1. Players freely form two teams. One person acts as the boat captain, and the other acts as the scout.
2. At the start of each game, both sides are given a map generated by the system. The map is represented as a 0-1 matrix: 1 means there is an obstacle and it is impassable, while 0 means open water and it is passable.
3. In the first round, both captains must choose a starting point on the map. This point cannot be an obstacle, so it must be 0.
4. In each round, the captain may command their boat to move by one unit to an adjacent open-water cell in one of the four directions: up/down/left/right. That is, the boat may only move onto a 0 in one of the four directions (and of course, it cannot move outside the map). After this operation is completed, they must tell the opponent the direction they moved in that round.
5. The scouts on both sides are responsible for recording the opponent boat’s movement direction in each round, and for inferring the opponent boat’s possible position at that moment. If a scout can infer the opponent boat’s exact position at that moment, they may fire a missile at it, and the scout’s side wins.

Now, Jasmine has recorded some movement directions of the opponent boat. She wants to determine how many possible positions the opponent boat may be at this moment. Since she is not good at calculations, she hands this task to you.

Input Format

The first line contains three positive integers $n$, $m$, $k$, indicating that the map has $n$ rows and $m$ columns, and the game has currently proceeded for $k$ rounds. It is guaranteed that $2\le n,m \le 1500$, $1\le k\le 5\times 10^6$.

Lines 2 to $n+1$ contain an $n$ by $m$ 0-1 matrix with no separators, describing the map information. The meaning is as described above.

The last line of the input is a string $s$ of length $k$, consisting only of the letters w, a, s, d. From left to right, the $i$-th character $s_i$ indicates that in round $i$, the opponent boat moved one unit up/left/down/right.

Output Format

Output one line containing one positive integer, indicating the number of possible positions of the opponent boat in round $k$. For all input data, it is guaranteed that a valid solution exists.

5 6 5
000000
001001
000100
001000
000001
dwdaa

4

Hint

Sample Explanation

The figure above shows the result after visualizing the path sequence. The figure below marks in blue the possible positions of the opponent boat at this moment.

Copyright Information

From the 2018 Tsinghua University Programming Contest and Collegiate Invitational Contest (THUPC2018). Thanks to Pony.ai for supporting this contest.

Resources such as the editorial can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5