NC1030. 与巨

题目描述

定义无穷数列 f：f(1)=1,f(n)=f(n-1) ×2+1。

定义函数 G(x)=min(fi)>=x。

dp[c][0]=0,dp[c][i]=max(dp[c][i-1],[((i×c)&G(i))=i]×i)。

求 ∑ i=0~n dp[c][i] mod 998244353

输入格式

第一行输入一个整数 T，表示测试用例的组数。

每组测试用例输入一行包含两个整数n,c。

其中 n 以二进制形式表示，且 n 不含有前导 0

输出格式

对于每组测试用例输出一行一个整数表示答案。

样例:

样例输入

5 1001 1

11111 1

101010111101 8999

10100101111010101 799

10010010 233 样例输出 #1

45

496

2835797

707482963

9940 数据范围

  测试点编号	        数据约束

1∼4	1≤∣n∣≤20,1≤c≤1e9
5∼8	1≤∣n∣≤30,1≤c≤50
9∼12	1≤∣n∣≤200000,1≤c≤1e9
13∼20	1≤∣n∣≤10000000,1≤c≤1e18

对于全部数据： 1≤T≤10，单个测试点中 ∑∣n∣≤1e7