Problem: Sereja painted n points on the plane, point number i (1 ≤ i ≤ n) has coordinates (i, 0). Then Sereja marked each point with a small or large English letter. Sereja don't like letter "x", so he didn't use it to mark points. Sereja thinks that the points are marked beautifully if the following conditions holds:

  * all points can be divided into pairs so that each point will belong to exactly one pair; 
  * in each pair the point with the lesser abscissa will be marked with a small English letter and the point with the larger abscissa will be marked with the same large English letter; 
  * if we built a square on each pair, the pair's points will be the square's opposite points and the segment between them will be the square's diagonal, then among the resulting squares there won't be any intersecting or touching ones. 



Little Petya erased some small and all large letters marking the points. Now Sereja wonders how many ways are there to return the removed letters so that the points were marked beautifully.

Input

The first line contains integer n the number of points (1 ≤ n ≤ 105). The second line contains a sequence consisting of n small English letters and question marks — the sequence of letters, that mark points, in order of increasing x-coordinate of points. Question marks denote the points without letters (Petya erased them). It is guaranteed that the input string doesn't contain letter "x".

Output

In a single line print the answer to the problem modulo 4294967296. If there is no way to return the removed letters, print number 0.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

4
a???


Output

50


Input

4
abc?


Output

0


Input

6
abc???


Output

1

Solution (in JAVA):

Solution:
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Niyaz Nigmatullin
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		FastPrinter out = new FastPrinter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    public void solve(int testNumber, FastScanner in, FastPrinter out) {
        in.next();
        char[] s = in.next().toCharArray();
        int n = s.length;
        if ((n & 1) == 1) {
            out.println(0);
            return;
        }
        int[] dp = new int[n / 2 + 1];
        int[] next = new int[n / 2 + 1];
        dp[0] = 1;
        int count = 0;
        for (int i1 = 0; i1 < n; i1++) {
            char e = s[i1];
            if (e == '?') {
                ++count;
                int left = i1 - n / 2;
                int right = i1 / 2;
                if (left < 0) left = 0;
                if ((i1 & 1) == 1) {
                    dp[(i1 + 1) / 2] += dp[(i1 + 1) / 2 - 1];
                }
                for (int i = right; i > left; i--) {
                    dp[i] += dp[i - 1];
                }
                if (i1 - n / 2 >= 0) {
                    dp[i1 - n / 2] = 0;
                }
            }
        }
        int ans = dp[n / 2];
        for (int i = 0; i < count - n / 2; i++) {
            ans *= 25;
        }
        out.println(Long.parseLong(Integer.toBinaryString(ans), 2));
    }
}

class FastScanner extends BufferedReader {

    public FastScanner(InputStream is) {
        super(new InputStreamReader(is));
    }

    public int read() {
        try {
            int ret = super.read();
//            if (isEOF && ret < 0) {
//                throw new InputMismatchException();
//            }
//            isEOF = ret == -1;
            return ret;
        } catch (IOException e) {
            throw new InputMismatchException();
        }
    }

    public String next() {
        StringBuilder sb = new StringBuilder();
        int c = read();
        while (isWhiteSpace(c)) {
            c = read();
        }
        if (c < 0) {
            return null;
        }
        while (c >= 0 && !isWhiteSpace(c)) {
            sb.appendCodePoint(c);
            c = read();
        }
        return sb.toString();
    }

    static boolean isWhiteSpace(int c) {
        return c >= 0 && c <= 32;
    }

    public String readLine() {
        try {
            return super.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    }

class FastPrinter extends PrintWriter {

    public FastPrinter(OutputStream out) {
        super(out);
    }

    public FastPrinter(Writer out) {
        super(out);
    }


}