A 地图 是一个由来自 ' 集合的符号组成的矩阵U', 'L', 'D', 和 'R'.
A 地图图 映射矩阵 $$$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)$$$。地图图形是 有效 当所有边都指向图中的有效顶点时。
An 可接受的地图 是一个映射,其映射图有效并且由一组循环组成。
A 说明 地图 $$$a$$$ 的 是地图所有行的串联 - 字符串 $$$a_{1,1} a_{1,2} \ldots a_{1, m} a_{2, 1} \ldots a_{n, m}$$$。
给你一个字符串$$$s$$$。你的任务是找出这个字符串的多少个子串可以构成某个可接受的地图的描述。
A 子字符串 长度为 $$$l$$$ 的字符串 $$$s_1s_2 \ldots s_l$$$ 的 由一对索引 $$$p$$$ 和 $$$q$$$ ($$$1 \le p \le q \le l$$$) 定义,并且等于 $$$s_ps_{p+1} \ldots s_q$$$。当 $$$s$$$ 的索引对 $$$(p, q)$$$ 不同时,$$$s$$$ 的两个子字符串被视为不同,即使它们表示相同的结果字符串。
输入
在唯一的输入行中,有一个字符串$$$s$$$,由至少一个、最多$$$20\,000$$$符号组成'U', 'L', 'D', 或 'R'.
输出
输出一个整数——$$$s$$$ 中构成某个可接受地图描述的子串数量。
示例
输入复制
RDUL
输出复制
2
输入复制
RDRU
输出复制
0
输入复制
RLRLRL
输出复制
6
注意
在第一个示例中,有两个子字符串可以构成可接受地图的描述 - “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) 的矩阵。




