{"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\u003eHiasat loves burgers, that\u0027s why he dreams about them while sleeping. One day he dreamed about an infinite grid of burgers, it can be described as an infinite grid with each cell having height of $$$n$$$ and width of $$$m$$$, inside each cell there\u0027s another grid of $$$n$$$ rows and $$$m$$$ columns with each cell having a height and width of 1.\u003c/p\u003e\u003cp\u003eIn each cell of the $$$n \\times m$$$ grid there was a burger, burgers in the first row had deliciousness equal to $$$1,2,3,...,m$$$ from left to right, in the second row the deliciousness of the burgers were equal to $$$m+1,m+2,m+3,...,2m$$$, and so on until the last row where the deliciousness of the burgers were equal to $$$(n-1)m+1,(n-1)m+2,(n-1)m+3,...,nm$$$.\u003c/p\u003e\u003cp\u003eHiasat is currently standing at some cell in the infinite grid, he will repeatedly do the following: If Hiasat ate before a burger that has deliciousness equal to the deliciousness of the burger in the cell he\u0027s currently standing at then he wakes up from the dream, otherwise he eats that burger and jump $$$r$$$ rows down and $$$c$$$ columns to the right.\u003c/p\u003e\u003cp\u003eWhen Hiasat wakes up from the dream his happiness will be equal to the sum of deliciousness of all the burgers he ate in his dream, if he chooses his starting cell optimally, what is the maximum possible happiness Hiasat can wake up with(it\u0027s guaranteed that Hiasat will wake up eventually regardless of his starting cell)? Print it \u003cspan class\u003d\"tex-font-style-bf\"\u003emodule\u003c/span\u003e $$$10^9+7$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eA single line containing four space separated integers $$$n,m,r,c$$$($$$1\\le r \\le n \\le 2\\cdot 10^9, 1 \\le c \\le m \\le 2\\cdot 10^9$$$).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer the maximum happiness \u003cspan class\u003d\"tex-font-style-bf\"\u003emodule\u003c/span\u003e $$$10^9+7$$$.\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\u003e3 3 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\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 4 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\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\u003e2000000000 1 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e91\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 example the grid looks like the grid below, Hiasat starts at the marked cell, he eats burgers with deliciousness $$$3+4+8\u003d15$$$.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/17e318bc0f4db1d7654d20197761bb93?v\u003d1714764628\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e"}}]}