{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eA toy is made up of N vertices and M undirected edges in the 2D plane. As usual, you want to know how many ways there are to color the vertices of the toy. You have totally C colors. And of course, to make things fun, you think that if one color configuration can be rotated to get another, these two configurations should be considered the same. Rotation means 2D in-plane rotation and reflection is not considered as rotation.\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/746b19d7254ea5fbbf698d58992aa7e6?v\u003d1725623105\"\u003e\u003c/center\u003e\u003cbr\u003eFor instance, consider coloring the following toy with 2 colors. The coordinates of the vertices are:\u003cbr\u003e\u003cbr\u003e 1. (0,0)\u003cbr\u003e 2. (1,0)\u003cbr\u003e 3. (0,1)\u003cbr\u003e 4. (-1,0)\u003cbr\u003e 5. (0,-1)\u003cbr\u003e\u003cbr\u003eThe toy has 6 edges: (1,2), (1,3), (2,3), (3,4), (4,5), (5,2).\u003cbr\u003e\u003cbr\u003eAs a 2D being, this toy has no symmetry. So there are 32 ways to color it. Had the first two edges been removed, there would be only 12 different ways.\u003cbr\u003e\u003cbr\u003eYou should output the answer modulo 10\u003csup\u003e9\u003c/sup\u003e + 7.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer T (T ≤ 20) denoting the number of the test cases.\u003cbr\u003e\u003cbr\u003eEach test case begins with three positive integers N (1 ≤ N ≤ 50), M (0 ≤ M ≤ N (N - 1)/2) and C(1 ≤ C ≤ 100).\u003cbr\u003e\u003cbr\u003eThen follow N lines. Each line contains 2 integers in range [-10000,10000] describing a vertex.\u003cbr\u003e\u003cbr\u003eThen follow M lines. Each line contains 2 integers in range [1,N] representing an edge. There are neither duplicate edges nor self-loops."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line containing the answer."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n5 6 2\r\n0 0\r\n1 0\r\n0 1\r\n-1 0\r\n0 -1\r\n1 2\r\n1 3\r\n2 3\r\n3 4\r\n4 5\r\n5 2\r\n5 4 2\r\n0 0\r\n1 0\r\n0 1\r\n-1 0\r\n0 -1\r\n2 3\r\n3 4\r\n4 5\r\n5 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e32\r\n12\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}