{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn order to unravel the mystery of their life experience, Nasa and Tsukasa plan to fly to the Moon with the help of spacecrafts from the Earth. When calculating and simulating the flight orbit of the spacecrafts, they assume that the Earth is located at $$$(0,0)$$$ and the Moon is located at $$$(1000,1000)$$$ in the universe.\u003c/p\u003e\u003cp\u003eAlthough the whole journey is so long and difficult, thanks to advanced aerospace technology, there are space stations at all positions with integer coordinates except the Earth and the Moon in the universe. So they can take a break on their long journey and interchange other spacecrafts in these stations.\u003c/p\u003e\u003cp\u003eThere are $$$n$$$ types of brand new spacecrafts in each space station, and the $$$i$$$-th type of spacecrafts can take $$$d_i$$$ units of fuels and always fly towards the Moon for reducing cost. More precisely, they can sail from $$$(x,y)$$$ to $$$(x+dx,y+dy)$$$, where $$$dx$$$ and $$$dy$$$ are non-negative integers and $$$0 \u0026lt; dx^2+dy^2 \\le d_i^2$$$, with the $$$i$$$-th type of spacecrafts.\u003c/p\u003e\u003cp\u003eDuring the journey, they can choose whether to land on some space stations and have a rest. Note that if they choose to take a break in a space station, they will change to a new spacecraft in that space station when they set off.\u003c/p\u003e\u003cp\u003eHowever, recently $$$m$$$ space stations are closed for maintenance, and they cannot stay on these closed stations. Also the spacecrafts in these closed stations are not available, too. Out of concerns about this matter, Nasa is worried whether they could reach the moon successfully.\u003c/p\u003e\u003cp\u003eTherefore, they turn to seek your assistance. You need to help them calculate the number of different ways to fly to the Moon. Since the answer may be too large, you only need to output the answer modulo $$$998\\,244\\,353$$$. Note that two ways are considered different if there exists a stage such that they choose two different types of spacecraft or fly towards two different space stations.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains two integers $$$n$$$ $$$(1 \\le n \\le 1000)$$$ and $$$m$$$ $$$(0 \\le m \\le 1000)$$$, indicating the number of spacecrafts in each space station and the number of closed space stations in the universe.\u003c/p\u003e\u003cp\u003eThen the second line contains $$$n$$$ integers $$$d_1,d_2,\\cdots,d_n$$$ $$$(1 \\le d_i \\le 1000)$$$, indicating the units of fuels that each type of spacecrafts can take.\u003c/p\u003e\u003cp\u003eEach of the following $$$m$$$ lines contain two integers $$$x$$$ and $$$y$$$ $$$(0 \\le x, y \\le 1000)$$$, indicating the space station at $$$(x,y)$$$ is closed. It is guaranteed that the given $$$m$$$ locations are not the same as the locations of the Earth and the Moon and they are pairwise distinct.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput the number of different ways to fly to the Moon modulo $$$998\\,244\\,353$$$.\u003c/p\u003e"}},{"title":"Examples","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 0\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e472799582\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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 1\n1\n500 500\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e447362327\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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 0\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e277036758\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eFor the first sample case, the answer is $$$\\binom{2000}{1000}$$$.\u003c/p\u003e\u003cp\u003eFor the second sample case, the answer is $$$\\binom{2000}{1000}-\\binom{1000}{500}^2$$$.\u003c/p\u003e\u003cp\u003eNote that $$$\\binom{n}{k}$$$ is a binomial coefficient, which gives the number of $$$k$$$-element subsets of an $$$n$$$-element set.\u003c/p\u003e"}}]}