Score : 600 points
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?
Input is given from Standard Input in the following format:
N S
Print the number of ways to paint the string that satisfy the condition.
4 cabaacba
4
There are four ways to paint the string, as follows:
11 mippiisssisssiipsspiim
504
4 abcdefgh
0
18 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
9075135300
The answer may not be representable as a 32-bit integer.