机器人 Calvin 位于一个无限长的矩形网格中。 Calvin 的源代码包含 n 个命令的列表,每个命令都是“U”、“R”、“D”或“L”——分别向上、向右、向下或向左移动单个方块的指令。 Calvin 有多少种方法可以执行命令的非空连续子串并返回到他开始的同一个方块?如果两个子字符串具有不同的起始或结束索引,则它们被视为不同。
输入
输入的第一行包含一个正整数 n (1 ≤ n ≤ 200) — 命令数。
下一行包含 n 个字符,每个字符可以是“U”、“R”、“D”或“L”——Calvin 的源代码。
输出
打印一个整数——Calvin 可以执行并返回到起始方格的连续子字符串的数量。
示例
输入 #1
6 URLLDR
输出 #1
2
输入 #2
4 DLUU
输出 #2
0
输入 #3
7 RLRLRLR
输出 #3
12
注意
在第一种情况下,整个源代码以及第二个和第三个字符中的“RL”子字符串都可以工作。
请注意,在第三种情况下,子字符串“LR”出现了三次,因此被计入总结果三次。