Luna 正在一家魔法商店购物，店里有 $n$ 种商品在售。第 $i$ 种商品的价值为 $v_i$，重量为 $w_i$。每种商品的数量都是无限的。Luna 的口袋最多能携带总重量为 $k$ 的商品。每次，Luna 可以拿走任意一种商品。她最多可以拿 $m$ 次。

为了能拿走更多的商品，Luna 使用了魔法，使得如果她购买的商品数量为 $i$，她就能携带总重量不超过 $i + k$ 的商品。购物的幸福度定义为她所购买的所有商品的价值乘积。如果她什么都不买，幸福度为 $1$。

购买商品的方式有很多种，她想知道所有可能的购物方式的幸福度之和。由于这个数字可能非常大，请输出该数字对 $998244353$ 取模的结果。

如果两次购物的拿取次数不同，或者在某一次拿取的商品种类不同，则认为这两种购物方式是不同的。

输入格式

第一行包含三个整数 $n, m, k$ ($1 \le n, m, k \le 10^5$)，分别表示商品种类数、最多拿取次数以及口袋的基础容量。

接下来的 $n$ 行，每行包含两个整数 $v, w$ ($1 \le v < 998244353, 0 \le w \le m + k$)，表示该种商品的价值和重量。保证存在一种重量 $w = 0$ 的商品。

输出格式

输出一个整数，表示幸福度之和对 $998244353$ 取模的结果。

样例

输入 1

1 1 1
1 0

输出 1

2

输入 2

3 2 3
8 2
5 3
2 0

输出 2

216

输入 3

7 4 6
8 2
5 3
2 0
4 2
7 5
5 8
11 2

输出 3

983858

说明

样例 1 的解释： * Luna 可以什么都不买，或者拿一件第 1 种商品，幸福度之和为 $2$。

样例 2 的解释： 如果 Luna 什么都不买，幸福度为 $1$。 如果 Luna 拿一次，任何种类都可以，所以幸福度之和为 $8+5+2=15$。 如果 Luna 拿两次，总重量应不超过 $5$。 如果 Luna 第一轮拿第 1 种，第二轮拿第 1 种，幸福度为 $64$。 如果 Luna 第一轮拿第 1 种，第二轮拿第 2 种，幸福度为 $40$。 如果 Luna 第一轮拿第 1 种，第二轮拿第 3 种，幸福度为 $16$。 如果 Luna 第一轮拿第 2 种，第二轮拿第 1 种，幸福度为 $40$。 如果 Luna 第一轮拿第 2 种，第二轮拿第 2 种，总重量为 $6$，不符合要求。 如果 Luna 第一轮拿第 2 种，第二轮拿第 3 种，幸福度为 $10$。 如果 Luna 第一轮拿第 3 种，第二轮拿第 1 种，幸福度为 $16$。 如果 Luna 第一轮拿第 3 种，第二轮拿第 2 种，幸福度为 $10$。 如果 Luna 第一轮拿第 3 种，第二轮拿第 3 种，幸福度为 $4$。

因此，两次购物的幸福度之和为 $64 + 40 + 16 + 40 + 10 + 16 + 10 + 4 = 200$，总的幸福度之和为 $1 + 15 + 200 = 216$。