{"raw_statement":[{"iden":"background","content":" > 想回到过去\\\n试着抱你在怀里\\\n羞怯的脸带有一点稚气\\\n想看你看的世界\\\n想在你梦的画面\\\n只要靠在一起就能感觉甜蜜\\\n想回到过去\\\n试着让故事继续\\\n至少不再让你离我而去\\\n分散时间的注意\\\n这次会抱得更紧\\\n这样挽留不知还来不来得及\\\n想回到过去\\\n沉默支撑跃过陌生\\\n静静看着凌晨黄昏\\\n你的身影 失去平衡\\\n慢慢下沉\\\n想回到过去\\\n—— 周杰伦《[回到过去](https://www.bilibili.com/video/BV1fx411N7bU?p=32&vd_source=2f4592e5507d6452d7d44dc098844d6b)》\n>\n\n什么阻碍着两颗心的碰面？什么阻碍着两个人的相见？\n\n或许是令人捉摸不透的时间吧。"},{"iden":"statement","content":"给出 $n,m,t$ 以及 $t$ 个障碍物坐标，求在 $n$ 行 $m$ 列的矩阵中的非障碍位置上放置 $k$ 个两两之间没有公共边的方格的方案有多少种，答案对 $10^9+7$ 取模。"},{"iden":"input","content":"**本题有多组数据。**\n\n第一行一个整数 $T$，表示测试点数量。\n\n接下来 $T$ 个测试点，每个测试点的第一行四个整数 $n,m,k,t$。接下来 $t$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个障碍物的坐标（保证不重叠）。"},{"iden":"output","content":"共 $T$ 行，每行一个整数表示当前询问的答案。"},{"iden":"note","content":"#### 【样例解释 #4】\n\n对于测试点 1，可以画出如下的图：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/9ld7rcxr.png)\n\n其中用黑色格子表示障碍物，可发现只有 $\\{(1,2)(1,4)\\}\\{(1,2)(2,3)\\}\\{(2,2)(1,4)\\}\\{(2,3)(1,4)\\}$ 四种方案满足题意。\n\n对于测试点 2，可以画出如下的图：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/74rbxvs6.png)\n\n可发现只有 $\\{(1,1)(1,3)(2,2)\\}\\{(1,1)(1,3)(2,4)\\}\\{(1,1)(2,2)(2,4)\\}\\{(1,3)(2,1)(2,4)\\}\\{(1,3)(2,2)(2,4)\\}$ 五种情况符合题意。\n\n### 数据点约定\n\n|  数据点编号  |    $n$     |    $m$     |       $k$       |         $t$         |\n| :----------: | :--------: | :--------: | :-------------: | :-----------------: |\n|     $1$      |    $=1$    | $\\le 10^9$ |      $=2$       |        $=0$         |\n|     $2$      |    $=1$    | $\\le 10^9$ |      $=3$       |        $=0$         |\n|     $3$      |  $\\le 20$  |  $\\le 20$  |      $=2$       |        $=0$         |\n|     $4$      |  $\\le 20$  |  $\\le 20$  |      $=3$       |        $=0$         |\n|     $5$      |  $\\le 20$  |  $\\le 20$  |      $=2$       |      $\\le 400$      |\n|     $6$      |  $\\le 20$  |  $\\le 20$  |      $=3$       |      $\\le 400$      |\n|    $7,8$     | $\\le 1000$ | $\\le 1000$ |      $=2$       |        $=0$         |\n|    $9,10$    | $\\le 1000$ | $\\le 1000$ |      $=3$       |        $=0$         |\n|     $11$     | $\\le 1000$ | $\\le 1000$ |      $=2$       |      $\\le 10$       |\n|     $12$     | $\\le 1000$ | $\\le 1000$ |      $=3$       |      $\\le 10$       |\n|   $13,14$    | $\\le 10^9$ |    $=n$    |      $=2$       |        $=0$         |\n|   $15,16$    | $\\le 10^9$ |    $=n$    |      $=3$       |        $=0$         |\n|   $17,18$    | $\\le 10^9$ | $\\le 10^9$ |      $=2$       |        $=0$         |\n|   $19,20$    | $\\le 10^9$ | $\\le 10^9$ |      $=3$       |        $=0$         |\n|   $21,22$    | $\\le 10^9$ | $\\le 10^9$ |      $=2$       | $\\le 2 \\times 10^4$ |\n|   $23,24$    | $\\le 10^9$ | $\\le 10^9$ |      $=3$       | $\\le 2 \\times 10^4$ |\n| $25$ | $\\le 10^9$ | $\\le 10^9$ | $2 \\le k \\le 3$ | $\\le 2 \\times 10^4$ |\n\n对于 $100\\%$ 的数据，$1 \\le n,m \\le 10^9$，$2 \\le k \\le 3$，$0 \\le t \\le \\min(n\\cdot m,2 \\times 10^4)$，$1 \\le x_i \\le n$，$1 \\le y_i \\le m$，$1 \\le T \\le 10$。每个数据点等分值。"}],"translated_statement":null,"sample_group":[["5\n4 3 2 0\n5 7 3 0\n2 2 3 0\n1 8 2 0\n19 13 3 0","49\n4773\n0\n21\n2369219"],["10\n4329 12935 3 0\n125891 5949823 2 0\n95023489 15327384 3 0\n28592394 32891538 2 0\n5894392 52374853 2 0\n58963495 32591238 3 0\n438291538 42819324 3 0\n58493683 234728 2 0\n284952 823499 3 0\n528394298 25892948 3 0","468372138\n510295355\n536959469\n56564283\n462091483\n842203294\n778629925\n806214146\n91259493\n793676806"],["10\n55888076 506356561 3 3\n48940088 192152177\n33004718 365781091\n45088097 31400730\n65004621 206038505 2 3\n50919157 24882066\n50919158 24882064\n50919156 24882067\n249418509 7616530 2 1\n205309921 4639136\n164784593 419325145 3 4\n105814446 200482317\n105814449 200482315\n105814443 200482315\n79723922 206425705\n477366546 180501076 3 4\n39819749 14485585\n39819746 14485582\n39819743 14485588\n39819748 14485585\n84215455 29656489 3 0\n524291275 23244413 3 4\n8149961 10903189\n8149958 10903192\n8149958 10903193\n8149961 10903191\n584987873 823324694 3 1\n540008401 27919189\n25681672 419244427 2 4\n4753299 108169462\n4753301 108169463\n4753298 108169462\n4753298 108169464\n313195991 98402123 3 3\n7016773 83186671\n7016770 83186674\n7016767 83186675","580170965\n521412840\n890711205\n353426094\n41995284\n193113183\n352219667\n748854206\n767819374\n351309432"],["10\n2 4 2 4\n1 1\n1 3\n2 1\n2 4\n2 4 3 3\n1 2\n2 3\n1 4\n1 1 3 0\n3 4 2 0\n3 2 2 1\n1 2\n4 2 3 0\n2 3 2 0\n5 4 3 3\n2 4\n1 3\n1 1\n4 5 2 2\n1 4\n2 1\n3 1 2 0","4\n5\n0\n49\n5\n12\n8\n385\n128\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}