{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eLuna 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\u0027s 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.\u003c/p\u003e\u003cp\u003eIn 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$$$. \u003c/p\u003e\u003cp\u003eThere 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$$$.\u003c/p\u003e\u003cp\u003eTwo 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eEach of the following $$$n$$$ lines contains two integers $$$v,w$$$ ($$$1\\le v\u0026lt; 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\u003d0$$$. \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer denoting the sum of happiness modulo $$$998244353$$$.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 1 1\n1 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2 3\n8 2\n5 3\n2 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e216\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 4 6\n8 2\n5 3\n2 0\n4 2\n7 5\n5 8\n11 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e983858\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe explanation of example 1: \u003c/p\u003e\u003cul\u003e \u003cli\u003e Luna can take nothing or take one item of kind 1, and the sum of happiness is 2. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe explanation of example 2: \u003c/p\u003e\u003cul\u003e \u003cli\u003e If Luna buys nothing, the happiness is 1. \u003c/li\u003e\u003cli\u003e If Luna buys one turn, any kind is ok, so the sum of happiness is 8+5+2\u003d15. \u003c/li\u003e\u003cli\u003e If Luna buys two turns, the sum of weight should be at most 5. \u003c/li\u003e\u003cli\u003e If Luna buys kind 1 in the first turn, and kind 1 in the second turn, the happiness is 64. \u003c/li\u003e\u003cli\u003e If Luna buys kind 1 in the first turn, and kind 2 in the second turn, the happiness is 40. \u003c/li\u003e\u003cli\u003e If Luna buys kind 1 in the first turn, and kind 3 in the second turn, the happiness is 16. \u003c/li\u003e\u003cli\u003e If Luna buys kind 2 in the first turn, and kind 1 in the second turn, the happiness is 40. \u003c/li\u003e\u003cli\u003e If Luna buys kind 2 in the first turn, and kind 2 in the second turn, the weight is 6, which is invalid. \u003c/li\u003e\u003cli\u003e If Luna buys kind 2 in the first turn, and kind 3 in the second turn, the happiness is 10. \u003c/li\u003e\u003cli\u003e If Luna buys kind 3 in the first turn, and kind 1 in the second turn, the happiness is 16. \u003c/li\u003e\u003cli\u003e If Luna buys kind 3 in the first turn, and kind 2 in the second turn, the happiness is 10. \u003c/li\u003e\u003cli\u003e If Luna buys kind 3 in the first turn, and kind 3 in the second turn, the happiness is 4. \u003c/li\u003e\u003c/ul\u003e So the sum of happiness of two-turn shopping is $$$64+40+16+40+10+16+10+4\u003d200$$$, and the sum of happiness is $$$1+15+200\u003d216$$$."}}]}