$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$이 주어진다.

다음 줄에는 $N$ 길이의 문자열이 주어지며, 이는 'B'와 'W' 문자로 구성된다. $i$번째 문자가 'B'이면 노드 $i$는 검은색이다. 그렇지 않으면 흰색이다. 노드 $1$은 검은색이고 노드 $2$는 흰색임이 보장된다.

서브태스크

출력

한 줄에 가능한 리스트의 개수를 $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