P5447 [THUPC 2018] Rowing

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.

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 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**.

### 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](http://pony.ai/) for supporting this contest. Resources such as the editorial can be found at . Translated by ChatGPT 5