一个地图（map）是一个由字符集合 {'U', 'L', 'D', 'R'} 组成的矩阵。

地图矩阵 $a$ 的地图图（map graph）是一个有 $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)$。当所有边都指向图中的有效顶点时，称该地图图是合法的。

容许地图（admissible map）是指其地图图合法且由一组循环（cycles）组成的地图。

地图 $a$ 的描述（description）是地图所有行的拼接——即字符串 $a_{1,1}a_{1,2} \dots a_{1,m}a_{2,1} \dots a_{n,m}$。

给定一个字符串 $s$。你的任务是找出该字符串中有多少个子串可以构成某个容许地图的描述。

字符串 $s_1s_2 \dots s_l$ 的一个长度为 $l$ 的子串由一对索引 $p$ 和 $q$（$1 \le p \le q \le l$）定义，等于 $s_p s_{p+1} \dots s_q$。即使两个子串代表相同的字符串，只要它们的索引对 $(p, q)$ 不同，它们就被视为不同的子串。

输入格式

输入仅一行，包含一个字符串 $s$，由至少 1 个、至多 20 000 个字符 'U'、'L'、'D' 或 'R' 组成。

输出格式

输出一个整数——可以构成某个容许地图描述的 $s$ 的子串数量。

样例

输入 1

RDUL

输出 1

2

输入 2

RDRU

输出 2

0

输入 3

RLRLRL

输出 3

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）的插图。

图 1

图 2

图 3

图 4

图 5