古明地恋(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<stdio.h>
#include<string.h>
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<n;N<<=1)k++;
for(i=0;i<N;i++)rev[i]=(rev[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<N;i++){
if(i<rev[i])swap(a[i],a[rev[i]]);
}
for(i=2;i<=N;i<<=1){
wn=pow(3,(on==1)?(mod-1)/i:(mod-1-(mod-1)/i));
for(j=0;j<N;j+=i){
w=1;
for(k=0;k<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<N;i++)a[i]=mul(a[i],iN);
}
}
int f[1100010];
char s[30];
int main(){
int n,p,i,j,las,al,rl,ans;
scanf("%d%d%s",&n,&p,s+1);
las=0;
al=(1<<n)-1;
rl=pow((al+1)*(ll)al/2%mod,mod-2);
ans=0;
for(i=1;i<=n;i++){
if(s[i]=='1'){
pre(1<<(i-las));
memset(f,0,sizeof(f));
for(j=0;j<=al;j++)inc(f[(j&((1<<i)-1))>>las],mul(j,rl));
ntt(f,1);
for(j=0;j<N;j++)f[j]=mul(mul(1-p,f[j]),pow(1-mul(p,f[j]),mod-2));
ntt(f,-1);
for(j=0;j<N;j++)inc(ans,mul(j<<las,f[j]));
las=i;
}
}
printf("%d",(ans+mod)%mod);
}