题目描述

约翰在屋顶上唱歌，以此来与奶牛们交流．但是奶牛们的听力很奇怪，她们只能听到约翰的歌声变成$\red{0}$和$\red{1}$构成的信息串时的样子．

约翰的声音里有$\red{N(1≤}$$\red{N≤}$$\red{2000)}$个$\red{0}$或$\red{1，}$奶牛听到的也是$\red{N}$个，而且$\red{0}$和$\red{1}$的数量不会变化，但是一部分$\red{0}$或$\red{1}$可能偏离原来的位置，这就是约翰的歌声在传输时发生的"传输延迟"现象．$\red{0}$或$\red{1}$的偏离距离不会超过$\red{D(O≤}$$\red{D<N)，}$也就是说 某一个码的原本位置和现在的位置之差的绝对值不大于$\red{D.}$

比如，对于$\red{0110，}$$\red{D=1，}$传输延迟发生后可能出现$\red{0101，}$$\red{0110，}$$\red{1001，}$$\red{1010}$这四种串．

给出约翰歌声的$\red{01}$串形式和一个整数$\red{K(1≤}$$\red{K≤}$$\red{108)，}$请计算传输延迟发生后一共有多少种可能的$\red{01}$串，以及其中第$\red{K}$大的串是什么．

输入格式

第一行输入 $\red{n , d , k }$第二行输入那个$\red{N}$位的数字,用二进制表示

输出格式

分别输出受到整数的种数$\red{(}$将结果$\red{Mod 100,000,000)，}$和这些整数第$\red{K}$小的那个

样例

输入样例

4 1 3
0110

输出样例

4
1001

提示

$\red{1<=n<=2000 0<=k}$