성간 구간

3000년, Bessie는 우주에 나간 최초의 소가 되었다. 별들 사이를 여행하던 중 그녀는 $N$개의 점($2 \leq N \leq 5 \cdot 10^5$)이 놓인 수직선을 발견한다. 점들은 $1$번부터 $N$번까지 번호가 매겨져 있다. 처음에는 모든 점이 흰색이다. 그녀는 다음 연산을 원하는 만큼 몇 번이든 수행할 수 있다.

• 수직선 위의 위치 $i$와 양의 정수 $x$를 고른다. $[i, i+x-1]$ 구간의 모든 점을 빨간색으로, $[i+x, i+2x-1]$ 구간의 모든 점을 파란색으로 칠한다. 선택한 구간들은 서로 겹치지 않아야 하므로, $[i, i+2x-1]$ 안의 점이 이미 빨간색이나 파란색이면 안 된다. 전체 구간은 수직선 안에 있어야 한다($1 \leq i \leq i+2x-1 \leq N$).

Farmer John은 R, B, X로 이루어진 길이 $N$의 문자열 $s$를 Bessie에게 준다. $s_i = R$이면 $i$번 점은 빨간색이어야 한다. $s_i = B$이면 $i$번 점은 파란색이어야 한다. $s_i = X$이면 $i$번 점의 색에는 제약이 없다.

Farmer John의 선호를 만족하는 서로 다른 색칠 방법의 수를 구하라. 적어도 한 점의 색이 다르면 두 색칠 방법은 다른 것으로 본다. 답이 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

첫 줄에 정수 $N$이 주어진다. 다음 줄에 문자열 $s$가 주어진다.

선호를 만족하는 색칠 방법의 수를 $10^9+7$로 나눈 나머지로 출력한다.