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.*;

class Pair<E1 extends Comparable<E1>, E2 extends Comparable<E2>>
        implements Comparable<Pair<E1, E2>> {
    private E1 first;
    private E2 second;

    public Pair(E1 first, E2 second) {
        this.first = first;
        this.second = second;
    }

    public E1 getFirst() {
        return first;
    }

    public E2 getSecond() {
        return second;
    }

    public void setFirst(E1 first) {
        this.first = first;
    }

    public void setSecond(E2 second) {
        this.second = second;
    }

    @Override
    public String toString() {
        return getClass().getName() + "[first=" + first + ",second=" + second + "]";
    }

    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        if (other == null) {
            return false;
        }
        if (getClass() != other.getClass()) {
            return false;
        }
        Pair<?, ?> p = (Pair<?, ?>) other;
        return Objects.equals(first, p.first) && Objects.equals(second, p.second);
    }

    @Override
    public int hashCode() {
        return Objects.hash(first, second);
    }

    @Override
    public int compareTo(Pair<E1, E2> other) {
        return Comparator.comparing(Pair<E1, E2>::getFirst).thenComparing(Pair<E1, E2>::getSecond)
                .compare(this, other);
    }
}


public class Main {
    public static void main(String[] args) {
        // read inputs
        Scanner in = new Scanner(System.in);
        final int N = in.nextInt();
        final String cs = in.next();

        // try all possible ways of coloring the right half
        // if the reverse of the red string on the right hand side is cRRs
        // and the reverse of the blue string on the left hand side is cRBs
        // count the number of times the pair (cRRs, cRBs) occurs
        String cRs = cs.substring(N, 2 * N);
        Map<Pair<String, String>, Long> rbStringToNumber = new HashMap<>();
        for (int S = 0; S < 1 << N; S++) {
            StringBuilder builder0 = new StringBuilder(), builder1 = new StringBuilder();
            for (int i = 0; i < N; i++) {
                if ((S & (1 << i)) == 0) {
                    builder0.append(cRs.charAt(i));
                } else {
                    builder1.append(cRs.charAt(i));
                }
            }
            Pair<String, String> rbString =
                    new Pair(builder0.reverse().toString(), builder1.reverse().toString());
            rbStringToNumber.computeIfAbsent(rbString, string -> 0L);
            rbStringToNumber.computeIfPresent(rbString, (string, num) -> num + 1);
        }
        // System.out.printf("rbStringToNumber:\n%s\n", rbStringToNumber);

        // try all possible ways of coloring the right half
        String cLs = cs.substring(0, N);
        long ans = 0;
        for (int S = 0; S < 1 << N; S++) {
            StringBuilder builder0 = new StringBuilder(), builder1 = new StringBuilder();
            for (int i = 0; i < N; i++) {
                if ((S & (1 << i)) == 0) {
                    builder0.append(cLs.charAt(i));
                } else {
                    builder1.append(cLs.charAt(i));
                }
            }
            Pair<String, String> rbString =
                    new Pair(builder0.toString(), builder1.toString());
            ans += rbStringToNumber.getOrDefault(rbString, 0L);
        }
        System.out.printf("%d\n", ans);
    }
}