一个多格骨牌（polyomino）是二维平面上无孔的、非空的单位正方形连通并集，其中每个单位正方形的顶点都在整数坐标上。多格骨牌可以通过其边界的字符串表示来描述。从多格骨牌边界上的某个整数坐标开始，我们可以沿着边界向上、向右、向下或向左移动单位步。我们分别用字母 u、r、d、l 来表示这些步骤。如果我们沿着多格骨牌的边界移动，并将这些字母拼接起来，直到回到起点坐标，那么这个拼接得到的字符串就称为该多格骨牌的边界字符串。注意，在沿着边界移动时，只有起点坐标可以被访问两次，路径中的所有其他坐标必须恰好被访问一次。

样例输入中第一个多格骨牌的部分平铺示意图。

边界字符串的循环移位（cyclic rotations）是通过从边界上的不同坐标开始，并按照与边界字符串相同的顺序（顺时针或逆时针，但不能两者混合）进行移动而得到的。例如，urdl 的循环移位有 urdl、rdlu、dlur 和 lurd。

对于一个由字母 u、r、d 和 l 组成的字符串 $S$，定义 $\overline{S}$ 为将 $S$ 的字符顺序反转，并将每个 u 替换为 d，每个 d 替换为 u，每个 r 替换为 l，每个 l 替换为 r 得到的字符串。例如，对于 $S = \text{uruurrdl}$，我们有 $\overline{S} = \text{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$ 可以被写为 $B = X \cdot Y \cdot \overline{X} \cdot \overline{Y}$ 或 $B = X \cdot Y \cdot Z \cdot \overline{X} \cdot \overline{Y} \cdot \overline{Z}$ 的方式总数，其中 $X, Y, Z$ 是非空字符串。如果该多格骨牌不能通过平移平铺平面，则此计数为 0。

输入格式

输入由单行组成，包含两个值 $k$ 和 $s$，其中 $k$ ($4 \le k \le 10\,000$) 是边界字符串的长度，$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}$ 形式的方法总数。

样例

输入样例 1

20 uurrrrdrdrdlldlullul

输出样例 1

6

输入样例 2

14 ururdrrdldllul

输出样例 2

4

输入样例 3

12 uurdrurddlll

输出样例 3

0

输入样例 4

8 urrrdlll

输出样例 4

16