有一個包含 $N$ 個節點的圖，節點編號從 $1$ 到 $N$。每個節點都被塗成黑色或白色。此外，已知節點 $1$ 是黑色，節點 $2$ 是白色。對於任何 $i$ 和 $j$（其中 $i \neq j$），存在一條從節點 $i$ 到 $j$ 的有向邊，該邊為紅色或藍色。其顏色由以下邏輯決定：

• 若 $i < j$ 且節點顏色相同，則為紅色。
• 若 $i < j$ 且節點顏色不同，則為藍色。
• 若 $i > j$ 且節點顏色相同，則為藍色。
• 若 $i > j$ 且節點顏色不同，則為紅色。

LoBren 的最愛顏色最初為藍色。接著他在圖上進行行走（注意行走允許重複經過頂點和邊）。他在行走時遵循以下規則：

• 如果他目前位於節點 $1$，他的最愛顏色變為藍色。
• 否則，如果他目前位於節點 $2$，他的最愛顏色變為紅色。
• 然後，他從當前節點沿著與他最愛顏色相同的出邊移動。可以證明這樣的邊一定存在。
• 最後，他可以選擇重複上述過程。

透過記錄他依序訪問的節點，他得到一個列表 $l_1, l_2, \dots, l_L$。請找出滿足以下條件的可能列表數量，並對 $10^9 + 7$ 取模：

• 列表以節點 $1$ 開始，以節點 $2$ 結束。
• 對於所有 $3 \le i \le N$，節點 $i$ 在列表中最多出現一次。
• 對於所有 $3 \le j \le L$，我們有 $l_{j-2} \neq l_j$。

可以證明此類列表的數量是有限的。

注意「mod」在大多數程式語言中對應於 % 運算子，表示除法後的餘數。例如，$5 \pmod 3 = 2$ 且 $17 \pmod 4 = 1$。

輸入格式

輸入的第一行包含一個整數 $N$。

下一行包含一個長度為 $N$ 的字串，由字元 B 和 W 組成。如果第 $i$ 個字元是 B，則節點 $i$ 為黑色。否則，它是白色。保證節點 $1$ 為黑色，節點 $2$ 為白色。

子任務

下表顯示了 25 分的分配方式：

輸出格式

在單行上輸出可能的列表數量，對 $10^9 + 7$ 取模。

範例

範例輸入 1

4
BWWB

範例輸出 1

4

說明

圖的結構如下：

實線代表藍色邊，虛線代表紅色邊。可能的路徑為：

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

在底線標示的節點處，最愛顏色為紅色，其餘情況為藍色。

範例輸入 2

12
BWBWBBBWWBBW

範例輸出 2

3377552