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