{"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":"\u003cp\u003eFor her excellent performance, pianist Chevonne was awarded a pearl necklace. The necklace consisted of $$$n$$$ pearls which form a circle and are numbered $$$1, 2, \\cdots, n$$$ clockwise. \u003c/p\u003e\u003cp\u003eTo prevent the pearls from being covered with dust, she wants to move pearls from the necklace and wipe them. However, the way to remove the pearls is complex because of their uniqueness of them.\u003c/p\u003e\u003cp\u003eSpecifically, every pearl on the necklace has a continuity value $$$c_i ~ (c_i \\geq 0)$$$. Each turn, Chevonne can choose a pearl $$$i$$$ with $$$c_i \\geq 1$$$ and move the pearl $$$i$$$ and $$$c_i - 1$$$ clockwise consecutive pearls ($$$c_i$$$ pearls in all). Be careful! If the number of remaining pearls is \u003cspan class\u003d\"tex-font-style-bf\"\u003eless than\u003c/span\u003e $$$c_i$$$, she will be unable to choose pearl $$$i$$$. After that, the remaining pearls will form a new circle.\u003c/p\u003e\u003cp\u003eChevonne will repeat the process till she can\u0027t remove any pearls or all the pearls have been removed. She is curious about the maximum number of pearls she could remove and the number of such solutions. \u003c/p\u003e\u003cp\u003eHere, we use a set to describe a solution. The set contains the number $$$i$$$ if Chevonne chose pearl $$$i$$$ in some step. Two solutions are different if and only if the sets are different.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains one positive integer $$$n~(1 \\leq n \\leq 2000)$$$.\u003c/p\u003e\u003cp\u003eThe following one line contains $$$n$$$ non-negative integers separated by spaces. The $$$i$$$-th number represents $$$c_i~(0 \\leq c_i \\leq 2000)$$$. Pearls are numbered clockwise from $$$1$$$ to $$$n$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePlease output two integers separated by one space.\u003c/p\u003e\u003cp\u003eThe first one is the maximum number of pearls Chevonne could remove and the second one is the number of such solutions. Since the number of solutions may be very large, please output it modular $$$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\u003e6\n0 1 1 3 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6 3\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 example, all the pearls could be removed by Chevonne, the $$$3$$$ possible solutions are shown as follows: \u003c/p\u003e\u003col\u003e \u003cli\u003e remove the $$$2, 3, 6, 4$$$-th pearl in order. \u003c/li\u003e\u003cli\u003e remove the $$$2, 3, 6, 5$$$-th pearl in order. \u003c/li\u003e\u003cli\u003e remove the $$$5, 4$$$-th pearl in order. \u003c/li\u003e\u003c/ol\u003e"}}]}