题目描述

小 Z 的机器人在二维整数坐标平面上运动，初始位于 (0, 0)，面向北方。北、东、南、西分别对应 y 轴正方向、x 轴正方向、y 轴负方向、x 轴负方向。

机器人使用一张环形指令带。指令带上依次写有 $n$ 条指令，相邻关系首尾相接：

• F：沿当前朝向前进一步；
• L：原地向左转 90°；
• R：原地向右转 90°。

执行程序时，机器人会从指令带上的某一条指令开始，沿固定方向依次执行，直到每条指令都恰好执行一次。指令的环上次序已知，但原本用于标记第一条指令的记号脱落了。

给定按环上顺序抄录的指令串 $s = s_1s_2\cdots s_n$。若选择第 $i$ 条指令作为起点，实际执行顺序为

枚举全部 $n$ 个可能的起点，求机器人一共可能到达多少个不同的最终位置。

输入格式

第一行一个整数 $n$。

第二行一个长度为 $n$ 的字符串 $s$，仅包含字符 F、L、R。

输出格式

输出一个整数，表示不同最终位置的数量。

3
FLF

3

样例解释

三个可能的起点对应字符串 FLF、LFF、FFL，最终位置依次为 (-1,1)、(-2,0)、(0,2)。

参见下发文件中的 mark2.in。

参见下发文件中的 mark2.ans。

大样例说明

该样例符合测试点 1 ~ 12 的约束。

参见下发文件中的 mark3.in。

参见下发文件中的 mark3.ans。

大样例说明

该样例符合测试点 15 ~ 20 的约束。

数据范围与提示

对于所有测试数据，保证：

• $1 \le n \le 2 \times 10^5$；
• $s$ 仅包含字符 F、L、R。

本题共 20 个测试点，每个测试点 5 分，各测试点单独计分。

下发文件：download_3625.zip