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.
// package CodeForces;

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;

public class Round674F {

	public static final long mod = (long)1e9 + 7;
	public static long[] fact;
	public static long[] infact;
	public static final int max = (int)2e5 + 100;
	public static long[] pow3;
	
	public static void Pre() {
		fact = new long[max];
		infact = new long[max];
		pow3 = new long[max];
		fact[0] = infact[0] = pow3[0] = 1;
		for(int i = 1; i < max; i++) {
			fact[i] = (fact[i - 1] * (long)i)%mod;
			infact[i] = (infact[i - 1] * (long)ModInverse(i, mod))%mod;
			pow3[i] = (pow3[i - 1] * 3L)%mod;
		}
	}
	
	public static long nCr(int n, int r) {
		if(n < r) {
			return 0;
		}
		return (((fact[n] * infact[r])%mod) * infact[n - r])%mod;
	}
	
	public static long add(long a, long b) {
		long sum = a + b;
		if(sum >= mod) sum -= mod;
		return sum;
	}
	
	public static long mul(long a, long b) {
		return (a*b)%mod;
	}
	
	public static long Power(int a) {
		if(a < 0) {
			return 0;
		}
		return pow3[a];
	}
	
	public static void solve() {
		Pre();
		int n = s.nextInt();
		String str = s.next();
		int[] A = new int[n];
		int[] C = new int[n];
		int[] Q = new int[n];
		for(int i = 0; i < n; i++) {
			if(i != 0) {
				A[i] = A[i - 1];
				C[i] = C[i - 1];
				Q[i] = Q[i - 1];
			}
			if(str.charAt(i) == 'a') {
				A[i]++;
			}else if(str.charAt(i) == 'c') {
				C[i]++;
			}else if(str.charAt(i) == '?') {
				Q[i]++;
			}
		}
		long ans = 0;
		for(int i = 0; i < n; i++) {
			if(str.charAt(i) == '?') {
				// both given
				ans = add(ans, mul(mul(Range_val(A, 0, i - 1), Range_val(C, i + 1, n - 1)), Power(Q[n - 1] - 1)));
				// A given, C not given
				ans = add(ans, mul(Range_val(A, 0, i - 1), mul(nCr(Range_val(Q, i + 1, n - 1), 1), Power(Q[n - 1] - 2))));
				// A not given, C given
				ans = add(ans, mul(mul(nCr(Range_val(Q, 0, i - 1), 1), Power(Q[n - 1] - 2)), Range_val(C, i + 1, n - 1)));
				// A not given, C not given
				ans = add(ans, mul(Power(Q[n - 1] - 3), mul(Range_val(Q, 0, i - 1), Range_val(Q, i + 1, n - 1))));
			}else if(str.charAt(i) == 'b') {
				// both given
				ans = add(ans, mul(Power(Q[n - 1]), mul(Range_val(A, 0, i - 1), Range_val(C, i + 1, n - 1))));
				// A given, C not given
				ans = add(ans, mul(Range_val(A, 0, i - 1), mul(nCr(Range_val(Q, i + 1, n - 1), 1), Power(Q[n - 1] - 1))));
				// A not given, C given
				ans = add(ans, mul(mul(nCr(Range_val(Q, 0, i - 1), 1), Power(Q[n - 1] - 1)), Range_val(C, i + 1, n - 1)));
				// A not given, C not given
				ans = add(ans, mul(Power(Q[n - 1] - 2), mul(Range_val(Q, 0, i - 1), Range_val(Q, i + 1, n - 1))));
			}
		}
		out.println(ans);
	}
	
	public static int Range_val(int[] prefix, int l, int r) {
		if(l > r) {
			return 0;
		}
		return prefix[r] - (l - 1 >= 0 ? prefix[l - 1] : 0);
	}

	public static void main(String[] args) {
		new Thread(null, null, "Thread", 1 << 27) {
			public void run() {
				try {
					out = new PrintWriter(new BufferedOutputStream(System.out));
					s = new FastReader(System.in);
					solve();
					out.close();
				} catch (Exception e) {
					e.printStackTrace();
					System.exit(1);
				}
			}
		}.start();
	}

	public static class Triplet {
		long gcd;
		long x;
		long y;

		Triplet(long gcd, long x, long y) {
			this.gcd = gcd;
			this.x = x;
			this.y = y;
		}
	}

	public static Triplet ExtendedEuclideanAlgo(long a, long b) {
		if (a == 0) {
			return new Triplet(b, 0, 1);
		}
		Triplet ans = ExtendedEuclideanAlgo(b % a, a);
		long x = ans.y - (b / a) * ans.x;
		long y = ans.x;
		return new Triplet(ans.gcd, x, y);
	}

	public static long ModInverse(long a, long m) {
		Triplet ans = ExtendedEuclideanAlgo(a, m);
		if (ans.gcd != 1) {
			throw null;
		} else {
			long result = (ans.x % m + m) % m;
			return result;
		}
	}
	
	public static PrintWriter out;
	public static FastReader s;

	public static class FastReader {

		private InputStream stream;
		private byte[] buf = new byte[4096];
		private int curChar, snumChars;

		public FastReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (snumChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException E) {
					throw new InputMismatchException();
				}
			}
			if (snumChars <= 0) {
				return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int number = 0;
			do {
				number *= 10;
				number += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			long sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long number = 0;
			do {
				number *= 10L;
				number += (long) (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextLong();
			}
			return arr;
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndofLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndofLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}

	
}
