The ABC number of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:

* 1 ≤ i < j < k ≤ |T| (|T| is the length of T.)
* T_i = `A` (T_i is the i-th character of T from the beginning.)
* T_j = `B`
* T_k = `C`



For example, when T = `ABCBC`, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.

You are given a string S. Each character of S is `A`, `B`, `C` or `?`.

Let Q be the number of occurrences of `?` in S. We can make 3^Q strings by replacing each occurrence of `?` in S with `A`, `B` or `C`. Find the sum of the ABC numbers of all these strings.

This sum can be extremely large, so print the sum modulo 10^9 + 7.

Constraints

* 3 ≤ |S| ≤ 10^5
* Each character of S is `A`, `B`, `C` or `?`.

Input

Input is given from Standard Input in the following format:


S


Output

Print the sum of the ABC numbers of all the 3^Q strings, modulo 10^9 + 7.

Examples

Input

A??C


Output

8


Input

ABCBC


Output

3


Input

????C?????B??????A???????


Output

979596887
/*
String[]の初期化、整数の型がlongになっているか
関数（splitとかcontainsとか）内では"+"とかは正規表現となされるので"\\+"とする
'+'とかは問題ない
配列のコピーはarr1=arr.clone()
HashSet<>[]はおのおの初期化した？？？？？
負の数の割り算は絶対値が小さいほうに切り捨てられるex.-1/2=0ので、ある値>kみたいな式だとバグらせやすいので注意
ある値>=kとして、切り上げた値をとるべき
toLowerCase()はアルファベット以外に対して行ってもエラーにはならない
ArrayDequeではpopとpushはStackと同じ操作になる
//import static java.lang.System.*; はしばらく使わなそう(使うとしてもexit(0)のためだけ)←return;でよさそう
最後にout.flush()またはout.close()をするのを忘れずに！
Point2D p2d=new Point2D.Double(d1,d2);
*/
//入力終了→Ctrl+D
import java.util.*;
import java.io.*;
import java.awt.*;
import java.awt.geom.Point2D;
import static java.lang.Math.*;
public class Main {
    public static void main(String[] $) {
        String s=sc.next();
        int n=s.length();
        long[][][][] dp=new long[n+1][2][2][2];
        dp[0][0][0][0]=1;
        for (int i = 1; i <= n; i++) {
            dp[i][0][0][0] = dp[i - 1][0][0][0];
            if (s.charAt(i - 1) == 'A') {
                dp[i][1][0][0] = (dp[i - 1][0][0][0] + dp[i - 1][1][0][0]) % mod;
                dp[i][1][1][0] = dp[i - 1][1][1][0];
                dp[i][1][1][1] = dp[i - 1][1][1][1];
            } else if (s.charAt(i - 1) == 'B') {
                dp[i][1][0][0] = dp[i - 1][1][0][0];
                dp[i][1][1][0] = (dp[i - 1][1][0][0] + dp[i - 1][1][1][0]) % mod;
                dp[i][1][1][1] = dp[i - 1][1][1][1];
            } else if (s.charAt(i - 1) == 'C') {
                dp[i][1][0][0] = dp[i - 1][1][0][0];
                dp[i][1][1][0] = dp[i - 1][1][1][0];
                dp[i][1][1][1] = (dp[i - 1][1][1][0] + dp[i - 1][1][1][1]) % mod;
            } else {
                dp[i][1][0][0] = (3 * dp[i - 1][1][0][0] + dp[i - 1][0][0][0]) % mod;
                dp[i][1][1][0] = (3 * dp[i - 1][1][1][0] + dp[i - 1][1][0][0]) % mod;
                dp[i][1][1][1] = (3 * dp[i - 1][1][1][1] + dp[i - 1][1][1][0]) % mod;
                dp[i][0][0][0] = (3 * dp[i - 1][0][0][0]) % mod;
            }
        }
        /*
        for (int i = 0; i < pow(3, 4); i++) {
            String k=Integer.toString(i,3);
            while (k.length()<4)k="0"+k;
            for (int j = 0; j < k.length(); j++) {
                out.print((char)( k.charAt(j)-'0'+'A'));
            }
            out.println();
        }
        */
        out.println(dp[n][1][1][1]);
        out.close();
    }

    static long mod = (long) 1e9 + 7;

    static class COM {

        static long[] fact;
        static long[] inv;

        static void Init(int n) {
            fact = new long[n];
            inv = new long[n];
            fact[0] = inv[0] = 1;
            for (int i = 1; i < n; i++) {
                fact[i] = (fact[i - 1] * i) % mod;
                inv[i] = power(fact[i], mod - 2);
            }
        }

        static long C(int n, int k) {
            if (k > n) return 0;
            return ((fact[n] * inv[n - k]) % mod * inv[k]) % mod;
        }
    }

    static long power(long x, long n) {
        if (n == 0) return 1;
        if (n % 2 == 0) {
            long e = power(x, n / 2);
            return (e * e) % mod;
        }
        return (x * power(x, n - 1)) % mod;
    }

    //クラスカル法(0-indexed) n頂点m辺
    static HashSet<Integer> Kruskal(int[] u, int[] v, int[] cost, int n) {
        int m = u.length;
        UF.Init(n);
        PriorityQueue<Integer> S = new PriorityQueue<>((p1, p2) -> cost[p1] - cost[p2]);
        for (int i = 0; i < m; i++) {
            S.add(i);
        }
        //最小全域木をなす辺
        HashSet<Integer> F = new HashSet<>();
        while (!S.isEmpty()) {
            int e = S.poll();
            if (!UF.same(u[e], v[e])) {
                F.add(e);
                UF.unite(u[e], v[e]);
            }
        }
        return F;
    }

    //Union Find木(0-indexed)
    static class UF {
        static int[] d;

        static void Init(int size) {
            d = new int[size];
            for (int i = 0; i < size; i++) {
                d[i] = -1;
            }
        }

        static boolean unite(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return false;
            if (d[x] > d[y]) {
                int t = d[y];
                d[y] = d[x];
                d[x] = t;
            }
            d[x] += d[y];
            d[y] = x;
            return true;
        }

        static boolean same(int x, int y) {
            return find(x) == find(y);
        }

        static int find(int k) {
            return d[k] < 0 ? k : (d[k] = find(d[k]));
        }

        static int size(int k) {
            return -d[find(k)];
        }
    }

    static PrintWriter out = new PrintWriter(System.out);

    static class sc {
        static Scanner s = new Scanner(System.in);

        static String next() {
            return s.next();
        }

        static String nextLine() {
            return s.nextLine();
        }

        static int nextInt() {
            return Integer.parseInt(s.next());
        }

        static long nextLong() {
            return Long.parseLong(s.next());
        }

        static double nextDouble() {
            return Double.parseDouble(s.next());
        }

        static boolean hasNext() {
            return s.hasNext();
        }

        static boolean hasNextInt() {
            return s.hasNextInt();
        }

    }

}