该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T2. 粉刷栅栏 (fence)

题目描述

小明帮爷爷粉刷一排 $N$ 块栅栏。他有 $3$ 种颜色的油漆：红色（R）、绿色（G）、蓝色（B）。刷漆的规则是：

• 相邻两块栅栏不能刷相同颜色。
• 有些栅栏已经提前刷好了颜色，这些栅栏的颜色不能改变。

请你帮小明计算，一共有多少种不同的刷漆方案。答案可能很大，请对 $10^9+7$ 取模。

输入格式

第一行一个整数 $N$。

第二行一个长度为 $N$ 的字符串，由 R、G、B、? 组成。R/G/B 表示该栅栏已固定为该颜色，? 表示该栅栏可以任意选择颜色。

输出格式

一行一个整数，表示方案数模 $10^9+7$。

样例

样例 #1

3
???

12

解释：3块栅栏任意刷，每块可选3种颜色，但相邻不同。第1块3种选择，第2块2种，第3块2种，共 $3\times 2\times 2=12$。

数据范围

对于全部数据，$1\le N\le 10^5$，固定颜色数不超过 $1000$。