Polyomino Tiling

문제

A polyomino is a nonempty connected union of unit squares without holes, where the corners of each unit square are at integer coordinates in the two-dimensional plane. A polyomino can be described by a string representation of its boundary. Starting at some integer coordinates on the polyomino's boundary we can follow the boundary by taking unit steps up, right, down, or left. We represent each of these steps with the letters u, r, d, l, respectively. If we concatenate these letters while following the boundary of the polyomino until we reach the starting coordinates, then the concatenation is called the boundary string for the polyomino. Note that while following the boundary, only the starting coordinates may be visited twice, all other coordinates in the path must be visited exactly once.

The cyclic rotations of the boundary string are obtained by starting at different coordinates on the boundary and proceeding in the same order as in the boundary string (either clockwise or counter-clockwise, but not both). For example, the cyclic rotations of urdl are urdl, rdlu, dlur, and lurd.

For a string $SS$, consisting of letters u, r, d, and l, define $\bar{S}\backslash overline\{S\}$ as the string obtained by reversing the letters of $SS$ and changing each u to d, each d to u, each r to l, and each l to r. For example, for $S=S=$uruurrdl, we have $\bar{S}=\backslash overline\{S\}=$rullddld.

It can be proven that a polyomino will tile the plane by translations (i.e., without rotations nor reflections) if and only if a cyclic rotation of the boundary string $BB$ can be written as $B=X\cdot Y\cdot Z\cdot \bar{X}\cdot \bar{Y}\cdot \bar{Z}B=X\backslash cdot\; Y\backslash cdot\; Z\; \backslash cdot\; \backslash overline\{X\}\; \backslash cdot\; \backslash overline\{Y\}\; \backslash cdot\; \backslash overline\{Z\}$ or $B=X\cdot Y\cdot \bar{X}\cdot \bar{Y}B=X\backslash cdot\; Y\; \backslash cdot\; \backslash overline\{X\}\backslash cdot\; \backslash overline\{Y\}$, where $X,Y,ZX,Y,Z$ are nonempty strings. Quite often, there may be many ways to rotate the boundary string and write it in one or both of these two forms.

Given a boundary string for a polyomino, count the number of ways that each cyclic rotation $BB$ of the boundary string can be written as either $B=X\cdot Y\cdot \bar{X}\cdot \bar{Y}B=X\backslash cdot\; Y\; \backslash cdot\; \backslash overline\{X\}\; \backslash cdot\; \backslash overline\{Y\}$ or $B=X\cdot Y\cdot Z\cdot \bar{X}\cdot \bar{Y}\cdot \bar{Z}B=X\backslash cdot\; Y\; \backslash cdot\; Z\backslash cdot\; \backslash overline\{X\}\; \backslash cdot\; \backslash overline\{Y\}\; \backslash cdot\; \backslash overline\{Z\}$ where $XX$, $YY$, and $ZZ$ are nonempty strings. This count will be $00$ if the polyomino cannot tile the plane by translations.

입력

Input consists of a single line containing two values $kk$ $ss$, where $kk$ ($4\le k\le 100004\backslash leq\; k\backslash leq\; 10\backslash ,000$) is the length of the boundary string and $ss$ is the boundary string. The boundary string will consist of the letters u, r, d, and l.

출력

Print a single integer, the number of ways that each cyclic rotation of the boundary string can be written in the form $X\cdot Y\cdot \bar{X}\cdot \bar{Y}X\; \backslash cdot\; Y\; \backslash cdot\; \backslash overline\{X\}\; \backslash cdot\; \backslash overline\{Y\}$ or $X\cdot Y\cdot Z\cdot \bar{X}\cdot \bar{Y}\cdot \bar{Z}X\; \backslash cdot\; Y\; \backslash cdot\; Z\; \backslash cdot\; \backslash overline\{X\}\; \backslash cdot\; \backslash overline\{Y\}\; \backslash cdot\; \backslash overline\{Z\}$.

힌트

Part of a tiling for the first polyomino in the sample input.

20 uurrrrdrdrdlldlullul

6

14 ururdrrdldllul

4

12 uurdrurddlll

0

8 urrrdlll

16