{"raw_statement":[{"iden":"statement","content":"Hiasat loves burgers, that's 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's another grid of $n$ rows and $m$ columns with each cell having a height and width of 1.\n\nIn 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,..., 2 m$, 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,..., n m$.\n\nHiasat 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's 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.\n\nWhen 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's guaranteed that Hiasat will wake up eventually regardless of his starting cell)? Print it *module* $10^9 + 7$.\n\nA single line containing four space separated integers $n, m, r, c$($1 <= r <= n <= 2 dot.op 10^9, 1 <= c <= m <= 2 dot.op 10^9$).\n\nPrint a single integer the maximum happiness *module* $10^9 + 7$.\n\nIn the first example the grid looks like the grid below, Hiasat starts at the marked cell, he eats burgers with deliciousness $3 + 4 + 8 = 15$.\n\n"},{"iden":"input","content":"A single line containing four space separated integers $n, m, r, c$($1 <= r <= n <= 2 dot.op 10^9, 1 <= c <= m <= 2 dot.op 10^9$)."},{"iden":"output","content":"Print a single integer the maximum happiness *module* $10^9 + 7$."},{"iden":"examples","content":"Input3 3 1 1\nOutput15\nInput1 4 1 2\nOutput6\nInput2000000000 1 1 1\nOutput91\n"},{"iden":"note","content":"In the first example the grid looks like the grid below, Hiasat starts at the marked cell, he eats burgers with deliciousness $3 + 4 + 8 = 15$.  "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\{a, b, c\\}^* $ be the input string of length $ n = |s| $.  \nLet $ \\mathcal{O} = \\{1, 2, 3, 4\\} $ be the set of operation types:  \n- Type 1: Remove one 'a'.  \n- Type 2: Remove one 'b'.  \n- Type 3: Remove one 'c'.  \n- Type 4: Remove substring \"abc\" (consecutive, in order).  \n\nLet $ s^{(0)} = s $, and $ s^{(k)} $ be the string after $ k $ operations.  \nLet $ m \\in \\mathbb{Z}^+ $ be the number of operations, with $ 1 \\leq m \\leq 3n $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\times 10^5 $  \n2. Each operation must be valid on $ s^{(k-1)} $:  \n   - For type $ t \\in \\{1,2,3\\} $: the character at index $ i $ must match the type.  \n   - For type 4: the substring starting at index $ i $ must be \"abc\".  \n3. After each operation, the string is updated (characters removed, indices adjusted).  \n4. Final string must be empty: $ s^{(m)} = \\varepsilon $.  \n\n**Objective**  \nDetermine whether there exists a sequence of operations $ (t_1, i_1), (t_2, i_2), \\dots, (t_m, i_m) $ such that:  \n- All operations are valid.  \n- $ s^{(m)} = \\varepsilon $.  \n- $ m \\leq 3n $.  \n\nIf possible, output $ m $ and the sequence of operations.  \nIf impossible, output $-1$.","simple_statement":"You are given a string of 'a', 'b', 'c'. You can perform 4 types of operations to remove characters. Can you remove the entire string in at most 3n operations? If yes, output the sequence of operations; if no, output -1.","has_page_source":false}