ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Dmitry Gozman Contest 1. Petrozavodsk training camp. Winter 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Path

Time limit: 1.0 second
Memory limit: 64 MB
A new robot "PTZ07" is now in the testing room. The testing room is a parallelepiped n × m × k. The robot knows a sequence of instructions to execute. The instructions are: 'u' — one position up, 'd' — one position down, 'l' — one position left, 'r' — one position right, 'f' — one position forward, 'b' — one position backward. Robot executes its program one by one. If the instruction tells the robot to go outside the room, the robot ignores this instruction.
You are given a sequence of instructions, but you don't know the initial location of the robot. Your task is to find the number of positions in which the robot may finish its trip.

Input

The first line of the input contains three integers n, m and k (1 ≤ n, m, k ≤ 105) — width (left-right dimension), height (up-down dimension) and length (forward-backward dimension). The second line contains the sequence of instructions. There will be no more than 105 instructions.

Output

Output the number of positions where robot may finish its trip after executing the given program.

Samples

inputoutput
1 1 1
uuuur
1
2 2 2
ulf
1
13 14 15
uudlbdrruffbr
1560
Problem Author: Dmitry Gozman
Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007
To submit the solution for this problem go to the Problem set: 1525. Path