{"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\"\u003eA delta wave is a high amplitude brain wave in humans with a frequency of 1 – 4 hertz which can be recorded with an electroencephalogram (EEG) and is usually associated with slow-wave sleep (SWS).\u003cbr\u003e-- from Wikipedia\u003cbr\u003e\u003cbr\u003eThe researchers have discovered a new kind of species called \"otaku\", whose brain waves are rather strange. The delta wave of an otaku\u0027s brain can be approximated by a polygonal line in the 2D coordinate system. The line is a route from point (0, 0) to (N, 0), and it is allowed to move only to the right (up, down or straight) at every step. And during the whole moving, it is not allowed to dip below the y \u003d 0 axis.\u003cbr\u003e\u003cbr\u003eFor example, there are the 9 kinds of delta waves for N \u003d 4:\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/8184c3022d27e69631b15f35c77b9d26?v\u003d1719354908\"\u003e\u003c/center\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003eGiven N, you are requested to find out how many kinds of different delta waves of otaku.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are no more than 20 test cases. There is only one line for each case, containing an integer N (2 \u0026lt; N \u0026lt;\u003d 10000)\u003cbr\u003e\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Output one line for each test case. For the answer may be quite huge, you need only output the answer module 10\u003csup\u003e100\u003c/sup\u003e."}},{"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\u003e3\r\n4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n9\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}