Codeforces Round #674 (Div. 3) F. Number of Subsequences

题目链接

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 s be k. Let’s replace each question mark with one of the letters “a”, “b” and “c”. Here we can obtain all 3k 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+7.

A subsequence of the string t is such a sequence that can be derived from the string t 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) and a subsequence consisting of letters at positions (3,5,6).

Input

The first line of the input contains one integer n (3≤n≤200000) — the length of s.

The second line of the input contains the string s of length n 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+7.

Examples

input

6 ac?b?c

output

24

input

7 ???????

output

2835

input

9 cccbbbaaa

output

0

input

5 a???c

output

46

简单 DP~ 我是直接手推的，首先我们可以想想怎么找一个字符串里某个子序列的个数，这个非常经典，不再赘述，我就拿样例一来推一下： $dp[1,3]$ 表示 $[a,c]$ 的字符个数

ac?b?c a b c 1 1 0 0 dp[0]=1,dp[1]+=dp[0] 2 1 0 0 dp[3]+=dp[2] 3 4 1 0 dp[1]=3*dp[1]+dp[0],dp[0]=3 4 4 5 0 dp[2]+=dp[1] 5 15 19 5 dp[3]=3*dp[3]+dp[2] dp[2]=3*dp[2]+dp[1] dp[1]=3*dp[1]+dp[0] 6 15 19 24 dp[3]+=dp[2]

很容易发现，当 $i$ 位置的字符为字母时，状态转移方程为： $$dp[i{-}^{\prime }{a}^{\prime }+1]=dp[i{-}^{\prime }{a}^{\prime }+1]+dp[i{-}^{\prime }{a}^{\prime }]$$ 当为问号时，状态转移方程为： $$dp[j]=3\ast dp[j]+dp[j-1],j\in [3,1]$$ 不难发现关键点就是 $dp[0]$，很容易发现 $dp[0]$ 和问号的个数 $cnt$ 有关，即： $$dp[0]=3^{cnt}$$ AC代码如下：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int N=2e5+5; ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;} ll n,cnt=0,dp[4],pow3[N]; string s; void init(){ pow3[0]=1; for(ll i=1;i<=200000;i++) pow3[i]=pow3[i-1]*3%mod; } int main(){ init(); cin>>n>>s; dp[0]=1; for(auto i:s){ if(isalpha(i)){ dp[i-'a'+1]=(dp[i-'a'+1]+dp[i-'a'])%mod; }else{ for(int j=3;j>=1;j--){ dp[j]=(3*dp[j]+dp[j-1])%mod; } cnt++; dp[0]=pow3[cnt]; } } cout<<dp[3]; return 0; }