Existe un grafo con $N$ nodos, numerados del 1 al $N$. Cada nodo está coloreado de negro o blanco. Además, se sabe que el nodo 1 es negro y el nodo 2 es blanco. Para cualquier $i$ y $j$ donde $i \neq j$, existe una arista dirigida del nodo $i$ al $j$ que es roja o azul. Su color se determina utilizando la siguiente lógica:
- Si $i < j$ y los nodos tienen el mismo color, entonces es roja.
- Si $i < j$ y los nodos tienen colores diferentes, entonces es azul.
- Si $i > j$ y los nodos tienen el mismo color, entonces es azul.
- Si $i > j$ y los nodos tienen colores diferentes, entonces es roja.
El color favorito de LoBren es inicialmente azul. Luego, realiza un recorrido en el grafo (nótese que los recorridos permiten vértices y aristas repetidos). Utiliza las siguientes reglas al caminar:
- Si actualmente está en el nodo 1, su color favorito se vuelve azul.
- De lo contrario, si actualmente está en el nodo 2, su color favorito se vuelve rojo.
- Luego, atraviesa una arista saliente desde su nodo actual con el mismo color que su color favorito. Se puede demostrar que tal arista debe existir.
- Finalmente, repite el proceso opcionalmente.
Al anotar los nodos que visita, en orden, obtiene una lista $l_1, l_2, \dots, l_L$. Encuentre el número de listas posibles, módulo $10^9 + 7$, que satisfacen las siguientes condiciones:
- La lista comienza en el nodo 1 y termina en el nodo 2.
- Para todo $i$ donde $3 \leq i \leq N$, el nodo $i$ aparece como máximo una vez en la lista.
- Para todo $j$ donde $3 \leq j \leq L$, tenemos $l_{j-2} \neq l_j$.
Es demostrable que el número de tales listas es finito.
Puede ser útil notar que "mod" corresponde al operador % en la mayoría de los lenguajes de programación, indicando el resto de la división. Por ejemplo, $5 \text{ mod } 3 = 2$ y $17 \text{ mod } 4 = 1$.
Entrada
La primera línea de la entrada contiene un único entero, $N$.
La siguiente línea contiene una cadena de longitud $N$, que consiste en los caracteres B y W. Si el $i$-ésimo carácter es B, entonces el nodo $i$ es negro. De lo contrario, es blanco. Se garantiza que el nodo 1 es negro y el nodo 2 es blanco.
Subtareas
La siguiente tabla muestra cómo se distribuyen las 25 marcas disponibles:
| Marcas otorgadas | Límites de $N$ | Restricciones adicionales |
|---|---|---|
| 1 marca | $3 \leq N \leq 8$ | Ninguna. |
| 3 marcas | $3 \leq N \leq 20$ | Ninguna. |
| 4 marcas | $3 \leq N \leq 50$ | Existe exactamente un nodo negro. |
| 4 marcas | $3 \leq N \leq 50$ | Existe un entero $i$ donde $2 \leq i \leq N$, tal que cada nodo en el rango $[2, i]$ es blanco, y cada otro nodo es negro. |
| 6 marcas | $3 \leq N \leq 50$ | Existen como máximo 5 nodos negros. |
| 7 marcas | $3 \leq N \leq 50$ | Ninguna. |
Salida
En una sola línea, imprima el número de listas posibles, módulo $10^9 + 7$.
Ejemplos
Entrada 1
4 BWWB
Salida 1
4
Nota 1
El grafo se ve así:
Las líneas continuas representan aristas azules, mientras que las líneas discontinuas representan aristas rojas. Los caminos posibles son:
- $1 \to 2$
- $1 \to 3 \to 2$
- $1 \to 3 \to 4 \to 2$
- $1 \to 2 \to 3 \to 1 \to 2$
El color favorito es rojo en los nodos subrayados, y azul en los demás.
Entrada 2
12 BWBWBBBWWBBW
Salida 2
3377552