[Usaco2009 Hol]Transmission Delay 传输谍延时

约翰站在屋顶上唱歌，与奶牛们交流。然而，奶牛们的听觉十分奇特：她们只能将约翰的歌声听成由 $0$ 和 $1$ 组成的信息串。

约翰发出的信息串长度为 $N$ ，奶牛听到的信息串长度同样为 $N$ ，其中 $0$ 和 $1$ 的数量均不会发生变化。但是，部分字符可能偏离原来的位置，这种现象称为“传输延时”。

每个字符偏离原位置的距离不超过 $D$ ，即该字符原位置与传输后位置之差的绝对值不大于 $D$ 。例如，对于字符串 $0110$ ，当 $D=1$ 时，经过传输延时后可能得到 $0101$ 、 $0110$ 、 $1001$ 和 $1010$ ，共 $4$ 个不同的字符串。

给定约翰发出的 $01$ 串以及整数 $K$ ，请计算经过传输延时后可能得到的不同 $01$ 串数量，并输出这些字符串按字典序从小到大排列后的第 $K$ 个。

输入格式

第一行输入三个整数 $N$ 、 $D$ 和 $K$ 。

第二行输入一个长度为 $N$ 、仅由字符 $0$ 和 $1$ 组成的字符串。

保证 $K$ 不超过经过传输延时后可得到的不同字符串数量。

第一行输出可得到的不同 $01$ 串数量对 $10^8$ 取模后的结果。

第二行输出所有可得到的字符串按字典序从小到大排列后的第 $K$ 个字符串。

4 1 3
0110

4
1001

本题为 USACO 2009 Holiday 试题「Transmission Delay」，题面与测试数据整理自 BZOJ。

4 1 3
0110

4
1001