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.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String s = br.readLine();
		br.close();

		String s1 = s.substring(0, n);
		String s2 = new StringBuilder(s.substring(n)).reverse().toString();
		Map<String, Integer> map1 = new HashMap<>();
		Map<String, Integer> map2 = new HashMap<>();

		int end = 1 << n;
		for (int i = 0; i < end; i++) {
			StringBuilder r1 = new StringBuilder();
			StringBuilder b1 = new StringBuilder();
			StringBuilder r2 = new StringBuilder();
			StringBuilder b2 = new StringBuilder();
			for (int j = 0; j < n; j++) {
				if ((i >> j & 1) == 1) {
					r1.append(s1.charAt(j));
					r2.append(s2.charAt(j));
				} else {
					b1.append(s1.charAt(j));
					b2.append(s2.charAt(j));
				}
			}
			addCntMap(map1, r1.append('-').append(b1).toString());
			addCntMap(map2, r2.append('-').append(b2).toString());
		}

		long ans = 0;
		for (String key : map1.keySet()) {
			if (map2.containsKey(key)) {
				ans += (long) map1.get(key) * map2.get(key);
			}
		}
		System.out.println(ans);
	}

	static void addCntMap(Map<String, Integer> map, String key) {
		if (map.containsKey(key)) {
			map.put(key, map.get(key) + 1);
		} else {
			map.put(key, 1);
		}
	}
}