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.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.ObjectInputStream.GetField;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class N674 {
	static PrintWriter out;
	static Scanner sc;
	static ArrayList<Integer>q,w;
	static ArrayList<Integer>adj[];
	static HashSet<Integer>primesH;
	static boolean prime[];
	//static ArrayList<Integer>a;
	static HashSet<Long>tmp;
	static long[]threes;
	static int[]c,d;
	static int[][]dp;
	static char[][]mp;
	static int A,B,n,m,h,ans;
	//static String a,b;
	static long oo=(long)1e9+7;
	public static void main(String[]args) throws IOException {
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
		//A();
	//	B();
	  // C();
		//D();
	//E();
		F();
		//G();
		out.close();
	}
	  private static void A() throws IOException {
		  int t=ni();
			while(t-->0) {
				int n=ni(),x=ni();
				int fl=1;
				int cur=3;
				while(cur<=n) {
					fl++;
					cur+=x;
				}
				ol(fl);
			}
		
	   }
		static void B() throws IOException {
			int t=ni();
			while(t-->0) {
				int n=ni(),m=ni();
				int[][]tiles=new int[n][4];
				for(int i=0;i<n;i++) {
					tiles[i][0]=ni();
					tiles[i][1]=ni();
					tiles[i][2]=ni();
					tiles[i][3]=ni();
				}
				if(m%2==1) {
					ol("NO");
				}
				else {
					boolean sym=false,half=false;
					for(int i=0;i<n;i++) {
						if(tiles[i][1]==tiles[i][2]) {
						//	if(tiles[i][0]==tiles[i][3]) {
								sym=true;
						//	}
						}
					}
//					for(int i=0;i<n&&!sym;i++) {
//						for(int j=i;j<n;j++) {
//							if(tiles[i][1]==tiles[i][2]&&tiles[i][1]==tiles[j][1]
//									&&tiles[j][1]==tiles[j][2]&&tiles[i][0]==tiles[j][3]
//											&&tiles[j][0]==tiles[i][3])
//								sym=true;
//						}
//					}
					//if(m==2) {
						ol(sym?"YES":"NO");
					//}else
					//ol(sym&&half?"YES":"NO");
				}
				
			}
		}
		
		static void C() throws IOException{
			 int t=ni();
			 while(t-->0) {
				 int n=ni();
				 int x=(int)Math.ceil(Math.sqrt(n));
				 int steps=n;
				 if(n==1) {ol(0);continue;}
				 for(int i=2;i<=x+10;i++) {
					 steps=Math.min(steps, i-2+(int)Math.ceil(n/(double)i));
				 }
//				 PriorityQueue<Integer>pq=new PriorityQueue<Integer>((u,v)->v-u);
//				 long sum=1;
//				 pq.add(1);
//				 int steps=0;
//				 while(sum<n) {
//					 int cur=pq.poll();
//					 sum++;
//					 steps++;
//					// pq.add(cur+1);
//					 if(sum>=n)break;
//					 sum++;
//					 steps++;
//					 pq.add(cur+2);
//					 if(sum>=n)break;
//					 sum+=(cur+2);
//					 pq.add(cur+2);
//					 steps++;
//				 }
				 ol(steps);
//		
			 }
		}
		static boolean isPrime(long n) {
			if(n==2)return true;
			if(n<2||n%2==0)return false;
			
			for(long i=3L;i*i<n;i+=2l) {
				long rem=(n%i);
				if(rem==0)return false;
			}
			return true;
		}
		static void D() throws IOException {
			int t=1;
			while(t-->0) {
				int n=ni();
				long l[]=nal(n);
				int ans=0;
				HashSet<Long>hs=new HashSet<Long>();
				hs.add((long) 0);
				long sum=0;
				for(int i=0;i<n;i++) {
					sum+=l[i];
					if(hs.contains(sum)) {
						ans++;
						hs.clear();
						hs.add((long) 0);
						sum=l[i];
					}
					hs.add(sum);
				}
				//if(ans==0&&tr.getOrDefault(pre[0], 0)==1)ans++;
				ol(ans);
			}
		}
		static int gcd (int a, int b) {
		    return b==0?a:gcd (b, a % b);
		}
		
	static void E() throws IOException {
		int t=1;
		while(t-->0) {
			int n=ni();
			int []a=nai(3);
			int b[]=nai(3);
			int mx=0;
			for(int i=0;i<3;i++) {
				mx+=Math.min(a[i], b[(i+1)%3]);
			}
			int mn=0;
			for(int i=0;i<3;i++) {
				mn+=Math.max(0,b[i]-(a[i]+a[(i+1)%3]) );
			}
			ol(mn+" "+mx);
		}
		
	}

	static void F() throws IOException {
		int t=1;
		long oo=(long)1e9+7;
		while(t-->0) {
			int n=ni();
			String s=ns();
			int[][]pre=new int[n][4];
			for(int i=0;i<s.length();i++) {
				pre[i][0]=i==0?0:pre[i-1][0];
				pre[i][1]=i==0?0:pre[i-1][1];
				pre[i][2]=i==0?0:pre[i-1][2];
				pre[i][3]=i==0?0:pre[i-1][3];
				if(s.charAt(i)=='a')pre[i][0]++;
				else if(s.charAt(i)=='b')pre[i][1]++;
				else if(s.charAt(i)=='c')pre[i][2]++;
				else pre[i][3]++;
			}
			long ans=0;
			threes=new long[n+1];
			threes[0]=1;
			for(int i=1;i<=n;i++) {
				threes[i]=(threes[i-1]*3l)%oo;
			}
			for(int i=1;i<n-1;i++) {
				long pra=pre[i-1][0];
				long suc=(pre[n-1][2]-pre[i][2]);
				if(s.charAt(i)=='b'||s.charAt(i)=='?') {
					long l=c(pra,pre[i-1][3]);
					long r=c(suc,pre[n-1][3]-pre[i][3]);
					ans=(ans+((l*r)%oo))%oo;
				}
			}
			ol(""+ans);
		}
	}
	private static long c(long pra, int i) {
		long res=(pra*threes[i])%oo;
		if(i>0) {
			res=(res+((i*threes[i-1])%oo))%oo;
		}
		return res;
	}
	static void G() throws IOException {
		int t=ni();
		while(t-->0) {
			
		}
	}
	static int ni() throws IOException {
		return sc.nextInt();
	}
	static double nd() throws IOException {
		return sc.nextDouble();
	}
	static long nl() throws IOException {
		return  sc.nextLong();
	}
	static String ns() throws IOException {
		return sc.next();
	}
	static int[] nai(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		return a;
	}
	static long[] nal(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextLong();
		return a;
	}
	static int[][] nmi(int n,int m) throws IOException{
		int[][]a=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextInt();
			}
		}
		return a;
	}

	static long[][] nml(int n,int m) throws IOException{
		long[][]a=new long[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextLong();
			}
		}
		return a;
	}
	static void o(String x) {
		out.print(x);
	}
	static void ol(String x) {
		out.println(x);
	}
	static void ol(int x) {
		out.println(x);
	}
	static void disp1(int []a) {
		for(int i=0;i<a.length;i++) {
			out.print(a[i]+" ");
		}
		out.println();
	}

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public boolean hasNext() {return st.hasMoreTokens();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
			
		public boolean ready() throws IOException {return br.ready(); }
		

	}
}
