题目描述

约翰在屋顶上唱歌，以此来与奶牛们交流。但是奶牛们的听力很奇怪，她们只能听到约翰的歌声变成 $0$ 和 $1$ 构成的信息串时的样子。 约翰的声音里有 $n$ 个 $0$ 或 $1$，奶牛听到的也是 $n$ 个，而且 $0$ 和 $1$ 的数量不会变化，但是一部分 $0$ 或 $1$ 可能偏离原来的位置，这就是约翰的歌声在传输时发生的"传输延迟"现象。$0$ 或 $1$ 的偏离距离不会超过 $d$，也就是说某一个码的原本位置和现在的位置之差的绝对值不大于 $d$。

比如，对于 $0110$，$d=1$，传输延迟发生后可能出现 $0101$，$0110$，$1001$，$1010$ 这四种串。

给出约翰歌声的 $01$ 串形式和一个整数$k$，请计算传输延迟发生后一共有多少种可能的 $01$ 串，以及其中第 $k$ 大的串是什么。

输入格式

• 第 $1$ 行：$3$ 个整数：$n,d,k$。
• 第 $2$ 行：$1$ 个 $n$ 位的二进制数字，代表信息串。

输出格式

• 第 $1$ 行：$1$ 个整数：收到整数的种数（对 $10^8$ 取模）
• 第 $2$ 行：$1$ 个整数：$1$ 个 $n$ 位的二进制数字，代表第 $k$ 大的串。

4 1 3
0110

4
1001

数据规模与约定

对于 $100\%$ 的数据，$1\le n \le 2000$，$0 \le d < n$，$1 \le k \le 10^8$。

题目来源

Usaco2009 Hol Gold