古明地恋(koishi)和计算器(calculator)是好朋友。

恋恋有一个神奇的计算器，可以进行两个数在模$2^n$意义下的加法运算。计算器上有一个寄存器，一开始寄存器中的数为$0$，每当恋恋输入一个数，计算器就会把寄存器中的值与输入的数相加，并存在寄存器中（覆盖原有的值）。

计算器内部采用二进制进行数的存储，两个数相加时，它会按照二进制加法的规则，从低位到高位依次相加、进位，并舍弃掉最后多出来的第$n+1$位。由于年久失修，计算器上的某些数位出了点小故障，这些数位上不会发生进位。也就是说，在加法的过程中，如果这个数位上的值超过了$1$，它会对$2$取模，而下一个数位却不会$+1$（显然第$n$位是否故障并没有多大区别，为了方便我们钦定它一定故障）。

恋恋会不停地向计算器输入数字。每次，她会在$[0,2^n)$的范围内随机选取一个数进行输入。这里每个数被选取的概率与它的数值大小成正比，也就是说，$x$被选中的概率为$\begin{align*}\dfrac x{\sum\limits_{i=0}^{2^n−1}i}\end{align*}$。每当恋恋输入完一个数，她会有$\dfrac{998244354−p}{998244354}$的概率感到厌倦，否则她会继续重复这一过程，直到她厌倦为止。现在，恋恋想知道在她感到厌倦之后，寄存器中的数的期望值是多少，答案对$998244353$取模。

每一段$0\cdots01$互不影响，可以分开计算答案，假设当前要计算一段长度为$m$的区间的答案

设$p_i$表示输入$i$的概率，构造多项式$\begin{align*}A(x)=\sum\limits_{i=0}^\infty p_ix^i\end{align*}$，那么$[x^k]\begin{align*}\sum\limits_{i=0}^\infty(1-p)p^iA^{i+1}(x)\end{align*}$就是最后和为$k$的概率（枚举恋恋在第$i$次加法时停止）注意这里的下标要模$2^m$，也就是说多项式乘法是循环卷积

等比数列求和一下，我们得到答案为$[x^k]\dfrac{(1-p)A(x)}{1-pA(x)}$，因为是循环卷积，所以直接用点值计算是可行的，就不用写多项式求逆了

#include
     
      #include
      
       const int mod=998244353;typedef long long ll;int mul(int a,int b){return a*(ll)b%mod;}int ad(int a,int b){return(a+b)%mod;}int de(int a,int b){return(a-b)%mod;}void inc(int&a,int b){a=ad(a,b);}int pow(int a,int b){	int s=1;	while(b){		if(b&1)s=mul(s,a);		a=mul(a,a);		b>>=1;	}	return s;}int rev[1100010],N,iN;void pre(int n){	int i,k;	for(N=1,k=0;N
       
        <<=1)k++;	for(i=0;i
        
         >1]>>1)|((i&1)<<(k-1));	iN=pow(N,mod-2);}void swap(int&a,int&b){a^=b^=a^=b;}void ntt(int*a,int on){	int i,j,k,t,w,wn;	for(i=0;i
         
          >1;k++){				t=mul(w,a[i/2+j+k]);				a[i/2+j+k]=de(a[j+k],t);				inc(a[j+k],t);				w=mul(w,wn);			}		}	}	if(on==-1){		for(i=0;i
          
           >las],mul(j,rl)); ntt(f,1); for(j=0;j