Canadian Computing Olympiad 2026: Day 2, Problem 3

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 \neq 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, \dots, 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 \leq i \leq N~, node ~i~ appears at most once in the list.

• For all ~j~ where ~3 \leq j \leq L~, we have ~l_{j - 2} \neq l_j~.

It is provable that the number of such lists is finite.

It may also be useful to note that ~\bmod~ corresponds to the % operator in most programming languages, indicating the remainder after division. For example, ~5 \bmod 3 = 2~ and ~17 \bmod 4 = 1~.

Input Specification

The first line of input contains a single integer, ~N~.

The next line contains a string of length ~N~, consisting of the characters B and W. If the ~i^\text{th}~ character is ~\texttt{B}~, then node ~i~ is black. Otherwise, it is white. It is guaranteed that node 1 is black and node 2 is white.

The following table shows how the 25 available marks are distributed:

Marks Awarded	Bounds on ~N~	Additional Constraints
1 mark	~3 \leq N \leq 8~	None.
3 marks	~3 \le N \le 20~	None.
4 marks	~3 \leq N \leq 50~	There exists exactly one black node.
4 marks		There exists an integer ~i~ where ~2 \leq i \leq N~, such that every node in the range ~[2, i]~ is white, and every other node is black.
6 marks		There exist at most 5 black nodes.
7 marks		None.

Output Specification

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

Sample Input 1

4
BWWB

Sample Output 1

4

Explanation for Sample Output 1

The graph looks like:

The solid lines represent blue edges, while the dashed lines represent red edges. The possible paths are:

• ~{\color{blue} 1 \rightarrow}\ {\color{red} \underline{2}}~

• ~{\color{blue} 1 \rightarrow 3 \rightarrow}\ {\color{red} \underline{2}}~

• ~{\color{blue} 1 \rightarrow 3 \rightarrow 4 \rightarrow}\ {\color{red} \underline{2}}~

• ~{\color{blue} 1 \rightarrow}\ {\color{red} \underline{2} \dashrightarrow \underline{3} \dashrightarrow}\ {\color{blue} 1 \rightarrow}\ {\color{red} \underline{2}}~

The favourite colour is red at the underlined nodes, and blue otherwise.

Sample Input 2

12
BWBWBBBWWBBW

Output for Sample Input 2

3377552