Counting Initial Pebble Strings

We are given a circular arrangement of n pebbles (stones), each of which is either black or white. Denote black by B and white by W.

Mirko performs an operation on the pebble circle k times (each operation is applied on the original pebbles only). In one operation, for every pair of adjacent (cyclic) pebbles in the initial stone string the following is done:

• If the two adjacent pebbles have the same color, a black pebble (B) is inserted between them.
• If they have different colors, a white pebble (W) is inserted.

After the operation, the number of pebbles is doubled from n to 2n. Then the initial string of pebbles is removed and the newly inserted string (of length n) is considered the result of that operation.

This operation is applied exactly k times, so starting from an initial stone string s, we get a final resulting string:
\( f^{k}(s) \) where the transformation \( f \) is defined over \( \mathbb{F}_2 \) by the rule

[ f(s)i = s_i \oplus s{(i+1),\bmod,n}, \quad \text{for } i=0,1,\ldots,n-1, ]

(Here we identify B with 0 and W with 1.)

Your task is: Given an integer k and the final resulting stone string after k operations, determine the number of different initial stone strings which, when processed by k operations, produce exactly the same final string.

Note: The transformation can be written in closed form as

[ f^{k}(s)i = \sum{j \in S} s_{(i+j),\bmod,n} \quad \text{(mod 2)}, \quad \text{where } S = {j \ : \ 0 \le j \le k \text{ and } {k \choose j}\equiv1 ; (\bmod,2)}. ]

You have to count the number of solutions \( s \in \{B,W\}^{n} \) (interpreting B as 0 and W as 1) to the linear system over \( \mathbb{F}_2 \)

[ A s = t, ]

where the matrix \( A \) is a circulant matrix defined by the rule \( A_{i, (i+j)\,\bmod\,n} = 1 \) if \( j \in S \) and \( 0 \) otherwise, and \( t \) is the given final string (with B = 0 and W = 1). The number of solutions is \(2^{n-\text{rank}(A)}\) if the system is consistent, and 0 otherwise.

inputFormat

The first line contains a single integer k (the number of operations).

The second line contains a string of length n consisting only of characters B and W — representing the final resulting stone string after k operations.

Note: n is determined by the length of the given string.

outputFormat

Output a single integer — the number of different initial stone strings which, after applying k operations, produce the given final string.

sample

1
BWB

0