{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eGiven are sequences of \u003cvar\u003e\\(N\\)\u003c/var\u003e integers each: \u003cvar\u003e\\(A \u003d (A_1, \\dots, A_N)\\)\u003c/var\u003e and \u003cvar\u003e\\(B \u003d (B_1, \\dots, B_N)\\)\u003c/var\u003e. Find the number of non-empty subsets \u003cvar\u003e\\(S\\)\u003c/var\u003e of \u003cvar\u003e\\(\\{1,2,\\ldots,N\\}\\)\u003c/var\u003e that satisfy the following condition:\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(\\max_{i \\in S} A_i \\geq \\sum_{i \\in S} B_i\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eSince the count can be enormous, print it modulo \u003cvar\u003e\\(998244353\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Constraints","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq N \\leq 5000\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq A_i,B_i \\leq 5000\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003eAll values in input are integers.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Input","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eInput is given from Standard Input in the following format:\u003c/p\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(N\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(A_1\\)\u003c/var\u003e \u003cvar\u003e\\(A_2\\)\u003c/var\u003e \u003cvar\u003e\\(\\ldots\\)\u003c/var\u003e \u003cvar\u003e\\(A_N\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(B_1\\)\u003c/var\u003e \u003cvar\u003e\\(B_2\\)\u003c/var\u003e \u003cvar\u003e\\(\\ldots\\)\u003c/var\u003e \u003cvar\u003e\\(B_N\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Output","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003ePrint the number of subsets \u003cvar\u003e\\(S\\)\u003c/var\u003e that satisfy the condition in the Problem Statement, modulo \u003cvar\u003e\\(998244353\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 1","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\u003e2\r\n3 1\r\n1 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cp\u003e\u003cvar\u003e\\(\\{1,2,\\ldots,N\\}\\)\u003c/var\u003e has three subsets: \u003cvar\u003e\\(\\{1\\}\\)\u003c/var\u003e, \u003cvar\u003e\\(\\{2\\}\\)\u003c/var\u003e, and \u003cvar\u003e\\(\\{1,2\\}\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eFor \u003cvar\u003e\\(S\u003d\\{1\\}\\)\u003c/var\u003e, we have \u003cvar\u003e\\(\\max_{i \\in S} A_i\u003d3\\)\u003c/var\u003e and \u003cvar\u003e\\(\\sum_{i \\in S} B_i\u003d1\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003cli\u003eFor \u003cvar\u003e\\(S\u003d\\{2\\}\\)\u003c/var\u003e, we have \u003cvar\u003e\\(\\max_{i \\in S} A_i\u003d1\\)\u003c/var\u003e and \u003cvar\u003e\\(\\sum_{i \\in S} B_i\u003d2\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003cli\u003eFor \u003cvar\u003e\\(S\u003d\\{1,2\\}\\)\u003c/var\u003e, we have \u003cvar\u003e\\(\\max_{i \\in S} A_i\u003d3\\)\u003c/var\u003e and \u003cvar\u003e\\(\\sum_{i \\in S} B_i\u003d3\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eThus, the condition \u003cvar\u003e\\(\\max_{i \\in S} A_i \\geq \\sum_{i \\in S} B_i\\)\u003c/var\u003e is satisfied by two subsets: \u003cvar\u003e\\(\\{1\\}\\)\u003c/var\u003e and \u003cvar\u003e\\(\\{1,2\\}\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 2","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\u003e2\r\n1 1\r\n2 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cp\u003eThere may be no subsets that satisfy the condition.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 3","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\u003e20\r\n1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247\r\n4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e476\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\u003c/section\u003e\r\n"}}]}