P17351 [ECNA 2025] Polyomino Tiling

多连块是若干单位正方形构成的非空、连通且无孔洞的并集；每个单位正方形的顶点都位于二维平面的整点上。一个多连块可以用表示其边界的字符串描述。 从多连块边界上的某个整点出发，沿边界每次向上、向右、向下或向左移动一个单位，并分别用字符 `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$ 的方案总数。