T539076 小伞与模拟退火

从人间之里访问回来的多多良小伞全然不顾身体的疲惫，连夜找我们几个小妖怪商量铁匠铺的安排。谈得晚了，便送我们出门，要小町送我们回家。在去大门口的路上，我们说：“ 小伞前辈，您回去休息吧。您刚从人里回来。” 小伞摇摇头，“不碍事，你们知道现在幻想乡有很多人把博丽大结界当作敌人，不断给我们制造麻烦，你们是乡里的未来，你们的事情便是乡里的事情，是头等大事。”我们都激动了，眼里噙着泪花。多好的小伞前辈呀。 小伞抬头看看天空说：“如果幻想乡真像这天空这么安静就好了，但是就有一些妖怪，像宫出口瑞灵，要搞乱这个幻想乡，她们是罪人。” 说着，小伞弯下腰，从兜里捡出一只封魔针，然后看着天空说：“该死的异变始作俑者。” 说着他把封魔针奋力向上一掷。很快就见空中一只灵突然爆发出耀眼的P点，然后就满身疮痍。“这是瑞灵的间谍灵，他们一直在博丽神社上空盘旋，侵犯我们的主权，我已经忍了很久了。”小伞愤愤地说。小妖怪们都鼓起掌来，为幻想乡有这样的铁匠感到自豪。 一会小伞叫来犬走椛问：“那些P点落到什么地方了？”“好像是妖怪之山一带。”椛说。 小伞一怔，说：“赶紧去查，看有什么问题没有。”之后前辈送我们到大门口， 一直挥手到看不见我们。 第四天我们听说妖怪之山那边出事了，我们很紧张。而这时小伞前辈叫我们过去。 她依然那么慈祥，让我们坐下说：“退治总是要有牺牲的。为博丽大结界牺牲的妖怪是伟大的。”他这时低下头说：“但我必须承认，我当时击落间谍灵的行为太鲁莽了， 我在这里向全乡妖怪道歉。我将向全乡说明情况。” 我们顿时热泪盈眶，多好的前辈呀，她在跟敌人斗争过程中的小失误竟然被他记在心里，还道了歉，我们在将来的学习中一定要向小伞前辈学，学她那宽广的胸怀，和不耻下问的精神。

小伞是幻想乡最强的铁匠。为了帮助灵梦解决异变，小伞正在制作一批封魔针。退火是锻造过程中重要的一步，每一只封魔针都有一个温度值，它们共同形成一个非负整数数列。 **一个温度为 $s$ 的封魔针的 $k$ 级退火参数定义为 $C^{s+1}_{k+1}$ 即 $k+1$ 选 $s+1$ 。** 小伞喜欢树形数据结构，所以小伞的封魔针退火参数信息是用一颗树维护的。但是小伞去人间之里访问时忘记了具体的信息，幸好她还记得一些特殊性质。你需要帮她生成出原来的温度数列。 形式化地，封魔针的退火温度存储是一个长度为 $n$ 的序列 $a$ 所生成的线段树，满足： - $a_n=0$ - 数列上 $[l,r]$ 区间所对应的线段树节点的左右子节点分别代表数列上的区间 $[l,\lfloor\frac{l+r}{2}\rfloor]$ 和 $[\lfloor\frac{l+r}{2}\rfloor+1,r]$ 。 - 线段树的生成方式是： - 定义一个区间的后继区间为区间中的每一个数加一后的新区间（$\{1,1,4,5,1,4\}$->$\{2,2,5,6,2,5\}$），一个区间对于一个 $i$ 的补区间为只去除第 $i$ 个数后的新区间（$i=1,\{9,1,9,8,1,0\}$->$\{1,9,8,1,0\}$）。 - 淬火位，任意时刻只对应 $[1,n]$ 上一个位置，初始为数列最右端即 $n$ ，含义见下。 - 对于从存储 $a_n$ 的节点到根节点的路径上经过的节点，如果左右儿子区间的长度 $a$ 与 $b$ 不相等（必有长度差为 $1$ ），则左儿子区间应为右儿子区间的后继区间在右侧并一个 $0$ 后形成的区间，**淬火位改变为赋值时对应了淬火位的位置**（原来在右儿子区间的第 $tmp$ 个数的位置，则新的淬火位在左儿子区间的第 $tmp$ 个数的位置）； 否则即 $a=b$ ，左儿子区间是右儿子区间对于淬火位的补区间的后继区间在右侧并一个 $0$ 的结果，**淬火位不变**。 - 其他区间按照正常线段树一样从上往下生成。 小伞有 $T$ 次询问，每次想知道，根据你所生成的温度序列，所有封魔针的 $k$ 级退火参数的和，答案对 $998244353$ 取模。

第一行一个正整数 $T$ 。 接下来 $T$ 行，每行： - 一个非负整数 $k$ 。 - 一个 $01$ 串，代表 $n$ 的二进制表示。

$T$ 行，每行一个非负整数，代表所有封魔针的 $k$ 级退火参数的和对 $998244353$ 取模的结果。

样例1解释： 对于第一组数据，$n$ 为 $19$ ,计算过程如图：  --- 注意: $C^m_n$（即 $n$ 选 $m$ ）在 $n\lt m$ 或 $m\lt 0$时定义为 $0$ 。 --- 对于 $10\%$ 的数据，满足 $1\le n\le 5\times 10^5$。 对于 $30\%$ 的数据，满足 $1\le n\le 2^{64}$。 对于另外 $30\%$ 的数据，满足 $n$是 $2$ 的正整数次幂。 对于 $100\%$ 的数据，$0\lt T\le10$，$0\le k \le10^6$，$1\le n\le 2^{10^6}$。 --- 注意：本题**不开启文件输入输出**。你无需**从kogasa.in**读入，也无需**输出到kogasa.out**。