{"problem":{"name":"B. Ralph And His Magic Field","description":{"content":"Ralph has a magic field which is divided into _n_ × _m_ blocks. That is to say, there are _n_ rows and _m_ columns on the field. Ralph can put an integer in each block. However, the magic field doesn'","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF894B"},"statements":[{"statement_type":"Markdown","content":"Ralph has a magic field which is divided into _n_ × _m_ blocks. That is to say, there are _n_ rows and _m_ columns on the field. Ralph can put an integer in each block. However, the magic field doesn't always work properly. It works only if the product of integers in each row and each column equals to _k_, where _k_ is either _1_ or _\\-1_.\n\nNow Ralph wants you to figure out the number of ways to put numbers in each block in such a way that the magic field works properly. Two ways are considered different if and only if there exists at least one block where the numbers in the first way and in the second way are different. You are asked to output the answer modulo 1000000007 = 109 + 7.\n\nNote that there is no range of the numbers to put in the blocks, but we can prove that the answer is not infinity.\n\n## Input\n\nThe only line contains three integers _n_, _m_ and _k_ (1 ≤ _n_, _m_ ≤ 1018, _k_ is either _1_ or _\\-1_).\n\n## Output\n\nPrint a single number denoting the answer modulo 1000000007.\n\n[samples]\n\n## Note\n\nIn the first example the only way is to put _\\-1_ into the only block.\n\nIn the second example the only way is to put _1_ into every block.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Ralph 有一个魔法字段，该字段被划分为 #cf_span[n × m] 个格子。也就是说，字段上有 #cf_span[n] 行和 #cf_span[m] 列。Ralph 可以在每个格子中填入一个整数。然而，魔法字段并不总是正常工作；只有当每一行和每一列的整数乘积都等于 #cf_span[k] 时，它才会正常工作，其中 #cf_span[k] 为 _1_ 或 _-1_。\n\n现在 Ralph 希望你计算出有多少种方法可以在每个格子中填入数字，使得魔法字段正常工作。如果存在至少一个格子，在两种方法中填入的数字不同，则认为这两种方法不同。你需要输出答案对 #cf_span[1000000007 = 109 + 7] 取模的结果。\n\n请注意，填入格子的数字没有范围限制，但我们能够证明答案不是无穷大。\n\n输入仅一行，包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n, m ≤ 1018]，#cf_span[k] 为 _1_ 或 _-1_）。\n\n请输出一个数字，表示对 #cf_span[1000000007] 取模后的答案。\n\n在第一个例子中，唯一的方法是将 _-1_ 填入唯一的格子。\n\n在第二个例子中，唯一的方法是将 _1_ 填入每一个格子。\n\n## Input\n\nThe only line contains three integers #cf_span[n], #cf_span[m] and #cf_span[k] (#cf_span[1 ≤ n, m ≤ 1018], #cf_span[k] is either _1_ or _-1_).\n\n## Output\n\nPrint a single number denoting the answer modulo #cf_span[1000000007].\n\n[samples]\n\n## Note\n\n在第一个例子中，唯一的方法是将 _-1_ 填入唯一的格子。在第二个例子中，唯一的方法是将 _1_ 填入每一个格子。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n, m \\in \\mathbb{N} $, $ n, m \\geq 1 $, and $ k \\in \\{1, -1\\} $.\n\nWe consider an $ n \\times m $ matrix $ A = (a_{ij}) $ with entries $ a_{ij} \\in \\{1, -1\\} $, such that:\n\n- For all $ i \\in \\{1, 2, \\dots, n\\} $, $ \\prod_{j=1}^m a_{ij} = k $,\n- For all $ j \\in \\{1, 2, \\dots, m\\} $, $ \\prod_{i=1}^n a_{ij} = k $.\n\nLet $ N(n, m, k) $ denote the number of such matrices.\n\nWe seek $ N(n, m, k) \\mod 1000000007 $.\n\n---\n\n**Observation:**\n\nThe constraints on row and column products are not independent. The product of all row products equals the product of all column products, both equaling $ k^n $ and $ k^m $, respectively. Therefore, we must have:\n\n$$\nk^n = k^m \\quad \\Rightarrow \\quad k^{n - m} = 1\n$$\n\nSince $ k \\in \\{1, -1\\} $, this holds if and only if:\n\n- $ k = 1 $, always true,\n- or $ k = -1 $ and $ n \\equiv m \\pmod{2} $.\n\nThus:\n\n- If $ k = -1 $ and $ n \\not\\equiv m \\pmod{2} $, then $ N(n, m, k) = 0 $.\n\nOtherwise, the degrees of freedom are in the top-left $ (n-1) \\times (m-1) $ submatrix. The last row and last column are determined by the product constraints, and the bottom-right corner is consistently determined if and only if $ k^n = k^m $, which we've already ensured.\n\nTherefore, for valid cases:\n\n$$\nN(n, m, k) = \n\\begin{cases}\n0 & \\text{if } k = -1 \\text{ and } n \\not\\equiv m \\pmod{2}, \\\\\n2^{(n-1)(m-1)} & \\text{otherwise}.\n\\end{cases}\n$$\n\n---\n\n**Final Answer:**\n\n$$\n\\boxed{\n\\begin{cases}\n0 & \\text{if } k = -1 \\text{ and } n \\not\\equiv m \\pmod{2}, \\\\\n2^{(n-1)(m-1)} \\mod 1000000007 & \\text{otherwise}.\n\\end{cases}\n}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF894B","tags":["combinatorics","constructive algorithms","math","number theory"],"sample_group":[["1 1 -1","1"],["1 3 1","1"],["3 3 -1","16"]],"created_at":"2026-03-03 11:00:39"}}