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.*;
import java.util.stream.Stream;
import java.text.*;
import java.lang.*;
import java.math.*;


public class Solution{
	
	static ArrayList a[] = new ArrayList [1000001];
	    public void solve () throws IOException  {
       
    	InputReader in = new InputReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt();
        long dp[][] = new long [n + 1][3];
        long cnt = 1L;
        char s[] = in.nextLine().toCharArray();
        
        for(int i = 0 ; i < n ; i++) {
        	if(s[i] == '?') {
        		
        		dp[i + 1][0] = (dp[i][0] * 3L)%mod +cnt;
        		dp[i + 1][0] %= mod;
        		dp[i + 1][1] = dp[i][1] * 3L + dp[i][0] ;
        		dp[i + 1][1] %= mod;
        		dp[i + 1][2] = dp[i][2] * 3L + dp[i][1];
        		dp[i + 1][2] %= mod;
        		cnt = cnt * 3L;
        		cnt %= mod;
        	}
        	else if(s[i] == 'a') {
        		dp[i + 1][0] = dp[i][0] + cnt;
        		dp[i + 1][0] %= mod;
        		dp[i + 1][1] = dp[i][1];
        		dp[i + 1][2] = dp[i][2];
        	}
        	else if(s[i] == 'b') {
        		dp[i + 1][0] = dp[i][0];
        		dp[i + 1][1] = dp[i][1] + dp[i][0];
        		dp[i + 1][1] %= mod;
        		dp[i + 1][2] = dp[i][2];
        		
        	}
        	else {
        		dp[i + 1][0] = dp[i][0];
        		dp[i + 1][1] = dp[i][1];
        		dp[i + 1][2] = dp[i][2] + dp[i][1];
        		dp[i + 1][2] %= mod;
        	}
        }
        
        pw.println(dp[n][2]);
        pw.flush(); 
        pw.close();
    }
    public static void main(String[] args) throws Exception {
        
         
        new Thread(null,new Runnable() {
            public void run() {
                  try {
                    new Solution().solve();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }  
        },"1",1<<26).start();
        
        
    }
   
    static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
        }
        
        static class InputReader 
        {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream) 
        {
            this.stream = stream;
        }
        public int snext() 
        {
            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 = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public long nextLong()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public int[] nextIntArray(int n) 
        {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) 
            {
                a[i] = nextInt();
            }
            return a;
        }
 
        public String readString()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        public String nextLine() 
        {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
        }
 
        public boolean isSpaceChar(int c) 
        {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c) 
        {
            return c == '\n' || c == '\r' || c == -1;
        }
 
        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }
        public static long mod = 1000000007;
        public static int d;
        public static int p;
        public static int q;
        public void extended(int a,int b) {
            if(b==0) {
                d=a;
                p=1;
                q=0;
            }
            else
            {
                extended(b,a%b);
                int temp=p;
                p=q;
                q=temp-(a/b)*q;
            }
        }
       
        
        public static long binaryExponentiation(long x,long n)
        {
            long result=1;
            while(n>0)
            {
                if(n % 2 ==1)
                    result=result * x;
                x=x*x;
                n=n/2;
            }
            return result;
        }
        
        public static long[] shuffle(long[] a,Random gen)
        {
            int n = a.length;
            for(int i=0;i<n;i++)
            {
                int ind = gen.nextInt(n-i)+i;
                long temp = a[ind];
                a[ind] = a[i];
                a[i] = temp;
            }
            return a;
        }
        
        public static void swap(int a, int b){
            int temp = a;
            a = b;
            b = temp;
        }
        
        public static HashSet<Integer> primeFactorization(int n)
        {
            HashSet<Integer> a =new HashSet<Integer>();
            for(int i=2;i*i<=n;i++)
            {
                while(n%i==0)
                {
                    a.add(i);
                    n/=i;
                }
            }
            if(n!=1)
                a.add(n);
            return a;
        }
        
        public static void sieve(boolean[] isPrime,int n)
        {
            for(int i=1;i<n;i++)
                isPrime[i] = true;
            
            isPrime[0] = false;
            isPrime[1] = false;
            
            for(int i=2;i*i<n;i++)
            {
                if(isPrime[i] == true)
                {
                    for(int j=(2*i);j<n;j+=i)
                        isPrime[j] = false;
                }
            }
        }
        
        public static long GCD(long n,long m)
        {
            if(m==0)
                return n;
            else
                return GCD(m,n%m);
        }
        public static long LCM (long a,long b) {
            return ((a*b)/(GCD(a,b)));
        }
        
        static class pair implements Comparable<pair>
        {
            Long x , y ;
            
            pair(long  a, long b )
            {
                this.x=a;
                this.y=b;
            }

           
            public int compareTo(pair o) {
                int result = x.compareTo(o.x);
                if(result==0)
                    result = y.compareTo(o.y);
                
                return result;
            }  
            
            public String toString()
            {
                return x+" "+y;
            }
            
            public boolean equals(Object o)
            {
                if (o instanceof pair)
                {
                    pair p = (pair)o;
                    return p.x == x && p.y == y ;
                }
                return false;
            }
            public int hashCode()
            {
                return x.hashCode()*3 +  y.hashCode();
                
            }
        }
        public static int binaryExponentiation(int x,int n)
        {
            int result=1;
            while(n>0)
            {
                if(n % 2 ==1)
                    result=result * x;
                x=x*x;
                n=n/2;
            }
            return result;
        }
        
       
        
        public static int modularExponentiation(int x,int n,int M)
        {
            int result=1;
            while(n>0)
            {
                if(n % 2 ==1)
                    result=(result * x)%M;
                x=(x%M*x)%M;
                n=n/2;
            }
            return result;
        }
        
        public static long modularExponentiation(long x,long n,long M)
        {
            long result=1;
            while(n>0)
            {
                if(n % 2 ==1)
                    result=(result%M * x%M)%M;
                x=(x%M * x%M)%M;
                n=n/2;
            }
            return result;
        }
        
        public static long modInverse(int A,int M)
        {
            return modularExponentiation(A,M-2,M);
        }
        
        public static long modInverse(long A,long M)
        {
            return modularExponentiation(A,M-2,M);
        }
        
       
        
                    
         
}
class trie {
	int cnt;
	trie a[] = new trie [2];
	
}

class Segment{ 
	trie seg[]; 
	int a[];
	int n;
    Segment (int n,int  b[]){
		seg=new trie [4*n];
		a=new int [b.length];
		a=b.clone();
	}
    public void build(int node,int start,int end) {
    	if(start==end) {
    		//createTrie(node , start , end);
    		return ;
    	}
    	int mid=(start+end)/2;
    	build(2*node+1,start,mid);
    	build(2*node+2,mid+1,end);
    	createTrie(node , start , end);
    }
    public void createTrie(int node , int l , int r) {
    	seg[node] = new trie();
    	for(int i = l ; i <= r ; i++) {
    		//seg[node].cnt++;
    		insert(node , a[i]);
    	}
    }
    
    public void insert(int node , int val) {
    	trie root = seg[node];
    	for(int j = 20 ; j >= 0 ; j--) {
    		byte x = (byte) ((val >> j) & 1);
    		if(root.a[x] == null)
    			root.a[x] = new trie();
    		root = root.a[x];
    		root.cnt ++;
   		}
    	
    }
    public int query(int node,int start,int end,int l,int r) {
    	if(l>end || r<start)
    		return 0;
    	if(start>=l && end<=r)
    		return 0;
    	
    	int  mid=(start+end)/2;
    	return (query(2*node+1,start,mid,l,r)+query(2*node+2,mid+1,end,l,r));
    }
        
}

