Submessage Sum Reconstruction

You are given a binary string of length \(N\) and a positive integer \(K\) (with \(K \le N\)). For a given binary string \(a_1a_2\cdots a_N\), its Submessage Sum (SMS) is defined as the sequence of \(N-K+1\) integers where the \(i\)th element is the sum of the \(K\) consecutive bits starting at position \(i\):

[ S_i = \sum_{j=i}^{i+K-1} a_j, \quad 1 \le i \le N-K+1. ]

For example, if \(K=4\) and the binary string is 110010, then the SMS is \(2,\; 2,\; 1\) because \(1+1+0+0=2,\; 1+0+0+1=2,\; 0+0+1+0=1\).

Your task is not to reconstruct the original binary string from the given SMS but rather to count how many different binary strings of length \(N\) may produce the given SMS.

Note: The first SMS element, \(S_1\), equals \(a_1+a_2+\cdots+a_K\). Thus, any valid binary string must have its first \(K\) bits summing to \(S_1\). In addition, for each index \(i\) with \(1 \le i \le N-K\), because the two adjacent windows \(S_i\) and \(S_{i+1}\) have a one‐element difference on each end, they satisfy the relation

[ S_{i+1} - S_i = a_{i+K} - a_i. ]

These relations induce dependencies between positions which split the indices into \(K\) independent chains (based on their residue modulo \(K\)). For each chain starting from one of the first \(K\) positions, the later entries are completely determined by the difference values \(S_{i+1}-S_i\). However, a candidate assignment for the starting bit of a chain (either 0 or 1) might lead to an invalid value (i.e. not 0 or 1) later in the chain. Let each chain contribute in a valid way only for those starting bits for which all its entries remain in \(\{0,1\}\).

The final answer is the number of ways to choose the \(K\) starting bits (one per chain) such that:

• For each chain, the chosen starting bit yields a valid sequence.
• The sum of the chosen starting bits is exactly \(S_1\) (the first SMS element).

Output the count of such binary strings.

inputFormat

The input consists of two lines:

1. The first line contains two integers \(N\) and \(K\) separated by a space.
2. The second line contains \(N-K+1\) integers \(S_1, S_2, \ldots, S_{N-K+1}\) separated by spaces, representing the SMS.

You may assume that \(1 \le K \le N \le 10^5\) and all \(S_i\) are integers.

outputFormat

Output a single integer – the number of binary strings of length \(N\) that yield the given SMS.

sample

6 4
2 2 1

3