A15036 | 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 as $(i, j)$ ( $1 \le i \le n; 1 \le j \le m$ ), where $n$ is the number of rows in the matrix, $m$ is the number of columns in the matrix. 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)$ ; $(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 such that its map graph is valid and consists of a set of cycles.

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

You are given a string $s$ . Your task is to find how many substrings of this string can constitute a description of some admissible map.

A substring of a string $s_1s_2 \ldots s_l$ of length $l$ is defined by a pair of indices $p$ and $q$ ( $1 \le p \le q \le l$ ) and is equal to $s_ps_{p+1} \ldots s_q$ . Two substrings of $s$ are considered different when the pair of their indices $(p, q)$ differs, even if they represent the same resulting string.

In the only input line, there is a string $s$ , consisting of at least one and at most $20\,000$ symbols 'U', 'L', 'D', or 'R'.

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