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.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        int num = 1 << n;
        HashMap hm = new HashMap<String, Integer>();
        for(int i=0; i<num; i++){
            String bin = String.format("%"+n+"s",Integer.toBinaryString(i)).replace(' ', '0');
            char[] left = new char[n];
            int lc = 0, rc = n-1;
            for(int j=0; j<n; j++){
                if(bin.charAt(j) == '0'){
                    left[lc] = s.charAt(j);
                    lc++;
                }else{
                    left[rc] = s.charAt(j);
                    rc--;
                }
            }
            String sleft = new String(left) + lc;
            if(hm.get(sleft) != null){
                hm.put(sleft, (int)hm.get(sleft) + 1);
            }else{
                hm.put(sleft, 1);
            }
        }

        long ans = 0;

        for(int i=0; i<num; i++){
            String bin = String.format("%"+n+"s",Integer.toBinaryString(i)).replace(' ', '0');
            char[] right = new char[n];
            int lc = 0, rc = n-1;
            for(int j=0; j<n; j++){
                if(bin.charAt(j) == '0'){
                    right[lc] = s.charAt(2*n-j-1);
                    lc++;
                }else{
                    right[rc] = s.charAt(2*n-j-1);
                    rc--;
                }
            }
            String sright = new String(right) + lc;
            if(hm.get(sright) != null){
                ans += (int)hm.get(sright);
            }
        }

        System.out.println(ans);
    }
}