{"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\"\u003eNow you have a stack and $n$ numbers $1,2,3,…,n$. These $n$ numbers are pushed in the order and popped if the number is at the top of the stack. You can read the sample to get more details.\u003cbr\u003eThis question is quite easy. Therefore I must give you some limits.\u003cbr\u003eThere are $m$ limits, each is expressed as a pair$\u0026lt;A,B\u0026gt;$ means the number $A$ must be popped before $B$.\u003cbr\u003eCould you tell me the number of ways that are legal in these limits?\u003cbr\u003eI know the answer may be so large, so you can just tell me the answer mod $1000000007({10}^{9}+7)$.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $T$(about 5),indicating the number of cases.\u003cbr\u003eEach test case begins with two integers $n(1 \\leq n \\leq 300)$ and $m(1 \\leq m \\leq 90000)$.\u003cbr\u003eNext $m$ lines contains two integers $A$ and $B(1 \\leq A \\leq n,1 \\leq B \\leq n)$\u003cbr\u003e(P.S. there may be the same limits or contradict limits.)"}},{"title":"Output","value":{"format":"HTML","content":"For each case, output an integer means the answer mod $1000000007$."}},{"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\u003e5\r\n1 0\r\n5 0\r\n3 2\r\n1 2\r\n2 3\r\n3 2\r\n2 1\r\n2 3\r\n3 3\r\n1 2\r\n2 3\r\n3 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n42\r\n1\r\n2\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"The only legal pop-sequence of case 3 is 1,2,3.\u003cbr\u003eThe legal pop-sequences of case 4 are 2,3,1 and 2,1,3."}}]}