409789: GYM103743 F Pockets

F. Pocketstime limit per test8 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Luna is shopping at a magic shop, where $$$n$$$ kinds of items are on sale. The value of the $$$i$$$-th kind of item is $$$v_i$$$, and the weight is $$$w_i$$$. The number of items is infinity. Luna's pocket can carry items with a total weight of no more than $$$k$$$. Each time, Luna can take one item of any kind. She can take at most $$$m$$$ times.

In order to take more items, Luna uses magic so that if the number of items she buys is $$$i$$$, she can carry a total weight of at most $$$i+k$$$. Her happiness of shopping is the product of the value over all the items she buys. If she buys nothing, the happiness is $$$1$$$.

There are many ways to buy items, and she wants to know the sum of happiness of all the possible ways of shopping. Since the number can be very large, just tell her the number modulo $$$998244353$$$.

Two ways of shopping are considered different if the number of times to take items are different or she takes a different kind of item at one time.

Input

The first line of input contains three integers $$$n,m,k$$$ ($$$1\le n,m,k\le 10^5$$$), indicating the number of kinds of items, the maximum number of times to take items, and the capacity of the pocket.

Each of the following $$$n$$$ lines contains two integers $$$v,w$$$ ($$$1\le v< 998244353$$$, $$$0\le w\le m+k$$$), indicating the value and weight of the kind of item. It is guaranteed that there exists a kind of item that $$$w=0$$$.

Output

Print a single integer denoting the sum of happiness modulo $$$998244353$$$.

ExamplesInput

1 1 1
1 0

Output

2

Input

3 2 3
8 2
5 3
2 0

Output

216

Input

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

Output

983858

Note

The explanation of example 1:

• Luna can take nothing or take one item of kind 1, and the sum of happiness is 2.

The explanation of example 2:

• If Luna buys nothing, the happiness is 1.
• If Luna buys one turn, any kind is ok, so the sum of happiness is 8+5+2=15.
• If Luna buys two turns, the sum of weight should be at most 5.
• If Luna buys kind 1 in the first turn, and kind 1 in the second turn, the happiness is 64.
• If Luna buys kind 1 in the first turn, and kind 2 in the second turn, the happiness is 40.
• If Luna buys kind 1 in the first turn, and kind 3 in the second turn, the happiness is 16.
• If Luna buys kind 2 in the first turn, and kind 1 in the second turn, the happiness is 40.
• If Luna buys kind 2 in the first turn, and kind 2 in the second turn, the weight is 6, which is invalid.
• If Luna buys kind 2 in the first turn, and kind 3 in the second turn, the happiness is 10.
• If Luna buys kind 3 in the first turn, and kind 1 in the second turn, the happiness is 16.
• If Luna buys kind 3 in the first turn, and kind 2 in the second turn, the happiness is 10.
• If Luna buys kind 3 in the first turn, and kind 3 in the second turn, the happiness is 4.

So the sum of happiness of two-turn shopping is $$$64+40+16+40+10+16+10+4=200$$$, and the sum of happiness is $$$1+15+200=216$$$.