There is a graph with nodes, numbered from to . Each node is coloured either black or white. Additionally, it is known that node is black and node is white. For any and where , there exists a directed edge from node to that is either red or blue. Its colour is determined using the following logic:
If and the nodes have the same colour, then it is red.
If and the nodes have different colours, then it is blue.
If and the nodes have the same colour, then it is blue.
If 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 , his favourite colour becomes blue.
Otherwise, if he is currently on node , 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 . Find the number of possible lists, mod , that satisfy the following conditions:
The list starts at node and ends at node .
For all where , node appears at most once in the list.
For all where , we have .
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, and .
输入格式
The first line of input contains a single integer, .
The next line contains a string of length , consisting of the characters and . If the th character is , then node is black. Otherwise, it is white. It is guaranteed that node is black and node is white.
输出格式
On a single line, output the number of possible lists, modulo .
样例
样例输入 1
4
BWWB
样例输出 1
4
样例输入 2
12
BWBWBBBWWBBW
样例输出 2
3377552
数据范围与提示
Explanation of Output for Sample Input
The graph looks like:
:::align{center}
:::
The solid lines represent blue edges, while the dashed lines represent red edges. The possible paths are:
The favourite colour is red at the underlined nodes, and blue otherwise.
The following table shows how the available marks are distributed:
Marks Awarded
Bounds on
Additional Constraints
mark
None.
marks
marks
There exists exactly black node.
There exists an integer where , such that every node in the range is white, and every other node is black.
:::