Problem: You are given a string S of length 2N consisting of lowercase English letters.

There are 2^{2N} ways to color each character in S red or blue. Among these ways, how many satisfy the following condition?

* The string obtained by reading the characters painted red from left to right is equal to the string obtained by reading the characters painted blue from right to left.

Constraints

* 1 \leq N \leq 18
* The length of S is 2N.
* S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:


N
S


Output

Print the number of ways to paint the string that satisfy the condition.

Examples

Input

4
cabaacba


Output

4


Input

11
mippiisssisssiipsspiim


Output

504


Input

4
abcdefgh


Output

0


Input

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa


Output

9075135300

Solution (in JAVA):

Solution:
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String s = in.next();
		char[] l = new char[n];
		char[] r = new char[n];
		for(int i=0;i<n;i++) {
			l[i] = s.charAt(i);
			r[i] = s.charAt(2*n-1-i);
		}
		char[][] buf = new char[2][n];
		long count = 0;
		for(int i=0;i<(1<<n);i++) {
			int[] p = new int[2];
			for(int j=0;j<n;j++) {
				int k = (i>>j)&1;
				buf[k][p[k]++] = l[j];
			}
			long[][] dp = new long[p[0] + 1][p[1] + 1];
		    dp[0][0] = 1;
		    for (int x = 0; x <= p[0]; x ++) {
		      for (int y = 0; y <= p[1]; y ++) {
		        if (x < p[0] && r[x + y] == buf[0][x]) {
		          dp[x + 1][y] += dp[x][y];
		        }
		        if (y < p[1] && r[x + y] == buf[1][y]) {
		          dp[x][y + 1] += dp[x][y];
		        }
		      }
		    }
		    count += dp[p[0]][p[1]];
		}
		System.out.println(count);
		in.close();
	}

}