Type Two de Bruijn Sequences

A word $s$ made up of $2^n + n - 1$ characters 0 and 1 is called a de Bruijn sequence of order $n$ if every $n$-character binary word appears as one of its subwords, that is a fragment of consecutive characters of $s$. For example, 0001011100 is a de Bruijn sequence of order 3.

A type two de Bruijn sequence of order $n$ is a word $s$ of arbitrary length such that every $n$-character binary word appears as a subsequence of $s$, that is a fragment of characters that are not necessarily consecutive. For example, 00101101 is a type two de Bruijn sequence of order 3. As far as we know, Nicolaas Govert de Bruijn did not invent such sequences, but their definition is clearly similar to the original one.

Consider a word $s$ made up only of zeroes and ones. How many digits (0 or 1) must be appended to the end of $s$ so that it becomes a type two de Bruijn sequence of order $n$?

The first line contains two integers $m$ and $n$ ($1 \le m, n \le 10^6$) separated by a single space. The second line contains the $m$-character word $s$, made up only of the digits 0 and 1, with no spaces.

Print a single non-negative integer: the minimal number of digits that must be appended to the end of $s$ so that it becomes a type two de Bruijn sequence of order $n$.

For $s =$ 00101 with $n = 3$, appending the two characters 01 gives 0010101, which is a type two de Bruijn sequence of order 3. Hence the answer is 2.