{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\r\n\u003cp\u003eNiwango-kun has \\(N\\) chickens as his pets. The chickens are identified by numbers \\(1\\) to \\(N\\), and the size of the \\(i\\)-th chicken is a positive integer \\(a_i\\).\u003c/p\u003e\r\n\u003cp\u003e\\(N\\) chickens decided to take each other\u0027s hand (wing) and form some cycles. The way to make cycles is represented by a permutation \\(p\\) of \\(1, \\ldots , N\\). Chicken \\(i\\) takes chicken \\(p_i\\)\u0027s left hand by its right hand. Chickens may take their own hand.\u003c/p\u003e\r\n\u003cp\u003eLet us define the \u003cem\u003ecycle\u003c/em\u003e containing chicken \\(i\\) as the set consisting of chickens \\(p_i, p_{p_i}, \\ldots, p_{\\ddots_i} \u003d i\\). It can be proven that after each chicken takes some chicken\u0027s hand, the \\(N\\) chickens can be decomposed into cycles.\u003c/p\u003e\r\n\u003cp\u003eThe \u003cem\u003ebeauty\u003c/em\u003e \\(f(p)\\) of a way of forming cycles is defined as the product of the size of the smallest chicken in each cycle.\r\nLet \\(b_i \\ (1 \\leq i \\leq N)\\) be the sum of \\(f(p)\\) among all possible permutations \\(p\\) for which \\(i\\) cycles are formed in the procedure above.\u003c/p\u003e\r\n\u003cp\u003eFind the greatest common divisor of \\(b_1, b_2, \\ldots, b_N\\) and print it \\({\\rm mod} \\ 998244353\\).\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Constraints","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e\\(1 \\leq N \\leq 10^5\\)\u003c/li\u003e\r\n\u003cli\u003e\\(1 \\leq a_i \\leq 10^9\\)\u003c/li\u003e\r\n\u003cli\u003eAll numbers given in input are integers\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Input","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\r\n\u003cp\u003eInput is given from Standard Input in the following format:\u003c/p\u003e\r\n\u003cpre\u003e\\(N\\)\r\n\\(a_1\\) \\(a_2\\) \\(\\ldots\\) \\(a_N\\)\r\n\u003c/pre\u003e\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Output","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\r\n\u003cp\u003ePrint the answer.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 1","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\r\n4 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\r\n\u003cp\u003eIn this case, \\(N \u003d 2, a \u003d [ 4, 3 ]\\).\u003c/p\u003e\r\n\u003cp\u003eFor the permutation \\(p \u003d [ 1, 2 ]\\), a cycle of an only chicken \\(1\\) and a cycle of an only chicken \\(2\\) are made, thus \\(f([1, 2]) \u003d a_1 \\times a_2 \u003d 12\\).\u003c/p\u003e\r\n\u003cp\u003eFor the permutation \\(p \u003d [ 2, 1 ]\\), a cycle of two chickens \\(1\\) and \\(2\\) is made, and the size of the smallest chicken is \\(a_2 \u003d 3\\), thus \\(f([2, 1]) \u003d a_2 \u003d 3\\).\u003c/p\u003e\r\n\u003cp\u003eNow we know \\(b_1 \u003d f([2, 1]) \u003d 3, b_2 \u003d f([1, 2]) \u003d 12\\), and the greatest common divisor of \\(b_1\\) and \\(b_2\\) is \\(3\\).\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 2","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\r\n2 5 2 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\r\n\u003cp\u003eThere are always \\(N!\\) permutations because chickens of the same size can be distinguished from each other.\u003c/p\u003e\r\n\u003cp\u003eThe following picture illustrates the cycles formed and their beauties when \\(p \u003d (2, 1, 4, 3)\\) and \\(p \u003d (3, 4, 1, 2)\\), respectively.\r\n\u003c/p\u003e\u003cdiv style\u003d\"text-align: center;\"\u003e\r\n\u003cimg alt\u003d\"bdd8ce0a7db3b4f920b04551c60aa207.png\" src\u003d\"CDN_BASE_URL/b160bc7b886aa74408baec8d0b1c062b?v\u003d1715950815\"\u003e\r\n\u003c/div\u003e\u003cp\u003e\u003c/p\u003e\u003c/section\u003e\r\n"}}]}