Counting Thue–Morse Extensions

The Thue–Morse sequence \(\{T_n\}\) is defined as follows:

• \(T_0=0\);
• \(T_{2n}=T_n\);
• \(T_{2n+1}=1-T_n\).

Thus, the beginning of the sequence is: \(0\,1\,1\,0\,1\,0\,0\,1\,1\,0\,0\,1\,0\,1\,1\,0\,\cdots\).

A string (a binary sequence) is said to be a factor (continuous subsequence) of the Thue–Morse sequence if it appears as a contiguous block in the infinite sequence. For example, 0, 1, 10100, 10011 and 011001 are factors, while 111 and 1000 are not.

Given a binary string \(S\) and a nonnegative integer \(k\), count the number of distinct factors \(T\) of the Thue–Morse sequence satisfying the following conditions:

• \(S\) is a prefix of \(T\);
• \(T\) is obtained by appending exactly \(k\) extra bits to \(S\) (i.e. \(|T|=|S|+k\)).

If \(S\) does not appear in the Thue–Morse sequence, the answer is 0.

inputFormat

The input consists of two lines:

1. The first line contains the binary string \(S\) (a nonempty string composed only of '0' and '1').
2. The second line contains a nonnegative integer \(k\) (\(0 \le k\)).

outputFormat

Output a single integer representing the number of distinct factors \(T\) of the Thue–Morse sequence that begin with \(S\) and have total length \(|S|+k\).

sample

0
1

1