{"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\"\u003eThere are $n$ stars in the sky. At every moment, the $i$-th of them has a probability of $u_i/v_i(1 \\leq u_i \u0026lt; v_i\u0026lt;P\u003d31607)$ to become visible. All stars are independent of each other. The position of a star can be described as a coordinate on a 2D plane. No two stars share the same coordinate. Your task is to compute the expectation value of the area of the convex hull formed by the visible stars.\u003cbr\u003eFormally, let $P \u003d 31607$. It can be shown that the answer can be expressed as an irreducible fraction $p/q$, where $p$ and $q$ are integers and $q \\not \\equiv 0 \\pmod{P}$. Output the integer equal to $p \\cdot q^{-1} \\bmod P$. In other words, output such an integer $x$ that $0 \\le x \u0026lt; P$ and $x \\cdot q \\equiv p \\pmod{P}$.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a single integer $T$ ($1 \\le T \\le 100$), denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains a single integer $n$$(1 \\le n \\le 1000)$, denoting the number of stars.\u003cbr\u003e\u003cbr\u003eEach of the following $n$ lines describes a stars. The $i$-th line of them contains 4 integers $x_i, y_i, u_i, v_i(-1000 \\le x_i,y_i \\le 1000, 1 \\leq u_i \u0026lt; v_i\u0026lt;P\u003d31607)$ indicating the coordinate of the $i$-th star and the probability of the $i$-th star to become visible. It is guaranteed that no two stars share the same coordinate.\u003cbr\u003e\u003cbr\u003eThere are at most $3$ test cases satisfying $n\u0026gt;20$."}},{"title":"Output","value":{"format":"HTML","content":"Output the integer equal to $p \\cdot q^{-1} \\bmod P$ denoting 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\n4\r\n0 0 1 2\r\n1 0 1 2\r\n0 1 1 2\r\n1 1 1 2\r\n4\r\n0 0 1 2\r\n1 0 1 2\r\n-1 0 1 2\r\n0 1 1 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e21730\r\n21730\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}