Admissible Map

A map is a matrix consisting of symbols from the set of U, L, D, and R.

A map graph of a map matrix $a$ is a directed graph with $n \cdot m$ vertices numbered $(i, j)$ ($1 \le i \le n; 1 \le j \le m$), where $n$ is the number of rows and $m$ is the number of columns. The graph has $n \cdot m$ directed edges $(i, j) \to (i + di_{a_{i,j}}, j + dj_{a_{i,j}})$, where $(di_U, dj_U) = (-1, 0)$, $(di_L, dj_L) = (0, -1)$, $(di_D, dj_D) = (1, 0)$, and $(di_R, dj_R) = (0, 1)$. A map graph is valid when all edges point to valid vertices in the graph.

An admissible map is a map whose map graph is valid and consists of a set of cycles.

A description of a map $a$ is the concatenation of all rows of the map: the string $a_{1,1} a_{1,2} \ldots a_{1,m} a_{2,1} \ldots a_{n,m}$.

You are given a string $s$. Count the substrings of $s$ that can constitute a description of some admissible map. A substring is defined by a pair of indices $p$ and $q$ ($1 \le p \le q \le l$, where $l$ is the length of $s$) and equals $s_p s_{p+1} \ldots s_q$. Two substrings are different when their index pairs $(p, q)$ differ, even if they spell the same string.

The only line contains a string $s$ of at least 1 and at most 20,000 symbols, each U, L, D, or R.

Print one integer: the number of substrings of $s$ that constitute a description of some admissible map.

In the first example, two substrings can constitute a description of an admissible map: RDUL as a $2 \times 2$ matrix (pic. 1) and DU as a $2 \times 1$ matrix (pic. 2).

In the second example, no substring works. For instance, reading RDRU as a $2 \times 2$ matrix gives a graph that is not a set of cycles (pic. 3).

In the third example, three substrings RL, two substrings RLRL, and one substring RLRLRL work, and some of them work in more than one way. For instance, RLRLRL works as a $3 \times 2$ matrix (pic. 4) and as a $1 \times 6$ matrix (pic. 5).