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.math.BigInteger;
import java.util.*;

public class Main {
	String s;
	int n;
	boolean []used;
	ArrayList<String[]> list, list2;
	HashMap<String, Integer> set;
	
	private void dfs(int deep){
		if(deep == n){
			StringBuilder sb1 = new StringBuilder();
			StringBuilder sb2 = new StringBuilder();
			for(int i = 0; i < n; i++){
				if(used[i]){
					sb1.append(s.charAt(i));
				}
				else{
					sb2.append(s.charAt(i));
				}
			}
			list.add(new String[]{sb1.toString(), sb2.reverse().toString()});
			return;
		}
		used[deep] = true;
		dfs(deep+1);
		used[deep] = false;
		dfs(deep+1);
	}
	private void dfs2(int deep){
		if(deep == n){
			StringBuilder sb1 = new StringBuilder();
			StringBuilder sb2 = new StringBuilder();
			for(int i = 0; i < n; i++){
				if(used[i]){
					sb1.append(s.charAt(2 * n - 1 - i));
				}
				else{
					sb2.append(s.charAt(2 * n - 1 - i));
				}
			}
			
			String s1 = sb1.reverse().toString();
			String s2 = sb2.toString();
			String s = s1 + " " + s2;
			if(set.containsKey(s)){
				set.put(s, set.get(s) + 1);
			}
			else{
				set.put(s, 1);
			}
			return;
		}
		used[deep] = true;
		dfs2(deep+1);
		used[deep] = false;
		dfs2(deep+1);
	}
	
	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			n = sc.nextInt();
			s = sc.next();
			used = new boolean[n];
			list = new ArrayList<>();
			dfs(0);
			used = new boolean[n];
			set = new HashMap<>();
			dfs2(0);
			long count = 0;
			for(int i = 0; i < list.size(); i++){
				String s = list.get(i)[1] + " " + list.get(i)[0];
				if(set.containsKey(s)){
					count += set.get(s);
				}
			}
			System.out.println(count);
		}
	}

	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

	public static void main(String[] args) {
		new Main().doit();
	}

}