[Wc2004]孪生项链

佳佳有许多黑色和白色的小珠子，他喜欢用它们串成漂亮的项链。每条项链都是由不超过 $n$ 个珠子串成的环，项链上的珠子数称为项链的长度。每条项链至少包含一个珠子。

每完成一条项链，佳佳都会在其中一个珠子上贴上标签。从贴有标签的珠子开始，顺时针记录每个珠子的颜色，其中白色用 $0$ 表示，黑色用 $1$ 表示，并将得到的二进制串写在标签上。

同一条项链可以用多个不同的标签串表示。例如，对于图（a）中的项链，当标签分别贴在珠子 $1$、$2$、$3$、$4$ 上时，标签上分别写着 $0100$、$1000$、$0001$ 和 $0010$。佳佳总会选择其中字典序最小的串，因此图（a）中的标签应贴在珠子 $3$ 上，标签内容为 $0001$。

再考虑图（b）所示的项链，其字典序最小的标签串为 $0101$，但标签既可以贴在珠子 $1$ 上，也可以贴在珠子 $3$ 上。佳佳不希望出现这种情况，因此他在制作项链时会保证项链是合法的，即字典序最小的标签串对应的标签位置唯一。

这样，每条合法项链都能由标签上的二进制串唯一表示，并可按照标签串的字典序排序。例如，图（c）中的项链小于图（d）中的项链，因为 $00101$ 的字典序小于 $0011$。

你需要完成以下两个任务：

• **任务一：**新年将至，佳佳准备给一对双胞胎表妹各做一条项链。在完成妹妹的项链后，他决定制作一对“孪生项链”。将所有长度不超过 $n$ 的合法项链按照标签串的字典序排列后，两条孪生项链的位置应当相邻，并且姐姐的项链标签字典序大于妹妹的项链标签。给定妹妹的项链，请求出姐姐的项链。
• **任务二：**求所有合法项链中，长度恰好为 $k$ 的项链数量。

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$，相邻整数之间用一个空格分隔。其中，$n$ 表示项链长度的上限，$m$ 表示任务一中妹妹项链的长度，$k$ 表示任务二所求项链的长度，并满足 $1\le m,k\le n$。

第二行包含一个长度为 $m$ 的二进制串，表示妹妹项链上的标签。

输入数据保证合法。

输出格式

第一行输出一个正整数 $t$，表示长度恰好为 $k$ 的合法项链数量。

第二行输出一个二进制串，表示姐姐项链上的标签。

输入数据保证姐姐的项链一定存在。

样例输入

5 5 5
00101

样例输出

6
0011

样例解释

当项链长度不超过 $5$ 时，所有合法项链按照标签串的字典序排列如下：

$0$，$00001$，$0001$，$00011$，$001$，$00101$，$0011$，$00111$，$01$，$01011$，$011$，$0111$，$01111$，$1$。

其中，长度分别为 $1$、$2$、$3$、$4$、$5$ 的合法项链数量依次为 $2$、$1$、$2$、$3$、$6$。

妹妹项链的标签为 $00101$，其后相邻且字典序更大的标签为 $0011$，因此姐姐项链的标签为 $0011$。

数据范围

• $1\le m,k\le n$；
• $1\le n\le 2\times 10^5$；
• $1\le k\le 10^3$。

来源与许可

本题为 WC 2004 试题「孪生项链」，题面与测试数据整理自 BZOJ 1361。

样例 1

输入

5 5 5
00101

输出

6
0011