허용 가능한 지도

지도는 U, L, D, R 기호로 이루어진 행렬이다.

지도 행렬 $a$의 지도 그래프는 $n \cdot m$개의 정점을 가진 방향 그래프다. 정점은 $(i, j)$ ($1 \le i \le n; 1 \le j \le m$)로 번호가 매겨지며, $n$은 행의 수, $m$은 열의 수다. 이 그래프에는 $n \cdot m$개의 간선이 있고, 간선은 $(i, j) \to (i + di_{a_{i,j}}, j + dj_{a_{i,j}})$로 정해진다. 여기서 $(di_U, dj_U) = (-1, 0)$, $(di_L, dj_L) = (0, -1)$, $(di_D, dj_D) = (1, 0)$, $(di_R, dj_R) = (0, 1)$이다. 모든 간선이 그래프 안의 유효한 정점을 가리키면 지도 그래프가 유효하다고 한다.

허용 가능한 지도는 지도 그래프가 유효하고 사이클들의 집합으로 이루어진 지도다.

지도 $a$의 설명은 모든 행을 이어 붙인 문자열 $a_{1,1} a_{1,2} \ldots a_{1,m} a_{2,1} \ldots a_{n,m}$이다.

문자열 $s$가 주어진다. $s$의 부분 문자열 중 어떤 허용 가능한 지도의 설명이 될 수 있는 것의 개수를 구하라. 부분 문자열은 두 인덱스 $p$, $q$ ($1 \le p \le q \le l$, $l$은 $s$의 길이)로 정해지며 $s_p s_{p+1} \ldots s_q$와 같다. 문자열이 같더라도 $(p, q)$가 다르면 서로 다른 부분 문자열이다.

입력은 한 줄이며, 길이가 1 이상 20,000 이하인 문자열 $s$가 주어진다. 각 문자는 U, L, D, R 중 하나다.

허용 가능한 지도의 설명이 될 수 있는 $s$의 부분 문자열 개수를 한 줄에 출력한다.

첫 번째 예시에서는 허용 가능한 지도의 설명이 되는 부분 문자열이 두 개다. RDUL을 $2 \times 2$ 행렬로 본 경우 (그림 1)와 DU를 $2 \times 1$ 행렬로 본 경우 (그림 2)다.

두 번째 예시에서는 조건을 만족하는 부분 문자열이 없다. 예를 들어 RDRU를 $2 \times 2$ 행렬로 보면 결과 그래프가 사이클들의 집합이 아니다 (그림 3).

세 번째 예시에서는 RL 3개, RLRL 2개, RLRLRL 1개가 조건을 만족한다. 일부 문자열은 여러 방식으로 행렬이 될 수 있다. 예를 들어 RLRLRL은 $3 \times 2$ 행렬 (그림 4)로도, $1 \times 6$ 행렬 (그림 5)로도 볼 수 있다.