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();
        
        HashMap<String, Long> h = new HashMap<>();
        
        for(int i=0; i< 1<<n; i++){
            String red = "";
            String blue = "";
            for(int j=0; j<n; j++){
                if((i&(1<<j)) > 0){
                    red += s.charAt(j);
                }else{
                    blue += s.charAt(j);
                }
            }
            String key = red+":"+blue;
            long tmp = h.getOrDefault(key, 0L);
            h.put(key, tmp+1);
        }
        
        long ans = 0;
        for(int i=0; i< 1<<n; i++){
            String red = "";
            String blue = "";
            for(int j=0; j<n; j++){
                if((i&(1<<j)) > 0){
                    red += s.charAt(2*n-1-j);
                }else{
                    blue += s.charAt(2*n-1-j);
                }
            }
            String key = red+":"+blue;
            long tmp = h.getOrDefault(key, 0L);
            ans += tmp;
        }
        
        System.out.println(ans);
    }
}