题目描述

多连块是若干单位正方形构成的非空、连通且无孔洞的并集；每个单位正方形的顶点都位于二维平面的整点上。一个多连块可以用表示其边界的字符串描述。

从多连块边界上的某个整点出发，沿边界每次向上、向右、向下或向左移动一个单位，并分别用字符 u、r、d、l 表示这些步。沿边界移动直至回到起点，把途中字符依次连接起来，就得到该多连块的边界字符串。注意，在沿边界行走时，只有起点会被访问两次，路径上的其他坐标都恰好访问一次。

边界字符串的循环移位，是指在边界上的不同坐标处开始，并按边界字符串原有方向继续行走得到的字符串；方向可以统一为顺时针或统一为逆时针，但不能同时把两个方向都计入。例如，urdl 的循环移位为 urdl、rdlu、dlur 和 lurd。

对于只含 u、r、d、l 的字符串 $S$，定义 $\overline S$ 为：先把 $S$ 中的字符顺序反转，再把每个 u 换成 d、每个 d 换成 u、每个 r 换成 l、每个 l 换成 r。例如，若 $S=\texttt{uruurrdl}$，则 $\overline S=\texttt{rullddld}$。

可以证明，一个多连块能够只通过平移——不允许旋转或翻转——平铺整个平面，当且仅当边界字符串的某个循环移位 $B$ 可以写成下列两种形式之一：

$$B=X\cdot Y\cdot Z\cdot\overline X\cdot\overline Y\cdot\overline Z,$$

或

$$B=X\cdot Y\cdot\overline X\cdot\overline Y,$$

其中 $X,Y,Z$ 都是非空字符串。通常，旋转边界字符串并将其写成其中一种或两种形式的方法可能有很多。

给定一个多连块的边界字符串，统计所有循环移位 $B$ 写成上述两种形式的方案总数，其中出现的 $X,Y,Z$ 均非空。如果多连块无法只通过平移平铺平面，答案为 $0$。

输入格式

输入仅一行，包含两个量 $k,s$。$k$（$4\le k\le 10000$）表示边界字符串长度，$s$ 是只由 u、r、d、l 组成的边界字符串。

输出格式

输出一个整数，表示边界字符串的各个循环移位写成 $X\cdot Y\cdot\overline X\cdot\overline Y$ 或 $X\cdot Y\cdot Z\cdot\overline X\cdot\overline Y\cdot\overline Z$ 的方案总数。

20 uurrrrdrdrdlldlullul

6

14 ururdrrdldllul

4

12 uurdrurddlll

0

8 urrrdlll

16