2. Sssssss, tak robia hady

Martin sa veľmi dobre pozná s ostatnými gréckymi bohmi. Raz sa však rozprával so svojím starým známym HADesom, ktorý počas celej noci strážil brány Olympu. Po dlhej šichte z neho vyliezlo iba:

Sssssssssss SSSsssS SSssssssssSS SSSSSSS SSSSsSSss?! sssssssSS ssSSSSSSSsSS SSSSSSSSs ssssssss sssSSSSSSS SSSSSSS SSSSsssS. SSSS SSSSSssss SSSssssSSS SSSsssSSSss sSSssss?

Určite každý z vás ovláda hadie jazyky, Pythony a iné Kobry, ale pre tých z vás, ktorí zadaniu vyššie nerozumejú, je tu aj jeho preklad do reči smrteľníkov.

Zadanie:

Vašou úlohou je odpovedať na základe pohybu hadíka v mriežke s rozmermi \(m \times n\), na koľkých políčkach mohol začať bez toho, aby vyšiel mimo mriežku. Hadík sa každým kolom zväčšuje a pohybuje sa do jedného zo štyroch základných smerov. Ak je postupnosť na vstupe neplatná (hadík narazil sám do seba alebo vyšiel mimo mriežku), odpovedzte 0.

Formát vstupu

V prvom riadku vstupu dostanete dve čísla \(m\) - počet stĺpcov, \(n\) - počet riadkov, Nasleduje 1 riadok v ktorom dostanete reťazec dĺžky \(t\) obsahujúci znaky: ‘H’,‘D’,‘P’,‘L’ - reprezentujúce smery: hore, dole, vpravo, vľavo.

V sadách platia nasledujúce obmedzenia:

V sadách 1, 2 navyše platí že hadík sa pohybuje iba dole a doprava.

Formát výstupu

Na jeden riadok vypíšte jedno číslo - na koľkých políčkach mohol had začať. Keďže výsledok môže byť fakt veľký nezabudnite použiť long long v C++

Príklady

Input:

3 3
DDD

Output:

0

Nezáleží, kde hadík začne v mriežke, vždy zíde o 3 políčka nižšie (mimo mriežku)

Input:

4 3
DDPPHLL

Output:

0

Hadík narazil sám do seba

Input:

13 13
PDDDPDDDPPPDPPPPPDDD

Output:

9