19897번 - Робот 다국어

Компания <<Филипп индастриз>> разрабатывает программу для нового робота-марсохода. Участок Марса, на котором будет работать робот, представляет собой квадратное поле размером $n \times n$, разбитое на квадратные участки размером $1 \times 1$, некоторые из которых могут содержать скалу ($1 \le n \le 500$, не более 500 клеток содержат скалу).

Введем на поле систему координат таким образом, что участки имеют координаты $(1, 1), (1, 2), \ldots, (1, n), (2, 1), \ldots, (n, n)$. Программа для робота представляет собой последовательность инструкций, каждая из которых кодируется одной латинской буквой:

• <<U>> --- переместиться с участка ($x$, $y$) на участок ($x$, $y+1$).
• <<D>> --- переместиться с участка ($x$, $y$) на участок ($x$, $y-1$).
• <<R>> --- переместиться с участка ($x$, $y$) на участок ($x+1$, $y$).
• <<L>> --- переместиться с участка ($x$, $y$) на участок ($x-1$, $y$).

Для экономии инженеры записывают в память последовательность инструкций $s$, пронумерованных от 1 до $t$. Затем можно заставить робота выполнить подпрограмму --- одну или несколько следующих подряд инструкций. Каждая подпрограмма, таким образом, характеризуется двумя целыми числами $(l, r)$ --- номером первой и последней инструкции в подпрограмме.

В процессе лабораторного эксперимента робот был размещен на некотором участке тестового поля. Будем называть подпрограмму $(l, r)$ корректной, если при последовательном выполнении инструкций $s[l], s[l+1], \ldots, s[r]$ робот не покидает поле и не перемещается на участок со скалой.

По описанию поля, программе для робота и его начальному положению определите, сколько у данной программы существует корректных подпрограмм.

В первой строке входного файла находятся два числа $n$ и $t$ ($1 \le n \le 500$, $1 \le t \le 10^5$) --- размер поля и количество инструкций в программе робота.

Во второй строке входного файла находится строка $s$ длины $t$ --- программа робота. Гарантируется, что строка $s$ состоит только из символов <<U>>, <<D>>, <<R>> и <<L>>.

Следующие $n$ строк содержат по $n$ символов в каждой и задают поле. Символ <<.>> означает, что участок пустой и по нему может перемещаться робот. Символ <<#>> означает, что на участке находится скала. Символ <<@>> означает, что в этой клетке находится стартовая позиция робота. Ось $X$ направлена слева направо, ось $Y$ --- снизу вверх. Гарантируется, что символ <<@>> встречается ровно один раз, а символ <<#>> встречается не более 500 раз.

В единственной строке выходного файла выведите количество корректных подпрограмм.

В примере следующие подпрограммы являются корректными: $(1,1)$=<<U>>, $(1,2)$=<<UL>>, $(1,3)$=<<ULU>>, $(3,3)$=<<U>>, $(3,4)$=<<UR>>, $(4,4)$=<<R>>.