{"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\u003eThe Floral Clock has been standing by the side of Mirror Lake for years. Though unable to keep time, it reminds people of the passage of time and the good old days.\u003c/p\u003e\u003cp\u003eOn the rim of the Floral Clock are \u003cspan class\u003d\"tex-span\"\u003e2\u003ci\u003en\u003c/i\u003e\u003c/span\u003e flowers, numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e2\u003ci\u003en\u003c/i\u003e\u003c/span\u003e clockwise, each of which has a colour among all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e possible ones. For each colour, there are exactly two flowers with it, the \u003cspan class\u003d\"tex-font-style-underline\"\u003edistance\u003c/span\u003e between which \u003cspan class\u003d\"tex-font-style-bf\"\u003eeither is less than or equal to \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e, or equals \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e\u003c/span\u003e. Additionally, if flowers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e are of the same colour, then flowers opposite to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and opposite to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e should be of the same colour as well — symmetry is beautiful!\u003c/p\u003e\u003cp\u003eFormally, the \u003cspan class\u003d\"tex-font-style-underline\"\u003edistance\u003c/span\u003e between two flowers is \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e plus the number of flowers on the minor arc (or semicircle) between them. Below is a possible arrangement with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e \u003d 6\u003c/span\u003e that cover all possibilities.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/332846704e7f78ad03c6bacd417c41f3?v\u003d1715275973\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eThe \u003cspan class\u003d\"tex-font-style-underline\"\u003ebeauty\u003c/span\u003e of an arrangement is defined to be the product of the lengths of flower segments separated by all opposite flowers of the same colour. In other words, in order to compute the beauty, we remove from the circle all flowers that have the same colour as flowers opposite to them. Then, the beauty is the product of lengths of all remaining segments. Note that we include segments of length \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e in this product. If there are no flowers that have the same colour as flower opposite to them, the beauty equals \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e. For instance, the \u003cspan class\u003d\"tex-font-style-underline\"\u003ebeauty\u003c/span\u003e of the above arrangement equals \u003cspan class\u003d\"tex-span\"\u003e1 × 3 × 1 × 3 \u003d 9\u003c/span\u003e — the segments are \u003cspan class\u003d\"tex-span\"\u003e{2}\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e{4, 5, 6}\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e{8}\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e{10, 11, 12}\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eWhile keeping the constraints satisfied, there may be lots of different arrangements. Find out the sum of \u003cspan class\u003d\"tex-font-style-underline\"\u003ebeauty\u003c/span\u003e over all possible arrangements, modulo \u003cspan class\u003d\"tex-span\"\u003e998 244 353\u003c/span\u003e. Two arrangements are considered different, if a pair \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003eu\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e)\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eu\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e ≤ 2\u003ci\u003en\u003c/i\u003e\u003c/span\u003e) exists such that flowers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e are of the same colour in one of them, but not in the other.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first and only line of input contains a lonely positive integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e3 ≤ \u003ci\u003en\u003c/i\u003e ≤ 50 000\u003c/span\u003e)\u0026nbsp;— the number of colours present on the Floral Clock.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput one integer — the sum of \u003cspan class\u003d\"tex-font-style-underline\"\u003ebeauty\u003c/span\u003e over all possible arrangements of flowers, modulo \u003cspan class\u003d\"tex-span\"\u003e998 244 353\u003c/span\u003e.\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\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e24\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\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\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\u003e7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1316\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\u003e15\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3436404\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\u003eWith \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e \u003d 3\u003c/span\u003e, the following six arrangements each have a \u003cspan class\u003d\"tex-font-style-underline\"\u003ebeauty\u003c/span\u003e of \u003cspan class\u003d\"tex-span\"\u003e2 × 2 \u003d 4\u003c/span\u003e.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/87c8f0ae9921f255b199d4d3d87bebc1?v\u003d1715275973\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eWhile many others, such as the left one in the figure below, have a \u003cspan class\u003d\"tex-font-style-underline\"\u003ebeauty\u003c/span\u003e of \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e. The right one is invalid, since it\u0027s asymmetric.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/7cf2121b4c63d0b1afa3092f54ca080f?v\u003d1715275973\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e"}}]}