Admissible Map

题意翻译

所谓“映射”，是由 'U'、'L'、'D' 和 'R' 四个字符组成的矩阵。 对于映射矩阵 $a$, 有一 $n \cdot m$ 有向映射图（$n$ 为矩阵 $a$ 的行数，$m$ 为矩阵 $a$ 的列数），图中有 $n \cdot m$ 条有向边，形式如下： - $(i,j) \rightarrow (i+di_{a_{i,j}},j+dj_{a_{i,j}})$ 其中： - $(i,j)$ 与 $(i+di_{a_{i,j}},j+dj_{a_{i,j}})$ 都表示 $a$ 的有向映射图中的顶点； - $\rightarrow$ 表示指向； - $(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_{i,j}$ 为映射矩阵 $a$ 中第 $i$ 行第 $j$ 列的字符。 （$di_U$ 中的 'U', $di_L$ 中的 'L', $di_D$ 中的 'D', $di_R$ 中的 'R' 皆为映射矩阵 $a$ 中的字符） 我们将图中任意一边都指向有效顶点的映射图视作“有效的”。 因而定义：容许映射是其映射图有效且其中存在如“说明/提示”中所展示的“循环”的映射。 我们用一串由映射 $a$ 中所有字符组成且按照如下顺序排列的字符串描述映射 $a$： - $a_{1,1}a_{1,2}…a_{1,m}a_{2,1}…a_{n,m}$（$n,m$ 同上述）。 给出这样的一个字符串 $s$，求字符串 $s$ 中有多少个子串是容许映射的描述。 原题面中为不使所求值产生歧义，补充如下： - 已知一个长 $l$ 的字符串 $s_1s_2…s_l$，正整数 $p$ 和 $q$，且 $1 \leq p \leq q \leq l$，则从位置 $p$ 到 $q$ 的子串为 $s_p s_{p+1}…s_q$. - 有子串 $substr_1$ 和 $substr_2$，分别对应 $(p_1,q_1)$ 和 $(p_2,q_2)$，若 $(p_1,q_1)$ 与 $(p_2,q_2)$ 不同，则即使 $substr_1=substr_2$，也称 $substr_1$ 与 $substr_2$ 不同。

题目描述

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.

输入输出样例

输入样例 #1

RDUL

输出样例 #1

2

输入样例 #2

RDRU

输出样例 #2

0

输入样例 #3

RLRLRL

输出样例 #3

6

说明

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