Дан граф с $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$.
• Для всех $i$, где $3 \le i \le N$, вершина $i$ встречается в списке не более одного раза.
• Для всех $j$, где $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