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 3^{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 10^{9} + 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 ≤ 200 000) — 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 10^{9} + 7.

Examples

Input


6
ac?b?c


Output


24


Input


7
???????


Output


2835


Input


9
cccbbbaaa


Output


0


Input


5
a???c


Output


46

Note

In the first example, we can obtain 9 strings:

  * "acabac" — there are 2 subsequences "abc", 
  * "acabbc" — there are 4 subsequences "abc", 
  * "acabcc" — there are 4 subsequences "abc", 
  * "acbbac" — there are 2 subsequences "abc", 
  * "acbbbc" — there are 3 subsequences "abc", 
  * "acbbcc" — there are 4 subsequences "abc", 
  * "accbac" — there is 1 subsequence "abc", 
  * "accbbc" — there are 2 subsequences "abc", 
  * "accbcc" — there are 2 subsequences "abc". 



So, there are 2 + 4 + 4 + 2 + 3 + 4 + 1 + 2 + 2 = 24 subsequences "abc" in total.
import java.util.*;
import java.io.*;
import java.text.*;

public class CF_1426_F{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        String s = n();
        long MOD = (long)1e9+7;
        int[] fa = new int[1+N], fc = new int[1+N], fq = new int[1+N];
        for(int i = 1; i<= N; i++){
            fa[i] = fa[i-1]+ (s.charAt(i-1) == 'a'?1:0);
            fc[i] = fc[i-1]+ (s.charAt(i-1) == 'c'?1:0);
            fq[i] = fq[i-1]+ (s.charAt(i-1) == '?'?1:0);
        }
        long ans = 0;
        for(int i = 2; i< N; i++){
            long a = fa[i-1], c = fc[N]-fc[i];
            long q1 = fq[i-1], q2 = fq[N]-fq[i];
            if(s.charAt(i-1) == 'b' || s.charAt(i-1) == '?'){
                if(Math.min(q1, q2) > 0){
                    ans += q1*q2%MOD*pow(3, q1+q2-2, MOD)%MOD;
                }
                if(ans >= MOD)ans %= MOD;
                if(Math.min(a, c) > 0){
                    ans += a*c%MOD*pow(3, q1+q2, MOD)%MOD;
                }
                if(ans >= MOD)ans %= MOD;
                if(Math.min(a, q2) > 0){
                    ans += a*q2%MOD * pow(3, q1+q2-1, MOD)%MOD;
                }
                if(ans >= MOD)ans %= MOD;
                if(Math.min(q1, c) > 0){
                    ans += c*q1%MOD * pow(3, q1+q2-1, MOD)%MOD;
                }
                if(ans >= MOD)ans %= MOD;
            }
        }
        pn(ans);
    }
    long pow(long a, long p, long MOD){
        long o = 1;
        for(; p> 0; p>>=1){
            if((p&1)==1)o = o*a%MOD;
            a = a*a%MOD;
        }
        return o;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    static void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
    final long IINF = (long)1e17;
    final int INF = (int)1e9+2;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-8;
    static boolean multipleTC = false, memory = true, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        long ct = System.currentTimeMillis();
        if (fileIO) {
            in = new FastReader("");
            out = new PrintWriter("");
        } else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = multipleTC? ni():1;
        pre();
        for (int t = 1; t <= T; t++) solve(t);
        out.flush();
        out.close();
        System.err.println(System.currentTimeMillis() - ct);
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new CF_1426_F().run();}catch(Exception e){e.printStackTrace();System.exit(1);}}}, "1", 1 << 28).start();
        else new CF_1426_F().run();
    }
    int[][] make(int n, int e, int[] from, int[] to, boolean f){
        int[][] g = new int[n][];int[]cnt = new int[n];
        for(int i = 0; i< e; i++){
            cnt[from[i]]++;
            if(f)cnt[to[i]]++;
        }
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
        for(int i = 0; i< e; i++){
            g[from[i]][--cnt[from[i]]] = to[i];
            if(f)g[to[i]][--cnt[to[i]]] = from[i];
        }
        return g;
    }
    int[][][] makeS(int n, int e, int[] from, int[] to, boolean f){
        int[][][] g = new int[n][][];int[]cnt = new int[n];
        for(int i = 0; i< e; i++){
            cnt[from[i]]++;
            if(f)cnt[to[i]]++;
        }
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]][];
        for(int i = 0; i< e; i++){
            g[from[i]][--cnt[from[i]]] = new int[]{to[i], i, 0};
            if(f)g[to[i]][--cnt[to[i]]] = new int[]{from[i], i, 1};
        }
        return g;
    }
    int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object... o){for(Object oo:o)out.print(oo+" ");}
    void pn(Object... o){for(int i = 0; i< o.length; i++)out.print(o[i]+(i+1 < o.length?" ":"\n"));}
    void pni(Object... o){for(Object oo:o)out.print(oo+" ");out.println();out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str;
            try{
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }
            return str;
        }
    }
}