给定一个长度为nnn的01串sss，你可以对其进行最多kkk次操作，每次操作形如，选择两个下标1≤i<j≤n1\leq i<j\leq n1≤i<j≤n（下标从111开始）且si=0,sj=1s_i=0,s_j=1si=0,sj=1，然后将sjs_jsj从原位置移除，并插入到sis_isi的前一个位置（即插入到si−1,sis_{i-1},s_isi−1,si）之间。请问最多使用kkk次操作，一共能得到多少种不同的01串？答案摸998244353998244353998244353输出
一行一个01串SSS,和一个非负整数kkk，用空格隔开
一行一个非负整数表示答案
0101 1
4
01100110 2
14
1100110101010101111101000111110011111011000111101110101010010101010101 20
139520955
1≤∣S∣≤3001\leq |S|\leq 3001≤∣S∣≤300
0≤k≤1090\leq k\leq 10^90≤k≤109