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

地图是一个由字符集 $\{ \text{U}, \text{L}, \text{D}, \text{R} \}$ 中的符号构成的矩阵。

一张地图 $a$ 的地图图（map graph）是一个有向图，其顶点为 $(i, j)$（其中 $1 \le i \le n$，$1 \le j \le m$），共 $n \cdot 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),\quad (di_L, dj_L) = (0, -1),\quad (di_D, dj_D) = (1, 0),\quad (di_R, dj_R) = (0, 1).$$

当所有边均指向图中合法顶点（即目标坐标满足 $1 \le i' \le n$ 且 $1 \le j' \le m$）时，该地图图称为合法的（valid）。

一张可容许地图（admissible map）是指其对应的地图图既合法，又仅由若干个环组成（即图中每个连通分量均为一个有向环，且无其他结构）。

地图 $a$ 的描述（description）是指将其所有行按顺序拼接而成的字符串：$a_{1,1} a_{1,2} \ldots a_{1, m} a_{2, 1} \ldots a_{n, m}$。

现给定一个字符串 $s$。你的任务是：求出该字符串中有多少个子串，能够作为某个可容许地图的描述。

字符串 $s_1 s_2 \ldots s_l$ 的一个长度为 $l$ 的子串由一对下标 $(p, q)$（满足 $1 \le p \le q \le l$）确定，其内容为 $s_p s_{p+1} \ldots s_q$。即使两个子串的内容完全相同，只要其下标对 $(p, q)$ 不同，即视为不同的子串。

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

在唯一的一行输入中，有一个字符串 $s$，由至少一个、至多 $20\,000$ 个字符组成，每个字符为 'U'、'L'、'D' 或 'R'。

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

输出一个整数——字符串 $s$ 中构成某个合法地图描述的子串数量。

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

In the second example, no substring can constitute a description of an admissible map. E. g. if we try to look at the string "RDRU" as a matrix of size $2 \times 2$, we can find out that the resulting graph is not a set of cycles (pic. 3).

In the third example, three substrings "RL", two substrings "RLRL" and one substring "RLRLRL" can constitute an admissible map, some of them in multiple ways. E. g. here are two illustrations of substring "RLRLRL" as matrices of size $3 \times 2$ (pic. 4) and $1 \times 6$ (pic. 5).

在第一个例子中，有两个子串可以构成一个合法地图的描述——“RDUL”作为 $2 \times 2$ 规模的矩阵（图 1），以及“DU”作为 $2 \times 1$ 规模的矩阵（图 2）。

在第二个例子中，没有任何子串可以构成合法地图的描述。例如，若尝试将字符串“RDRU”视为 $2 \times 2$ 规模的矩阵，则可发现所得图并非若干个环的集合（图 3）。

在第三个例子中，有三个子串“RL”、两个子串“RLRL”以及一个子串“RLRLRL”可以构成合法地图，其中部分子串存在多种构造方式。例如，子串“RLRLRL”可分别以 $3 \times 2$ 规模（图 4）和 $1 \times 6$ 规模（图 5）的矩阵形式呈现。