---{"category_name":"medium","problem_code":"MATPERM","problem_name":"Matrix Permutations","problemComponents":{"constraints":"- $1 \\leq T \\leq 1,000$\n- $1 \\leq N,M \\leq 50,000$\n- $1 \\leq K \\leq \\min(N \\cdot M, 1,000)$\n- $1 \\leq R_i \\leq N$ for each valid $i$\n- $1 \\leq C_i \\leq M$ for each valid $i$\n- the sum of $K$ over all test cases does not exceed $1,000$\n- the sum of $N$ over all test cases does not exceed $10^7$\n- the sum of $M$ over all test cases does not exceed $10^7$\n","constraintsState":true,"subtasks":"**Subtask #1 (30 points):** \n- $1 \\leq N \\cdot M \\leq 10^6$\n- The sum of $ N \\cdot M$ over all test cases does not exceed $10^6$\n\n**Subtask #2 (70 points):** original constraints\n","subtasksState":true,"inputFormat":"- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\n- The first line of each test case contains three space-separated integers $N$, $M$ and $K$.\n- $K$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $R_i$ and $C_i$ — the row and column where the $i$-th cannon is located.\n","inputFormatState":true,"outputFormat":"For each test case, print a single line containing one integer $P \\cdot Q^{-1}$ modulo $2,500,000,001$.\n","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"3\n2 2 2\n1 1\n2 2\n2 2 4\n1 1\n1 2\n2 1\n2 2\n1 2 1\n1 1","output":"1250000001\n1\n1250000001\n","explanation":"","isDeleted":false}}},"video_editorial_url":"","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"vanshkaul","problem_tester":"","date_added":"29-07-2021","tags":{"0":"ltime98","1":"medium","2":"vanshkaul"},"problem_difficulty_level":"Medium-Hard","best_tag":"Medium Hard","editorial_url":"https://discuss.codechef.com/problems/MATPERM","time":{"view_start_date":1627745402,"submit_start_date":1627745402,"visible_start_date":1627745402,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=MATPERM","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problem statements in [Mandarin](https://www.codechef.com/download/translated/LTIME98/mandarin/MATPERM.pdf), [Bengali](https://www.codechef.com/download/translated/LTIME98/bengali/MATPERM.pdf), [Russian](https://www.codechef.com/download/translated/LTIME98/russian/MATPERM.pdf), and [Vietnamese](https://www.codechef.com/download/translated/LTIME98/vietnamese/MATPERM.pdf) as well.There is a grid with $N$ rows and $M$ columns. There are $K$ cannons (numbered $1$ through $K$) placed in $K$ cells of this grid. Each cannon can fire a ball to any cell whose Manhattan distance from the cannon does not exceed the strength of the cannon (including the cell with the cannon). Initially (at the $0$-th second), the strengths of all the cannons are $0$ and they increase by $1$ every second. Starting at the $0$-th second, cannons start throwing balls according to the following rules:- At each second, exactly one cannon fires one ball to a cell which does not contain any balls yet. (Note that at least one such cell exists for each cannon unless the grid is full.)- The same cannon may fire during multiple seconds.- When a ball is fired by a cannon at the $i$-th second, the number $i$ gets printed on the cell the ball lands in.At the end of the $N \cdot M - 1$ th second, the grid will be representing a permutation of the integers $0$ through $N \cdot M - 1$. (Two permutations $P_1$ and $P_2$ are different if at least one cell has different numbers printed on it in $P_1$ and $P_2$.)A permutation is considered to be *good* if it can be formed at the end of the $N \cdot M - 1$th second in the given process.Your task is to find the fraction of permutations that are good, i.e. the number of good permutations divided by the number of all permutations of $0$ through $N \cdot M - 1$. Let's denote this fraction by $P/Q$, where $P$ and $Q$ are positive integers and $Q$ is coprime with $2,500,000,001$. You should compute $P \cdot Q^{-1}$ modulo $2,500,000,001$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $2,500,000,001$.**Note:** The Manhattan distance between a cell in row $r_1$ and column $c_1$ and a cell in row $r_2$ and column $c_2$ is $|r_1-r_2| + |c_1-c_2|$.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>