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 void main(Scanner sc) {
        int n = sc.nextInt();
        String s = sc.next();
        char s1[] = s.substring(0, n).toCharArray();
        char s2[] = new StringBuilder(s.substring(n, 2 * n)).reverse().toString().toCharArray();

        Map<String, Long> map1 = new HashMap<>();
        Map<String, Long> map2 = new HashMap<>();
        for (int i = 0; i < (1 << n); i++) {
            StringBuilder red1 = new StringBuilder();
            StringBuilder blue1 = new StringBuilder();
            StringBuilder red2 = new StringBuilder();
            StringBuilder blue2 = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if ((i >> j) % 2 == 1) {
                    red1.append(s1[j]);
                    blue2.append(s2[j]);
                } else {
                    blue1.append(s1[j]);
                    red2.append(s2[j]);
                }
            }

            String key1 = red1.toString() + ":" + blue1.toString();
            map1.compute(key1, (k, v) -> v == null ? 1 : v + 1);
            String key2 = red2.toString() + ":" + blue2.toString();
            map2.compute(key2, (k, v) -> v == null ? 1 : v + 1);
        }

        long sum = 0;
        for (Map.Entry<String, Long> entry : map1.entrySet()) {
            String key = entry.getKey();
            sum += entry.getValue() * map2.getOrDefault(key, 0L);
        }
        System.out.println(sum);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        new Main().main(sc);
        sc.close();
    }
}