{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"epigraph\"\u003e\u003cdiv class\u003d\"epigraph-text\"\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eIn every real man a child is hidden that wants to play.\u003c/span\u003e\u003c/div\u003e\u003cdiv class\u003d\"epigraph-source\"\u003eā Friedrich Nietzsche, \u003cspan class\u003d\"tex-font-style-it\"\u003eThus Spoke Zarathustra\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cp\u003eOn a day that could not be more ordinary, \u003cspan class\u003d\"tex-font-style-it\"\u003eKP\u003c/span\u003e unexpectedly received an anonymous birthday gift ā an aeroplane chess!\u003c/p\u003e\u003cp\u003eThe gift evoked memories of his childhood, but after several hours of playing, he had a doubt:\u003c/p\u003e\u003cp\u003eDuring the \u003cspan class\u003d\"tex-font-style-it\"\u003eHome Zone Backtrack\u003c/span\u003e, if the chess is on the $$$i$$$-th cell, what is the expected number of rolls required to reach the end?\u003c/p\u003e\u003cp\u003eFormally, assume that the chess is placed on an axis, where the point $$$\\mathtt{0}$$$ denotes the end.\u003c/p\u003e\u003cp\u003eDuring one operation, you will randomly choose a number $$$y$$$ $$$(1 \\leq y \\leq n)$$$. Assume that the point of the chess is $$$x$$$:\u003c/p\u003e\u003cul\u003e \u003cli\u003e if $$$y \u0026lt; x$$$, then $$$x :\u003d x - y$$$; \u003c/li\u003e\u003cli\u003e if $$$y \u0026gt; x$$$, then $$$x:\u003d y - x$$$; \u003c/li\u003e\u003cli\u003e Otherwise, the game ends. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eNow you need to process $$$q$$$ queries, each query consists of a single integer $$$x$$$, denoting the point of the chess.\u003c/p\u003e\u003cp\u003eFor each query, you need to output the expected number of operations needed to reach the end of the game.\u003c/p\u003e\u003cp\u003eIt can be shown that the answer can be represented as $$$P / Q$$$, where $$$P$$$, $$$Q$$$ are coprime integers and $$$Q \\not \\equiv 0 \\pmod {998244353}$$$. Print the value of $$$P \\times Q^{-1} \\pmod {998244353}$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n$$$, $$$q$$$ $$$(1 \\leq n \\leq 500, 1 \\leq q \\leq 2 \\times 10 ^ 5)$$$.\u003c/p\u003e\u003cp\u003eThe $$$i$$$-th of the next $$$q$$$ lines contains a single integer $$$x$$$ $$$(1 \\leq x \\leq 10 ^ 6)$$$, denoting the point of the chess.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each query, output a single integer, denoting the answer to the query modulo $$$998244353$$$.\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\u003e2 2\n1\n114514\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n64376993\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\u003eIn the first test case, the chess is on point $$$\\mathtt{1}$$$, and the following will happen:\u003c/p\u003e\u003col\u003e \u003cli\u003e You randomly choose $$$1$$$ for possibility $$$\\frac{1}{2}$$$. After that, $$$1 \u003d x$$$, and you reach the end. \u003c/li\u003e\u003cli\u003e You randomly choose $$$2$$$ for possibility $$$\\frac{1}{2}$$$. After that, $$$2 \u0026gt; x$$$, so $$$x :\u003d 2 - x \u003d 1$$$. Then you randomly choose $$$1$$$ for possibility $$$\\frac{1}{2}$$$. After that, $$$1 \u003d x$$$, and you reach the end. \u003c/li\u003e\u003cli\u003e ... \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eIt can be shown that the expected number of operations to reach the end equals:\u003c/p\u003e\u003cp\u003e$$$\\displaystyle E \u003d 1 \\times \\frac{1}{2} + 2 \\times \\frac{1}{2^2} + 3 \\times \\frac{1}{2^3} + \\ldots \u003d 2.$$$\u003c/p\u003e\u003cp\u003eIn the second test case, note that you need to print the answer modulo $$$998244353$$$.\u003c/p\u003e"}}]}