You are given a string s consisting of lowercase Latin letters “a”, “b” and “c” and question marks “?”.
Let the number of question marks in the string ss be kk. Let’s replace each question mark with one of the letters “a”, “b” and “c”. Here we can obtain all 3k3^k possible strings consisting only of letters “a”, “b” and “c”. For example, if s=“ac?b?c” then we can obtain the following strings: [“acabac”, “acabbc”, “acabcc”, “acbbac”, “acbbbc”, “acbbcc”, “accbac”, “accbbc”, “accbcc”].
Your task is to count the total number of subsequences “abc” in all resulting strings. Since the answer can be very large, print it modulo 109+710^9+7.
A subsequence of the string tt is such a sequence that can be derived from the string tt after removing some (possibly, zero) number of letters without changing the order of remaining letters. For example, the string “baacbc” contains two subsequences “abc” — a subsequence consisting of letters at positions (2,5,6)(2,5,6) and a subsequence consisting of letters at positions (3,5,6)(3,5,6).

Input

The first line of the input contains one integer nn (3≤n≤200000)(3≤n≤200000) — the length of ss.
The second line of the input contains the string ss of length nn consisting of lowercase Latin letters “a”, “b” and “c” and question marks"?".

Output

Print the total number of subsequences “abc” in all strings you can obtain if you replace all question marks with letters “a”, “b” and “c”, modulo 109+710^9+7.

Examples

input

1
2
6  
ac?b?c

output

1
24

input

1
2
7
???????

output

1
2835

input

1
2
9
cccbbbaaa

output

1
0

input

1
2
5
a???c

output

1
46

Note

In the first example, we can obtain 99 strings:

  • “acabac” — there are 22 subsequences “abc”,
  • “acabbc” — there are 44 subsequences “abc”,
  • “acabcc” — there are 44 subsequences “abc”,
  • “acbbac” — there are 22 subsequences “abc”,
  • “acbbbc” — there are 33 subsequences “abc”,
  • “acbbcc” — there are 44 subsequences “abc”,
  • “accbac” — there is 11 subsequence “abc”,
  • “accbbc” — there are 22 subsequences “abc”,
  • “accbcc” — there are 22 subsequences “abc”.

So, there are 2+4+4+2+3+4+1+2+2=242+4+4+2+3+4+1+2+2=24 subsequences “abc” in total.

Translation

给出一个由 ==a,b,c,?== 组成的字符串 ss, ?? 可以变为 a,b,ca,b,c 其中任何一个，求在 ss 的所有可能情况中共有多少子序列 “abc”。

Idea

