Dany jest graf o $N$ wierzchołkach, ponumerowanych od $1$ do $N$. Każdy wierzchołek jest pokolorowany na czarno lub biało. Dodatkowo wiadomo, że wierzchołek $1$ jest czarny, a wierzchołek $2$ jest biały. Dla dowolnych $i$ oraz $j$, gdzie $i \neq j$, istnieje skierowana krawędź z wierzchołka $i$ do $j$, która jest albo czerwona, albo niebieska. Jej kolor jest określony zgodnie z następującą logiką:

• Jeśli $i < j$ i wierzchołki mają ten sam kolor, krawędź jest czerwona.
• Jeśli $i < j$ i wierzchołki mają różne kolory, krawędź jest niebieska.
• Jeśli $i > j$ i wierzchołki mają ten sam kolor, krawędź jest niebieska.
• Jeśli $i > j$ i wierzchołki mają różne kolory, krawędź jest czerwona.

Ulubionym kolorem LoBrena jest początkowo niebieski. Następnie wykonuje on spacer po grafie (należy zauważyć, że spacery dopuszczają powtarzanie wierzchołków i krawędzi). Podczas spaceru stosuje następujące zasady:

• Jeśli aktualnie znajduje się w wierzchołku $1$, jego ulubiony kolor zmienia się na niebieski.
• W przeciwnym razie, jeśli aktualnie znajduje się w wierzchołku $2$, jego ulubiony kolor zmienia się na czerwony.
• Następnie przechodzi przez krawędź wychodzącą z bieżącego wierzchołka, która ma ten sam kolor co jego ulubiony kolor. Można wykazać, że taka krawędź zawsze istnieje.
• Na koniec może opcjonalnie powtórzyć ten proces.

Zapisując odwiedzane wierzchołki w kolejności, otrzymuje listę $l_1, l_2, \dots, l_L$. Znajdź liczbę możliwych list, modulo $10^9 + 7$, które spełniają następujące warunki:

• Lista zaczyna się w wierzchołku $1$ i kończy w wierzchołku $2$.
• Dla wszystkich $i$, gdzie $3 \le i \le N$, wierzchołek $i$ pojawia się na liście co najwyżej raz.
• Dla wszystkich $j$, gdzie $3 \le j \le L$, zachodzi $l_{j-2} \neq l_j$.

Można udowodnić, że liczba takich list jest skończona.

Warto zauważyć, że „mod” odpowiada operatorowi % w większości języków programowania, oznaczając resztę z dzielenia. Na przykład $5 \pmod 3 = 2$ oraz $17 \pmod 4 = 1$.

Wejście

Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $N$.

Druga linia zawiera ciąg znaków o długości $N$, składający się ze znaków B i W. Jeśli $i$-ty znak to B, wierzchołek $i$ jest czarny. W przeciwnym razie jest biały. Gwarantuje się, że wierzchołek $1$ jest czarny, a wierzchołek $2$ jest biały.

Podzadania

Poniższa tabela przedstawia rozkład 25 dostępnych punktów:

Wyjście

W jednej linii wypisz liczbę możliwych list, modulo $10^9 + 7$.

Przykład 1

Wejście 1

4
BWWB

Wyjście 1

4

Uwagi

Graf wygląda następująco:

Ciągłe linie reprezentują niebieskie krawędzie, podczas gdy przerywane linie reprezentują czerwone krawędzie. Możliwe ścieżki to:

• $1 \to 2$
• $1 \to 3 \to 2$
• $1 \to 3 \to 4 \to 2$
• $1 \to 2 \to 3 \to 1 \to 2$

Ulubiony kolor jest czerwony w podkreślonych wierzchołkach, a niebieski w pozostałych.

Przykład 2

Wejście 2

12
BWBWBBBWWBBW

Wyjście 2

3377552