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.HashMap;
import java.util.Objects;
import java.util.Scanner;

class C {

    static class Pair {
        final int bits;
        final String s;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return bits == pair.bits &&
                    Objects.equals(s, pair.s);
        }

        @Override
        public int hashCode() {

            return Objects.hash(bits, s);
        }

        public Pair(int bits, String s) {

            this.bits = bits;
            this.s = s;
        }
    }

    public static void main(String... args) {
        final Scanner sc = new Scanner(System.in);
        final int N = sc.nextInt();
        final char[] S = sc.next().toCharArray();
        final HashMap<Pair, Integer> map = new HashMap<>();
        for (int i = 0; i < 1 << N; i++) {
            final StringBuilder sb = new StringBuilder();
            for (int j = 0; j < N; j++)
                if ((i & 1 << j) > 0)
                    sb.append(S[j]);
            for (int j = N - 1; j >= 0; j--)
                if ((i & 1 << j) == 0)
                    sb.append(S[j]);
            final Pair p = new Pair(Integer.bitCount(i), sb.toString());
            map.put(p, map.getOrDefault(p, 0) + 1);
        }
        long ans = 0;
        for (int i = 0; i < 1 << N; i++) {
            final StringBuilder sb = new StringBuilder();
            for (int j = N - 1; j >= 0; j--)
                if ((i & 1 << j) == 0)
                    sb.append(S[j + N]);
            for (int j = 0; j < N; j++)
                if ((i & 1 << j) > 0)
                    sb.append(S[j + N]);
            final Pair p = new Pair(N - Integer.bitCount(i), sb.toString());
            ans += map.getOrDefault(p, 0);
        }
        System.out.println(ans);
    }
}
public class Main {
    public static void main(String...args) {
        C.main();
    }
}