P16906 [CCO 2026] Walking on a Graph

There is a graph with $N$ nodes, numbered from $1$ to $N$. Each node is coloured either black or white. Additionally, it is known that node $1$ is black and node $2$ is white. For any $i$ and $j$ where $i \ne j$, there exists a directed edge from node $i$ to $j$ that is either red or blue. Its colour is determined using the following logic: - If $i < j$ and the nodes have the same colour, then it is red. - If $i < j$ and the nodes have different colours, then it is blue. - If $i > j$ and the nodes have the same colour, then it is blue. - If $i > j$ and the nodes have different colours, then it is red. LoBren’s favourite colour is initially blue. He then takes a walk on the graph (note that walks allow for repeated vertices and edges). He uses the following rules when walking: - If he is currently on node $1$, his favourite colour becomes blue. - Otherwise, if he is currently on node $2$, his favourite colour becomes red. - He then traverses an outgoing edge from his current node with the same colour as his favourite colour. It can be shown that such an edge must exist. - Finally, he optionally repeats the process. By writing down the nodes he visits, in order, he gets a list $l_1, l_2, \ldots, l_L$. Find the number of possible lists, mod $10^9 + 7$, that satisfy the following conditions: - The list starts at node $1$ and ends at node $2$. - For all $i$ where $3 \le i \le N$, node $i$ appears at most once in the list. - For all $j$ where $3 \le j \le L$, we have $l_{j-2} \ne l_j$. It is provable that the number of such lists is finite. It may also be useful to note that “mod” corresponds to the `%` operator in most programming languages, indicating the remainder after division. For example, $5 \bmod 3 = 2$ and $17 \bmod 4 = 1$.

The first line of input contains a single integer, $N$. The next line contains a string of length $N$, consisting of the characters $\mathrm{B}$ and $\mathrm{W}$. If the $i$th character is $\mathrm{B}$, then node $i$ is black. Otherwise, it is white. It is guaranteed that node $1$ is black and node $2$ is white.

On a single line, output the number of possible lists, modulo $10^9 + 7$.

**Explanation of Output for Sample Input $1$** The graph looks like: :::align{center}  ::: The solid lines represent blue edges, while the dashed lines represent red edges. The possible paths are: - $\color{blue}{1}\ \color{blue}{\to}\ \color{red}{\underline{2}}$ - $\color{blue}{1}\ \color{blue}{\to}\ \color{blue}{3}\ \color{blue}{\to}\ \color{red}{\underline{2}}$ - $\color{blue}{1}\ \color{blue}{\to}\ \color{blue}{3}\ \color{blue}{\to}\ \color{blue}{4}\ \color{blue}{\to}\ \color{red}{\underline{2}}$ - $\color{blue}{1}\ \color{blue}{\to}\ \color{red}{\underline{2}}\ \color{red}{\dashrightarrow}\ \color{red}{\underline{3}}\ \color{red}{\dashrightarrow}\ \color{blue}{1}\ \color{blue}{\to}\ \color{red}{\underline{2}}$ The favourite colour is red at the underlined nodes, and blue otherwise. The following table shows how the $25$ available marks are distributed: | Marks Awarded | Bounds on $N$ | Additional Constraints | |:-:|:-:|:-:| | $1$ mark | $3 \le N \le 8$ | None. | | $3$ marks | $3 \le N \le 20$ | None. | | $4$ marks | $3 \le N \le 50$ | There exists exactly $1$ black node. | | $4$ marks | $3 \le N \le 50$ | There exists an integer $i$ where $2 \le i \le N$, such that every node in the range $[2, i]$ is white, and every other node is black. | | $6$ marks | $3 \le N \le 50$ | There exist at most $5$ black nodes. | | $7$ marks | $3 \le N \le 50$ | None. |