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.
/**
 * BaZ :D
 */

import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main
{
    static MyScanner scan;
    static PrintWriter pw;
    static long MOD = 1_000_000_007;
    static long INF = 2_000_000_000_000_000_000L;
    static long inf = 2_000_000_000;
    public static void main(String[] args) {
        new Thread(null, null, "BaZ", 1 << 27) {
            public void run() {
                try {
                    solve();
                } catch (Exception e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }

    static void solve() throws IOException
    {
        //initIo(true, "");
        initIo(false, "");
        StringBuilder sb = new StringBuilder();
        int n = ni();
        String s = ne();
        long dp[][] = new long[n+1][4];
        dp[0][0] = 1;
        for(int i=1;i<=n;++i) {
            char c = s.charAt(i-1);
            if(c == '?') {
                dp[i][0] = 3*dp[i-1][0];
                dp[i][1] = dp[i-1][0] + 3*dp[i-1][1];
                dp[i][2] = dp[i-1][1] + 3*dp[i-1][2];
                dp[i][3] = dp[i-1][2] + 3*dp[i-1][3];
            }
            else if(c == 'a') {
                dp[i][0] = dp[i-1][0];
                dp[i][1] = dp[i-1][0] + dp[i-1][1];
                dp[i][2] = 0 + dp[i-1][2];
                dp[i][3] = 0 + dp[i-1][3];
            }
            else if(c == 'b') {
                dp[i][0] = dp[i-1][0];
                dp[i][1] = 0 + dp[i-1][1];
                dp[i][2] = dp[i-1][1] + dp[i-1][2];
                dp[i][3] = 0 + dp[i-1][3];
            }
            else {
                dp[i][0] = dp[i-1][0];
                dp[i][1] = 0 + dp[i-1][1];
                dp[i][2] = 0 + dp[i-1][2];
                dp[i][3] = dp[i-1][2] + dp[i-1][3];
            }
            dp[i][0]%=MOD;
            dp[i][1]%=MOD;
            dp[i][2]%=MOD;
            dp[i][3]%=MOD;
        }
        //pa("DP", dp);
        pl(dp[n][3]);
        pw.flush();
        pw.close();
    }

    static void assert_in_range(String varName, int n, int l, int r) {
        if (n >=l && n<=r) return;
        System.out.println(varName + " is not in range. Actual: "+n+" l : "+l+" r: "+r);
        System.exit(1);
    }
    static void assert_in_range(String varName, long n, long l, long r) {
        if (n>=l && n<=r) return;
        System.out.println(varName + " is not in range. Actual: "+n+" l : "+l+" r: "+r);
        System.exit(1);
    }

    static void initIo(boolean isFileIO, String suffix) throws IOException {
        scan = new MyScanner(isFileIO, suffix);
        if(isFileIO) {
            pw = new PrintWriter("/Users/amandeep/Desktop/output"+suffix+".txt");
        }
        else {
            pw = new PrintWriter(System.out, true);
        }
    }
    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static String ne() throws IOException
    {
        return scan.next();
    }
    static String nel() throws IOException
    {
        return scan.nextLine();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static void pa(String arrayName, Object arr[])
    {
        pl(arrayName+" : ");
        for(Object o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, int arr[])
    {
        pl(arrayName+" : ");
        for(int o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, long arr[])
    {
        pl(arrayName+" : ");
        for(long o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, double arr[])
    {
        pl(arrayName+" : ");
        for(double o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, char arr[])
    {
        pl(arrayName+" : ");
        for(char o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, boolean arr[])
    {
        pl(arrayName+" : ");
        for(boolean o : arr)
            p(o);
        pl();
    }
    static void pa(String listName, List list)
    {
        pl(listName+" : ");
        for(Object o : list)
            p(o);
        pl();
    }
    static void pa(String arrayName, Object[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(Object o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, int[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(int o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, long[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(long o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, char[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(char o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, double[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(double o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, boolean[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(boolean o : arr[i])
                p(o);
            pl();
        }
    }
    static class MyScanner
    {
        BufferedReader br;
        StringTokenizer st;
        MyScanner(boolean readingFromFile, String suffix) throws IOException
        {
            if(readingFromFile) {
                br = new BufferedReader(new FileReader("/Users/amandeep/Desktop/input"+suffix+".txt"));
            }
            else {
                br = new BufferedReader(new InputStreamReader(System.in));
            }
        }
        String nextLine()throws IOException
        {
            return br.readLine();
        }
        String next() throws IOException
        {
            if(st==null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        int nextInt() throws IOException
        {
            return Integer.parseInt(next());
        }
        long nextLong() throws IOException
        {
            return Long.parseLong(next());
        }
        double nextDouble() throws IOException
        {
            return Double.parseDouble(next());
        }
    }
}