$N$ 個のノードが $1$ から $N$ まで番号付けられたグラフがある。各ノードは黒または白に色付けされている。さらに、ノード $1$ は黒、ノード $2$ は白であることがわかっている。$i \neq j$ である任意の $i, 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$ について、ノード $i$ はリスト内に高々一度しか現れない。
• $3 \le j \le L$ を満たすすべての $j$ について、$l_{j-2} \neq l_j$ が成り立つ。

このようなリストの数は有限であることが証明できる。

なお、「mod」はほとんどのプログラミング言語における % 演算子に対応し、除算の余りを表す。例えば、$5 \pmod 3 = 2$、$17 \pmod 4 = 1$ である。

入力

入力の最初の行には、単一の整数 $N$ が含まれる。 次の行には、文字 B と W からなる長さ $N$ の文字列が含まれる。$i$ 番目の文字が B ならばノード $i$ は黒であり、そうでなければ白である。ノード $1$ は黒、ノード $2$ は白であることが保証されている。

小課題

出力

1行に、可能なリストの個数を $10^9 + 7$ を法として出力せよ。

入出力例

入力 1

4
BWWB

出力 1

4

注記

出力例 1 の説明： グラフは以下のようになる。

実線は青いエッジ、破線は赤いエッジを表す。可能な経路は以下の通りである。

• $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