{"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正在一个魔法商店购物,那里有$$$n$$$种物品在售。第$$$i$$$种物品的价值为$$$v_i$$$,重量为$$$w_i$$$。物品的数量是无限的。Luna的口袋最多可以携带总重量不超过$$$k$$$的物品。每次,Luna可以拿走任意一种物品。她最多可以拿走$$$m$$$次。\u003c/p\u003e\u003cp\u003e为了拿更多的物品,Luna使用魔法,这样如果她购买的物品数量为$$$i$$$,她可以携带的总重量最多为$$$i+k$$$。她的购物幸福感是她购买的所有物品价值的乘积。如果她什么都不买,幸福感为$$$1$$$。\u003c/p\u003e\u003cp\u003e购买物品有许多种方式,她想知道所有可能的购物方式的幸福感总和。由于数字可能非常大,只需告诉她对$$$998244353$$$取模的数字。\u003c/p\u003e\u003cp\u003e如果拿物品的次数不同或者她每次拿不同种类的物品,那么认为两种购物方式是不同的。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含三个整数$$$n,m,k$$$($$$1\\le n,m,k\\le 10^5$$$),表示物品种类数、最多拿物品的次数和口袋容量。\u003c/p\u003e\u003cp\u003e接下来的$$$n$$$行中,每行包含两个整数$$$v,w$$$($$$1\\le v\u0026lt; 998244353$$$,$$$0\\le w\\le m+k$$$),表示物品的价值和重量。保证存在一种物品满足$$$w\u003d0$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数,表示对$$$998244353$$$取模后的幸福感总和。\u003c/p\u003e"}},{"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\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"}},{"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"}},{"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"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e示例1的解释:\u003c/p\u003e\u003cul\u003e\u003cli\u003eLuna可以什么都不拿或者拿一件第1种物品,幸福感总和为2。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e示例2的解释:\u003c/p\u003e\u003cul\u003e\u003cli\u003e如果Luna什么都不买,幸福感为1。\u003c/li\u003e\u003cli\u003e如果Luna购买一次,任何种类都可以,所以幸福感总和为8+5+2\u003d15。\u003c/li\u003e\u003cli\u003e如果Luna购买两次,总重量应最多为5。\u003c/li\u003e\u003cli\u003e如果Luna第一次购买第1种物品,第二次购买第1种物品,幸福感为64。\u003c/li\u003e\u003cli\u003e如果Luna第一次购买第1种物品,第二次购买第2种物品,幸福感为40。\u003c/li\u003e\u003cli\u003e如果Luna第一次购买第1种物品,第二次购买第3种物品,幸福感为16。\u003c/li\u003e\u003cli\u003e如果Luna第一次购买第2种物品,第二次购买第1种物品,幸福感为40。\u003c/li\u003e\u003cli\u003e如果Luna第一次购买第2种物品,第二次购买第2种物品,总重量为6,不合法。\u003c/li\u003e\u003cli\u003e如果Luna第一次购买第2种物品,第二次购买第3种物品,幸福感为10。\u003c/li\u003e\u003cli\u003e如果Luna第一次购买第3种物品,第二次购买第1种物品,幸福感为16。\u003c/li\u003e\u003cli\u003e如果Luna第一次购买第3种物品,第二次购买第2种物品,幸福感为10。\u003c/li\u003e\u003cli\u003e如果Luna第一次购买第3种物品,第二次购买第3种物品,幸福感为4。\u003c/li\u003e\u003c/ul\u003e所以两次购物的幸福感总和为$$$64+40+16+40+10+16+10+4\u003d200$$$,幸福感总和为$$$1+15+200\u003d216$$$。"}}]}