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.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        MyReader reader = new MyReader(System.in);
//        MyReader reader = new MyReader(new FileInputStream("input.txt"));
        MyWriter writer = new MyWriter(System.out);
        new Main().run(reader, writer);
        writer.close();
    }

    private void run(MyReader reader, MyWriter writer) throws Exception {
        int t = 1;
        for (int i = 0; i < t; i++) {
            int n = reader.nextInt();
            char[] s = reader.nextCharArray();
            int k = 0;
            long mod = 1_000_000_007;
            long[] ac = new long[n];
            long[] cc = new long[n];
            long[] qcl = new long[n];
            long[] qcr = new long[n];
            for (int j = 0; j < n; j++) {
                if (j > 0) {
                    qcl[j] = qcl[j - 1];
                    ac[j] = ac[j - 1];
                }
                if (s[j] == '?') {
                    k++;
                    qcl[j]++;
                }
                if (s[j] == 'a') {
                    ac[j]++;
                }
            }
            for (int j = n - 1; j >= 0; j--) {
                if (j < n - 1) {
                    qcr[j] = qcr[j + 1];
                    cc[j] = cc[j + 1];
                }
                if (s[j] == '?') {
                    qcr[j]++;
                }
                if (s[j] == 'c') {
                    cc[j]++;
                }
            }
            long[] q = new long[k + 1];
            q[0] = 1;
            for (int j = 1; j <= k; j++) {
                q[j] = q[j - 1] * 3 % mod;
            }
            long ans = 0;
            for (int j = 0; j < n; j++) {
                int ww = 0;
                if (s[j] == 'b' || s[j] == '?') {
                    if (s[j] == '?') {
                        ww++;
                    }
                    ans += ac[j] * cc[j] % mod * q[k - ww] % mod;
                    if (k - ww >= 1) {
                        ans += (qcl[j] - ww) * cc[j] % mod * q[k - ww - 1] % mod;
                        ans += ac[j] * (qcr[j] - ww) % mod * q[k - ww - 1] % mod;
                    }
                    if (k - ww >= 2) {
                        ans += (qcl[j] - ww) * (qcr[j] - ww) % mod * q[k - ww - 2] % mod;
                    }
                    ans %= mod;
                }
            }
            writer.println(ans);
        }
    }

    class Pair<T> extends Pair2<T, T> {

        public Pair(T x, T y) {
            super(x, y);
        }
    }

    class Pair2<T, U> {

        T x;
        U y;

        public Pair2(T x, U y) {
            this.x = x;
            this.y = y;
        }
    }

    public class DSU {

        int n;
        int[] p;
        int[] r;

        DSU(int n) {
            this.n = n;
            p = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = i;
            }
            r = new int[n];
        }

        int get(int x) {
            if (p[x] != x) {
                p[x] = get(p[x]);
            }
            return p[x];
        }

        void union(int x, int y) {
            x = get(x);
            y = get(y);
            if (x == y) {
                return;
            }
            if (r[x] == r[y]) {
                r[x]++;
            }
            if (r[x] < r[y]) {
                p[x] = y;
            } else {
                p[y] = x;
            }
        }
    }

    public class Graph<T> {

        int counter = 0;
        List<Node> nodes = new ArrayList<>();
        List<Long> dist;

        void initNodes(int n) {
            for (int i = 0; i < n; i++) {
                nodes.add(new Node());
            }
        }

        void addNode(T obj) {
            nodes.add(new Node(obj));
        }

        void addEdge(int i, int j, boolean oriented) {
            addEdge(i, j, 0, oriented);
        }

        void addEdge(int i, int j, long w, boolean oriented) {
            Node from = nodes.get(i);
            Node to = nodes.get(j);
            addEdge(from, to, w, oriented);
        }

        void addEdge(Node from, Node to, boolean oriented) {
            addEdge(from, to, 0, oriented);
        }

        void addEdge(Node from, Node to, long w, boolean oriented) {
            Edge edge = new Edge(from, to, w);
            from.edges.add(edge);
            if (!oriented) {
                Edge rev = new Edge(to, from, w);
                to.edges.add(rev);
            }
        }

        long mst() {
            List<Edge> list = new ArrayList<>();
            for (Node node : nodes) {
                list.addAll(node.edges);
            }
            list.sort((e1, e2) -> (int) (e1.w - e2.w));
            DSU dsu = new DSU(nodes.size());
            long weight = 0;
            for (Edge edge : list) {
                if (dsu.get(edge.from.i) != dsu.get(edge.to.i)) {
                    weight += edge.w;
                    dsu.union(edge.from.i, edge.to.i);
                }
            }
            return weight;
        }

//    void dijkstra() {
//        PriorityQueue<Main.Pair2<Node, Long>> queue = new PriorityQueue<>((o1, o2) -> (int) (o1.y - o2.y));
//        queue.add(new Main.Pair2<>(nodes.get(0), 0L));
//        while (!queue.isEmpty()) {
//            Main.Pair2<Node, Long> p = queue.poll();
//            Node n = p.x;
//            long d = p.y;
//            if (n.dist != -1) {
//                continue;
//            }
//            n.dist = d;
//            for (Edge edge : n.edges) {
//                queue.add(new Main.Pair2<>(edge.to, d + edge.w));
//            }
//        }
//    }

        class Node {

            int i;
            T obj;
            List<Edge> edges = new ArrayList<>();
            long dist = -1;

            public Node() {
                this(null);
            }

            public Node(T obj) {
                this.i = counter++;
                this.obj = obj;
            }
        }

        class Edge {

            long w;
            Node from;
            Node to;

            public Edge(Node from, Node to) {
                this(from, to, 0);
            }

            public Edge(Node from, Node to, long w) {
                this.from = from;
                this.to = to;
                this.w = w;
            }
        }
    }


    public static class MyReader {

        final BufferedInputStream in;
        final int bufSize = 1 << 16;
        final byte[] buf = new byte[bufSize];
        int i = bufSize;
        int k = bufSize;
        boolean end = false;
        final StringBuilder str = new StringBuilder();

        MyReader(InputStream in) {
            this.in = new BufferedInputStream(in, bufSize);
        }

        int nextInt() throws IOException {
            return (int) nextLong();
        }

        int[] nextIntArray(int n) throws IOException {
            int[] m = new int[n];
            for (int i = 0; i < n; i++) {
                m[i] = nextInt();
            }
            return m;
        }

        int[][] nextIntMatrix(int n, int m) throws IOException {
            int[][] a = new int[n][0];
            for (int j = 0; j < n; j++) {
                a[j] = nextIntArray(m);
            }
            return a;
        }

        long nextLong() throws IOException {
            int c;
            long x = 0;
            int sign = 1;
            while ((c = nextChar()) <= 32) ;
            if (c == '-') {
                sign = -1;
                c = nextChar();
            }
            if (c == '+') {
                c = nextChar();
            }
            while (c >= '0') {
                x = x * 10 + (c - '0');
                c = nextChar();
            }
            return sign * x;
        }

        long[] nextLongArray(int n) throws IOException {
            long[] m = new long[n];
            for (int i = 0; i < n; i++) {
                m[i] = nextLong();
            }
            return m;
        }

        int nextChar() throws IOException {
            if (i == k) {
                k = in.read(buf, 0, bufSize);
                i = 0;
            }
            return i >= k ? -1 : buf[i++];
        }

        String nextString() throws IOException {
            if (end) {
                return null;
            }
            str.setLength(0);
            int c;
            while ((c = nextChar()) <= 32 && c != -1) ;
            if (c == -1) {
                end = true;
                return null;
            }
            while (c > 32) {
                str.append((char) c);
                c = nextChar();
            }
            return str.toString();
        }

        String nextLine() throws IOException {
            if (end) {
                return null;
            }
            str.setLength(0);
            int c = nextChar();
            while (c != '\n' && c != '\r' && c != -1) {
                str.append((char) c);
                c = nextChar();
            }
            if (c == -1) {
                end = true;
                if (str.length() == 0) {
                    return null;
                }
            }
            if (c == '\r') {
                nextChar();
            }
            return str.toString();
        }

        char[] nextCharArray() throws IOException {
            return nextString().toCharArray();
        }

        char[][] nextCharMatrix(int n) throws IOException {
            char[][] a = new char[n][0];
            for (int i = 0; i < n; i++) {
                a[i] = nextCharArray();
            }
            return a;
        }
    }

    public static class MyWriter {

        final BufferedOutputStream out;
        final int bufSize = 1 << 16;
        final byte buf[] = new byte[bufSize];
        int i = 0;
        final byte c[] = new byte[30];
        static final String newLine = System.getProperty("line.separator");

        MyWriter(OutputStream out) {
            this.out = new BufferedOutputStream(out, bufSize);
        }

        void print(long x) throws IOException {
            int j = 0;
            if (i + 30 >= bufSize) {
                flush();
            }
            if (x < 0) {
                buf[i++] = (byte) ('-');
                x = -x;
            }
            do {
                c[j++] = (byte) (x % 10 + '0');
                x /= 10;
            } while (x != 0);
            while (--j >= 0) {
                buf[i++] = c[j];
            }
        }

        void println(long x) throws IOException {
            print(x);
            println();
        }

        void print(int[] m) throws IOException {
            for (int a : m) {
                print(a);
                print(' ');
            }
        }

        void print(long[] m) throws IOException {
            for (long a : m) {
                print(a);
                print(' ');
            }
        }

        void print(String s) throws IOException {
            for (int i = 0; i < s.length(); i++) {
                print(s.charAt(i));
            }
        }

        void print(char x) throws IOException {
            if (i == bufSize) {
                flush();
            }
            buf[i++] = (byte) x;
        }

        void print(char[] m) throws IOException {
            for (char c : m) {
                print(c);
            }
        }

        void println(String s) throws IOException {
            print(s);
            println();
        }

        void println() throws IOException {
            print(newLine);
        }

        void flush() throws IOException {
            out.write(buf, 0, i);
            out.flush();
            i = 0;
        }

        void close() throws IOException {
            flush();
            out.close();
        }
    }
}