当前没有测试数据。

题目描述

作为 $\red{GDOI }$的组题人，小 $\red{Y }$需要整理手中已有的题目，考虑它们的难度以及所考察的知识点，然后将它 们组成数套题目。小 $\red{Y }$希望先能组出第一套题目，为了整套题目具有良好的区分度，在一套题目中：

•所有题目的难度需要能排成等差数列；（也就是说，若将所有题目按难度从小到大排序，那么每相邻两 题的难度的差相等，这个差叫做公差）

•每道题目的难度都是公差的倍数，公差不为 $\red{0}$；

•需要有不少于 $\red{L }$道题，不多于 $\red{R }$道题。

现在小 $\red{Y }$手里已经有了 $\red{m }$道题目，其中难度为 $\red{a_i }$的题有 $\red{c_i }$道（$\red{1 ≤}$ $\red{i ≤}$ $\red{n）}$。小 $\red{Y }$希望能够知道，他 有多少种不同的方式能够组出一套题目。

在这道题目中，我们认为两种组题方式不同当且仅当 $\red{∃k(1 ≤}$ $\red{k ≤}$ $\red{m)，}$使得一种方案包含第 $\red{k }$道题而另 一种方案不包含。由于答案可能很大，输出答案对 $\red{998244353 }$取模。

输入格式

第一行三个整数 $\red{n, m, L, R，}$分别表示有多少种不同难度的题目、题目总数、一套题的题数下限和上限。

接下来 $\red{n }$行，每行两个正整数 $\red{a_i, c_i，}$表示有 $\red{c_i }$道难度为 $\red{a_i }$的题（$\red{1 ≤}$ $\red{i ≤}$ $\red{n）}$

输出格式

输出一个数，表示组题方案数对 $\red{998244353 }$取模的值

样例

输入样例

6 12 2 3
2 2
4 2
6 2
8 2
12 2
16 2

输出样例

64

提示

对于所有测试点，$\red{1 ≤}$ $\red{n, c_i ≤}$ $\red{10^5，}$$\red{0 ≤}$ $\red{a_i ≤}$ $\red{10^5，}$$\red{m =\sum_{i=1}^{n}c_i ≤}$ $\red{10^5，}$$\red{2 ≤}$ $\red{L ≤}$ $\red{R ≤}$ $\red{m，}$$\red{a_i }$两两不同。