{"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAlice has got addicted to a game called Sirtet recently.\u003c/p\u003e\u003cp\u003eIn Sirtet, player is given an $$$n \\times m$$$ grid. Initially $$$a_{i,j}$$$ cubes are stacked up in the cell $$$(i,j)$$$. Two cells are called adjacent if they share a side. Player can perform the following operations: \u003c/p\u003e\u003cul\u003e \u003cli\u003e stack up one cube in two \u003cspan class\u003d\"tex-font-style-bf\"\u003eadjacent\u003c/span\u003e cells; \u003c/li\u003e\u003cli\u003e stack up two cubes in one cell. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eCubes mentioned above are identical in height.\u003c/p\u003e\u003cp\u003eHere is an illustration of the game. States on the right are obtained by performing one of the above operations on the state on the left, and grey cubes are added due to the operation.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/718947fee7939e7ba8ca4b91b1913063?v\u003d1715688396\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003ePlayer\u0027s goal is to \u003cspan class\u003d\"tex-font-style-bf\"\u003emake the height of all cells the same\u003c/span\u003e (i.e. so that each cell has the same number of cubes in it) using above operations. \u003c/p\u003e\u003cp\u003eAlice, however, has found out that on some starting grids she may never reach the goal no matter what strategy she uses. Thus, she is wondering the number of initial grids such that \u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$L \\le a_{i,j} \\le R$$$ for all $$$1 \\le i \\le n$$$, $$$1 \\le j \\le m$$$; \u003c/li\u003e\u003cli\u003e player can reach the goal using above operations. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003ePlease help Alice with it. Notice that the answer might be large, please output the desired value modulo $$$998,244,353$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe only line contains four integers $$$n$$$, $$$m$$$, $$$L$$$ and $$$R$$$ ($$$1\\le n,m,L,R \\le 10^9$$$, $$$L \\le R$$$, $$$n \\cdot m \\ge 2$$$).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput one integer, representing the desired answer modulo $$$998,244,353$$$.\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\u003e2 2 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\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\u003e1 2 1 2\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":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample, the only initial grid that satisfies the requirements is $$$a_{1,1}\u003da_{2,1}\u003da_{1,2}\u003da_{2,2}\u003d1$$$. Thus the answer should be $$$1$$$.\u003c/p\u003e\u003cp\u003eIn the second sample, initial grids that satisfy the requirements are $$$a_{1,1}\u003da_{1,2}\u003d1$$$ and $$$a_{1,1}\u003da_{1,2}\u003d2$$$. Thus the answer should be $$$2$$$.\u003c/p\u003e"}}]}