小$A$和小$B$在做游戏。他们找到了一个$n$行$m$列呈网格状的画板。小$A$拿出了$p$支不同颜色的画笔，开始在上面涂色。看到小$A$涂好的画板，小$B$觉得颜色太单调了，于是把画板擦干净，希望涂上使它看起来不单调的颜色（当然，每个格子里只能涂一种颜色）。小$B$想知道一共有多少种不单调的涂色方案。我们定义一个涂色方案是不单调的，当且仅当任意相邻两列都出现了至少$q$种颜色。

一行四个整数$n,m,p,q$，意义如题中所述。

一行一个整数，表示不单调的涂色方案数模$998244353$的值。

样例输入：

2 3 3 3

样例输出：

162

对于$20\%$的数据：$n\times m\leqslant 15,q\leqslant p\leqslant 3$对于另外$20\%$的数据：$n\leqslant 7,m\leqslant 100,p=q=2$对于另外$30\%$的数据：$n\leqslant 100,m\leqslant 1,000,q\leqslant p\leqslant 100$对于$100\%$的数据：$n\leqslant 100,m\leqslant {10}^9 ,q\leqslant p\leqslant 100$

首先，明确题意，不能不涂（也是被这个我并没有看出来的条件坑死了……）

静观数据范围，显然是矩阵快速幂。

那么，我们现在思考如何构建转移矩阵。

先把矩阵搁在一边，考虑$DP$，设$f[i][j]$表示对于一列，选到了第$i$行的格子，恰好涂了$j$种颜色的方案数，直接给出式子：

$$f[i][j]=f[i-1][j-1]\times (p-(j-1))+f[i-1][j]\times j$$

前半部分的转移即为又选了一个新的，那么我就要在这么多的颜色中再选一个；后半部分相当于我又从原来的$j$中颜色中选了一种涂在了这里。

那么，我们在设$g[j]$表示对于一列，选了$j$种颜色的方案数，那么根据第二类斯特林数（类比将$n$个有区别的小球放进$m$个没有区别的盒子，每个盒子至少放一个小球），一列中涂上每种$j$元颜色集合的颜色的方案数就是$\frac{g[j]}{C_p^j}$。

那么，我们对于这一列用了$j$元集合，下一列要用$k$元集合，则方案数为：

$$\sum \limits_{x=\max(q,j,k)}^{\min(p,j+k)}C_j^{j+k-x}C_{p-i}^{x-j}$$

解释一下上式，考虑两个极端情况，$\alpha.j\cup k=\varnothing$，$\beta.j\subset k\ or\ k\subset j$，这也是上式的上下线；再来理解组合数，因为$j$和$k$会有交集，所以前一个组合数就是交集，而第二个就是交集以外的。

现在，我们令：

$$trans[j][k]=\frac{g[j]}{C_p^j}\sum \limits_{x=\max(q,j,k)}^{\min(p,j+k)}C_j^{j+k-x}C_{p-i}^{x-j}$$

那么，$dp[i][k]=dp[i-1][j]\times [j][k]$，$dp[1][j]=g[j]$。

这样我们就可以拿到$70$分了。

观察式子，可以用矩阵快速幂快速转移。

时间复杂度：$\Theta(n^3\log m)$。

期望得分：$100$分。

实际得分：$100$分。