{"problem":{"name":"D. Coin Table","description":{"content":"Eli has got a square board as his birthday present. Some cells of this board are filled with coins and other cells are empty. Rashof (her Russian bear doll) is capable of collecting coins and can go r","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10053D"},"statements":[{"statement_type":"Markdown","content":"Eli has got a square board as his birthday present. Some cells of this board are filled with coins and other cells are empty. Rashof (her Russian bear doll) is capable of collecting coins and can go right or down. She will put Rashof in the top-left cell of the table. If a rectangle of the table is blocked, which means Rashof can not pass or land on that rectangle at all, how many ways can Rashof take maximum number of coins and reach lower-right cell of the board?\n\nEach test case contains one positive integer n, the size of the board. Each of the next n lines contain n characters, '.' or 'C'. '.' is an empty cell and 'C' is a coin.   The next line contains Q, the number of queries. Each of the next Q lines contains four integers, r1, c1, r2 and c2, which are the top-left and bottom-right cells of the blocked rectangle.   For each query print the number of ways Rashof can take maximum number of coins.  1 ≤ n ≤ 1000   0 ≤ r1, c1, r2, c2 ≤ n - 1   1 ≤ Q ≤ 1000  \n\nFor each query print two space separated integers, the maximum number of coins Rashof can take without passing the blocked rectangle, and the number of ways it can do that modulo 1000000007.\n\n## Input\n\nEach test case contains one positive integer n, the size of the board. Each of the next n lines contain n characters, '.' or 'C'. '.' is an empty cell and 'C' is a coin.   The next line contains Q, the number of queries. Each of the next Q lines contains four integers, r1, c1, r2 and c2, which are the top-left and bottom-right cells of the blocked rectangle.   For each query print the number of ways Rashof can take maximum number of coins.  1 ≤ n ≤ 1000   0 ≤ r1, c1, r2, c2 ≤ n - 1   1 ≤ Q ≤ 1000  \n\n## Output\n\nFor each query print two space separated integers, the maximum number of coins Rashof can take without passing the blocked rectangle, and the number of ways it can do that modulo 1000000007.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the size of the square grid.  \nLet $ G = (V, E) $ be a grid graph with vertices $ V = \\{ (i,j) \\mid 0 \\leq i,j < n \\} $, and edges from $ (i,j) $ to $ (i+1,j) $ (down) and $ (i,j+1) $ (right).  \nLet $ c_{i,j} \\in \\{0,1\\} $ denote the coin count at cell $ (i,j) $:  \n$$\nc_{i,j} = \n\\begin{cases}\n1 & \\text{if cell } (i,j) \\text{ contains 'C'} \\\\\n0 & \\text{if cell } (i,j) \\text{ contains '.'}\n\\end{cases}\n$$  \nLet $ Q \\in \\mathbb{Z}^+ $ be the number of queries.  \nFor each query $ q \\in \\{1, \\dots, Q\\} $, let $ R_q = [r1_q, r2_q] \\times [c1_q, c2_q] \\subseteq V $ be a blocked rectangular region (inclusive), where Rashof cannot traverse any cell in $ R_q $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 1000 $  \n2. $ 0 \\leq r1_q, c1_q, r2_q, c2_q \\leq n-1 $ and $ r1_q \\leq r2_q $, $ c1_q \\leq c2_q $  \n3. $ 1 \\leq Q \\leq 1000 $  \n4. Rashof starts at $ (0,0) $, ends at $ (n-1, n-1) $, and moves only right or down.  \n5. All paths must avoid all cells in $ R_q $.  \n6. All computations are modulo $ 1000000007 $.\n\n**Objective**  \nFor each query $ q $, compute:  \n- $ M_q $: the maximum number of coins collectible along any valid path from $ (0,0) $ to $ (n-1,n-1) $ avoiding $ R_q $.  \n- $ W_q $: the number of such paths achieving $ M_q $, modulo $ 1000000007 $.  \n\nOutput $ (M_q, W_q) $ for each query.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10053D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}