面积恰为$k$不好处理，先求$\leq k$的概率

设$f_{i,j}$表示（有$i$列，最下$j$行都安全，第$j+1$行至少有一个位置危险）的概率，则$g_{i,j}=\sum\limits_{r\geq j}f_{i,r}$为（有$i$列，最下$j$行都安全）的概率

枚举第$j+1$行第一个危险的格子是哪个以转移

$f_{i,j}=\sum\limits_{r=0}^{i-1}g_{r,j+1}g_{i-r-1,j}q^j(1-q)$

左边$j+1$行$r$列，中间第$r+1$行最下$j$个格子，右边$j$行$i-r-1$列都要是安全的，同时$j+1$行第$r+1$个格子是危险的

因为当$ij\gt k$时$f_{i,j}=g_{i,j}=0$，所以直接DP时间复杂度是$O(n^2)$的

当$i\gt k$时，$f_{i,j}=0(j\geq1)$，所以我们只需要求$f_{i,0}$，此时转移为$g_{i,0}=f_{i,0}=\sum\limits_{r=0}^k(1-q)g_{r,1}g_{i-r-1,0}$，是$g_{i,0}$的常系数线性递推式，所以最终复杂度为$O(k^2\log_2n)$

#include
     
      #include
      
       typedef long long ll;const int mod=998244353;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;}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 t[2010];void mul(int*a,int*b,int*m,int*c,int n){	int i,j,u,v;	memset(t,0,sizeof(t));	for(i=0;i<=n;i++){		for(j=0;j<=n;j++){			t[i+j]=ad(t[i+j],mul(a[i],b[j]));		}	}	u=pow(m[n],mod-2);	for(i=n;i>=0;i--){		v=mul(u,t[i+n]);		for(j=0;j<=n;j++)t[i+j]=de(t[i+j],mul(m[j],v));	}	memcpy(c,t,n<<2);}void pow(int*a,int b,int*m,int*c,int n){	c[0]=1;	while(b){		if(b&1)mul(c,a,m,c,n);		mul(a,a,m,a,n);		b>>=1;	}}int f[2010][1010],id[1010],a[1010],res[1010],n,q;int solve(int k){	memset(f,0,sizeof(f));	memset(id,0,sizeof(id));	memset(a,0,sizeof(a));	memset(res,0,sizeof(res));	int i,j,r,t;	for(i=0;i<=k+1;i++)f[0][i]=1;	for(i=1;i<=2001;i++){		for(j=0;i*j<=k;j++){			t=mul(pow(q,j),1-q);			f[i][j]=0;			for(r=0;r
       
        <=k;r++)f[i][j]=ad(f[i][j],mul(mul(f[r][j+1],f[i-r-1][j]),t));		}		for(j=k/i;j>=0;j--)f[i][j]=ad(f[i][j],f[i][j+1]);	}	if(n<=1000)return f[n][0];	for(i=0;i<=k;i++)id[i]=mul(q-1,f[k-i][1]);	id[k+1]=1;	a[1]=1;	pow(a,n-k,id,res,k+1);	r=0;	for(i=0;i<=k+1;i++)r=ad(r,mul(res[i],f[k+i][0]));	return r;}int main(){	int k,x,y;	scanf("%d%d%d%d",&n,&k,&x,&y);	q=mul(x,pow(y,mod-2));	printf("%d",ad(de(solve(k),solve(k-1)),mod));}