由 $(2^{n} + n - 1)$ 个字符 0 和 1 组成的字符串 $s$ 如果满足每一个长度为 $n$ 的由 0 和 1 组成的字符串都是 $s$ 的子串（即 $s$ 中连续的片段），则称其为 $n$ 阶 de Bruijn 序列。例如，0001011100 是一个 3 阶 de Bruijn 序列。

$n$ 阶二型 de Bruijn 序列是指一个任意长度的字符串 $s$，使得每一个长度为 $n$ 的由 0 和 1 组成的字符串都是 $s$ 的子序列（即 $s$ 中不一定连续的片段）。例如，00101101 是一个 3 阶二型 de Bruijn 序列。据我们所知，Nicolaas Govert de Bruijn 并没有发明这种序列，但它们的定义与前者类似，不是吗？

考虑一个仅由 0 和 1 组成的字符串 $s$。为了使该字符串成为 $n$ 阶二型 de Bruijn 序列，需要在 $s$ 的末尾添加多少个数字（当然是 0 或 1）？

输入格式

第一行包含两个整数 $m$ 和 $n$ ($1 \le m, n \le 1\,000\,000$)，由一个空格分隔。第二行包含一个长度为 $m$ 的字符串 $s$，仅由数字 0 和 1 组成，且不包含空格。

输出格式

第一行且仅有一行输出一个非负整数，表示为了使字符串 $s$ 成为 $n$ 阶二型 de Bruijn 序列，需要在其末尾添加的最少数字个数。

样例

输入 1

5 3
00101

输出 1

2

说明 1

在添加字符 01 后，我们得到了以下 3 阶二型 de Bruijn 序列：0010101。