Description

张士超是你在上海音乐学院的同(ji)学(you)，关系非常好。你们在五角场附件合租了一间屋子 每天晚上给给。由于你那么有钱，一下买了 $n$ 把相同的锁，并一下配了 $N$ 把相同的钥匙。你用这些锁并联锁住你家的大门，需要同时插入 $n$ 把钥匙才能打开。

一天晚上，张士超带着华师大的姑娘去了闵行。而且还把你们的 $N$ 把钥匙全部藏在了一些奇怪的地方。王八蛋王八蛋张士超，欠下了欠下了N把钥匙，带着他的小姨子跑了。

张士超有 $M$ 个可能的地方来藏钥匙，比如地毯，花园，或门口大爷。每处藏匿位置至多可容纳 $a\_i$ 把钥匙，并且有 $p\_i$ 的独立概率被你找到。当然如果一个位置被你找到了，你就会拿到这里的所有钥匙。你必须至少拿到其中 $n$ 把钥匙才能回家。

假设张士超按所有合法方案中的任何一种方案放钥匙的概率相同。现在你希望算出你可以找到钥匙顺利回家的概率，如果这个概率太小，就干脆打车跑到闵行去把张士超痛扁一顿。

张士超在闵行乐不思蜀，你却在五角场无家可归。你必须在2s内算出答案，否则就会在寒风凛冽的国定路被冻死。

对$998244353$取模。为避免除法可能出现的问题，请输出答案乘上合法方案总数的积，即放钥匙的所有方案中能回家的概率之和。合法方案即一个数组 $b_i(1\le i\le M)$ 满足 $0\le b\_i\le a_i,~\sum_ib_i=N$。

Input

第一行3个正整数 $M, d, N, n$

接下来 $M$ 行，每行2个整数 $a_i, p_i$，保证 $d|(a_i+1)$

所有概率都在模$998244353$意义下计算。

Output

输出一行一个整数表示你能回家的概率乘上合法方案数对$998244353$取模的结果。

Sample

input I

2 1 11 5
8 249561089
19 0

output I

3

explanation

共$9$种合法方案，即枚举在第$1$个地方放$0$至$8$把。 其中能回家的必须是在第$1$个地方放了至少$5$把，并以 $p_1=\frac34$ 的概率成功找到。 所以答案是 $\frac49\times\frac34=\frac13$，应输出 $\frac13\times9=3$

Constraints

所有测试数据满足 $1\le M\le100,~1\le n\le N\le\sum a_i,~1\le N,a_i\le10^9,~1\le d\le10^7,~0\le p_i<998244353$ $N\le100d,~d|(a_i+1)$，但并不保证 $d|N$ 或 $d|n$

</tbody> </table>

Other Constraints	$M,~N$	Points
$a_i\le 10$	$M\le 6$	10
$n=1$ 或 $n=N$	$N\le100$	5
		15
$p_i\in\{0,1\}$	$N\le100$	5
		15
No more constraints	$N\le100$	30
		20