题目描述

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

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

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

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

输入格式

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

输出格式

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

样例

输入样例

4 1 3
0110

输出样例

4
1001

提示

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