用 ai,bi,ci,xia_i,b_i,c_i,x_i 分别表示 s1∼sis_1\sim s_i 中 a,b,c,?a,b,c,? 的个数。每次以 bb 为中心统计两边 a,ca,c 可取的个数。
枚举 ss 的第 ii 个字符 sis_i。若 sis_i 为 bb，分四种情况讨论：组成的 abcabc 无 ?? 参与，在 s1∼si−1s_1\sim s_{i-1} 中取一个 aa，在 si+1∼sns_{i+1}\sim s_n 中取一个 cc，此时每个 ?? 有三种可能，共有 3xn3^{x_n} 个串对此类情况产生贡献，总数为 ai−1(cn−ci)⋅3xna_{i-1}(c_{n}-c_i)\cdot3^{x_n}；用 ab?ab? 组成 abcabc，在 s1∼si−1s_1\sim s_{i-1} 中取一个 aa，在 si+1∼sns_{i+1}\sim s_n 中取一个 ??，共有 3xn−13^{x_n-1} 个串对此类情况产生贡献，总数为 ai−1(xn−xi)⋅3xn−1a_{i-1}(x_n-x_i)\cdot3^{x_n-1}；用 ?bc?bc 代替 abcabc，在 s1∼si−1s_1\sim s_{i-1} 中取一个 ??，在 si+1∼sns_{i+1}\sim s_n 中取一个 cc，共有 3xn−13^{x_n-1} 个串对此类情况产生贡献，总数为 xi−1(cn−ci)⋅3xn−1x_{i-1}(c_{n}-c_i)\cdot3^{x_n-1}；用 ?b??b? 代替 abcabc，在 s1∼si−1s_1\sim s_{i-1} 中取一个 ??，在 si+1∼sns_{i+1}\sim s_n 中取一个 ??，共有 3xn−23^{x_n-2} 个串对此类情况产生贡献，总数为 xi−1(xn−xi)⋅3xn−2x_{i-1}(x_{n}-x_i)\cdot3^{x_n-2}。若 sis_i 为 ??，那么就令 ?? 为 bb，此处仍然分四种情况讨论：用 a?ca?c 代替 abcabc，在 s1∼si−1s_1\sim s_{i-1} 中取一个 aa，在 si+1∼sns_{i+1}\sim s_n 中取一个 cc，共有 3xn−13^{x_n-1} 个串对此类情况产生贡献，总数为 ai−1(cn−ci)⋅3xn−1a_{i-1}(c_{n}-c_i)\cdot3^{x_n-1}；用 ??c??c 代替 abcabc，在 s1∼si−1s_1\sim s_{i-1} 中取一个 ??，在 si+1∼sns_{i+1}\sim s_n 中取一个 cc，共有 3xn−23^{x_n-2} 个串对此类情况产生贡献，总数为 xi−1(cn−ci)⋅3xn−2x_{i-1}(c_{n}-c_i)\cdot3^{x_n-2}；用 a??a?? 代替 abcabc，在 s1∼si−1s_1\sim s_{i-1} 中取一个 aa，在 si+1∼sns_{i+1}\sim s_n 中取一个 ??，共有 3xn−23^{x_n-2} 个串对此类情况产生贡献，总数为 ai−1(xn−xi)⋅3xn−2a_{i-1}(x_{n}-x_i)\cdot3^{x_n-2}；用 ?????? 代替 abcabc，在 s1∼si−1s_1\sim s_{i-1} 中取一个 ??，在 si+1∼sns_{i+1}\sim s_n 中取一个 ??，共有 3xn−33^{x_n-3} 个串对此类情况产生贡献，总数为 xi−1(xn−xi)⋅3xn−3x_{i-1}(x_{n}-x_i)\cdot3^{x_n-3}。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1426F
Date: 10/9/2020
Description: Count
*******************************************************************/
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=200004;
const int mod=1000000007;
ll power[N];
int n;
char s[N];
ll a[N],b[N],c[N],x[N];
int main(){
	cin>>n>>(s+1);
	int i;
	power[0]=1;
	for(i=1;i<N;i++){
		power[i]=power[i-1]*3%mod;
	}
	for(i=1;i<=n;i++){
		a[i]=a[i-1]+(s[i]=='a');
		b[i]=b[i-1]+(s[i]=='b');
		c[i]=c[i-1]+(s[i]=='c');
		x[i]=x[i-1]+(s[i]=='?');
	}
	ll ans=0;
	for(i=1;i<=n;i++){
		if(s[i]=='b'){
			if(x[n]>=0){
				//abc
				ans=(ans+a[i-1]*(c[n]-c[i])%mod*power[x[n]]%mod)%mod;
			}
			if(x[n]>=1){
				//ab? ?bc
				ans=(ans+a[i-1]*(x[n]-x[i])%mod*power[x[n]-1]%mod)%mod;
				ans=(ans+x[i-1]*(c[n]-c[i])%mod*power[x[n]-1]%mod)%mod;
			}
			if(x[n]>=2){
				//?b?
				ans=(ans+x[i-1]*(x[n]-x[i])%mod*power[x[n]-2]%mod)%mod;
			}

		}else if(s[i]=='?'){
			if(x[n]>=1){
				//a?c->abc
				ans=(ans+a[i-1]*(c[n]-c[i])%mod*power[x[n]-1]%mod)%mod;
			}
			if(x[n]>=2){
				//??c->abc
				ans=(ans+x[i-1]*(c[n]-c[i])%mod*power[x[n]-2]%mod)%mod;
				//a??->abc
				ans=(ans+a[i-1]*(x[n]-x[i])%mod*power[x[n]-2]%mod)%mod;
			}
			if(x[n]>=3){
				ans=(ans+x[i-1]*(x[n]-x[i])%mod*power[x[n]-3]%mod)%mod;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}