我们称一个排列 为内卷的当且仅当对于每个 有 。
你需要求出所有长度为 的内卷的排列中，逆序对个数 的排列个数 。
为了文明起见，我们输入一个正整数 ，你需要对于每个 都输出答案。
一行两个整数 。
一行一个长度为 的 01 串，表示每个 的输出答案。
3 9
100100000
120 399
111001011110110000001011001000100011000010010000100100000101000001000010000001100000010000001000000000000000100000000100010110100100001111101010101010101001110110101111000111111101111100000001101011111111101000100011110101011111101000001011110111110001100000011101000111011010001100111111101010000001110111010100001111000011011111000110110100010101101110111011100000100000111001101010101001110001100
对于的数据：。
对于所有数据，。