{"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 K pieces on the chessboard.\u003cbr\u003e\u003cbr\u003eThe size of the chessboard is N*N.\u003cbr\u003e\u003cbr\u003eThe pieces are initially placed on the top cells of the board.\u003cbr\u003e\u003cbr\u003eA piece located on (r, c) can be moved by one cell right to (r, c + 1) or one cell down to (r+1, c).\u003cbr\u003e\u003cbr\u003eYour task is to count how many different ways to move all pieces to the given positions at the bottom of the board.\u003cbr\u003e\u003cbr\u003eFurthermore, the paths of the pieces mustn’t intersect each other.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of input contains an integer T-the number of test cases.\u003cbr\u003e\u003cbr\u003eEach test case begins with a line containing two integers-N(1\u0026lt;\u003dN\u0026lt;\u003d100000) and K(1\u0026lt;\u003dK\u0026lt;\u003d100) representing the size of the chessboard and the number of pieces respectively.\u003cbr\u003e\u003cbr\u003eThe second line contains K integers: 1\u0026lt;\u003da1\u0026lt;a2\u0026lt; …\u0026lt;aK\u0026lt;\u003dN representing the initial positions of the pieces. That is, the pieces are located at (1, a1), (1, a2), …, (1, aK).\u003cbr\u003e\u003cbr\u003eNext line contains K integers: 1\u0026lt;\u003db1\u0026lt;b2\u0026lt;…\u0026lt;bK\u0026lt;\u003dN representing the final positions of the pieces. This means the pieces should be moved to (N, b1), (N, b2), …, (N, bK).\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Print consecutive T lines, each of which represents the number of different ways modulo 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\u003e1\r\n5 2\r\n1 2\r\n3 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e50\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}