{"raw_statement":[{"iden":"statement","content":"Zayin and Ziyin are playing a game with $n$ piles of stones, where the $i$-th pile has $a_i$ stones for each $1 <= i <= n$. Zayin and Ziyin play in turn, with Zayin going first.\n\nThe one who is unable to remove stones in his turn lose.\n\nCompute the number of strategies Zayin can make in his first turn in order to guarantee a win no matter what choices Ziyin makes.\n\nTwo strategies are considered to be different if they remove a different number of stones or they remove stones from different set of piles.\n\nThe first line contains the number of stone piles $n \" \"(1 <= n <= 10^6)$.\n\nThe second line contains $n$ integers $a_1, a_2, \\\\\\\\cdots, a_n \" \"(1 <= a_i <= 10^9)$ - the number of stones in each pile.\n\nThe only line contains an integer, representing the number of strategies Zayin can make in his first turn modulo $998244353$.\n\n"},{"iden":"input","content":"The first line contains the number of stone piles $n \" \"(1 <= n <= 10^6)$.The second line contains $n$ integers $a_1, a_2, \\\\\\\\cdots, a_n \" \"(1 <= a_i <= 10^9)$ - the number of stones in each pile."},{"iden":"output","content":"The only line contains an integer, representing the number of strategies Zayin can make in his first turn modulo $998244353$."}],"translated_statement":[{"iden":"statement","content":"你被给定一个由 $n$ 个整数组成的序列 $a_1, a_2, dots.h, a_n$。\n\n你需要计算以下三个值：\n\n第一行包含一个整数 $n$ $(1 lt.eq n lt.eq 2 dot.op 10^5)$ —— 序列中元素的个数。\n\n第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ $(-10^9 lt.eq a_i lt.eq 10^9)$ —— 序列的元素。\n\n请输出三个整数，分别为：乘积为负的子段数量、乘积为零的子段数量、乘积为正的子段数量。\n\n在第一个例子中，有六个子段的乘积为负：$(1, 2)$、$(1, 3)$、$(2, 2)$、$(2, 3)$、$(3, 4)$、$(4, 4)$；五个子段的乘积为零：$(1, 5)$、$(2, 5)$、$(3, 5)$、$(4, 5)$、$(5, 5)$；四个子段的乘积为正：$(1, 1)$、$(1, 4)$、$(2, 4)$、$(3, 3)$。\n\n"},{"iden":"input","content":"第一行包含一个整数 $n$ $(1 lt.eq n lt.eq 2 dot.op 10^5)$ —— 序列中元素的个数。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ $(-10^9 lt.eq a_i lt.eq 10^9)$ —— 序列的元素。"},{"iden":"output","content":"请输出三个整数，分别为：乘积为负的子段数量、乘积为零的子段数量、乘积为正的子段数量。"},{"iden":"examples","content":"输入\n5\n5 -3 3 -1 0\n输出\n6 5 4\n\n输入\n10\n4 0 -4 3 1 2 -4 3 0 3\n输出\n12 32 11\n\n输入\n5\n-1 -2 -3 -4 -5\n输出\n9 0 6\n"},{"iden":"note","content":"在第一个例子中，有六个子段的乘积为负：$(1, 2)$、$(1, 3)$、$(2, 2)$、$(2, 3)$、$(3, 4)$、$(4, 4)$；五个子段的乘积为零：$(1, 5)$、$(2, 5)$、$(3, 5)$、$(4, 5)$、$(5, 5)$；四个子段的乘积为正：$(1, 1)$、$(1, 4)$、$(2, 4)$、$(3, 3)$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, P, Q \\in \\mathbb{Z}^+ $ with $ \\gcd(P, Q) = 1 $.  \nLet $ S \\subseteq \\{1, 2, \\dots, N\\} $ be a nonempty subset.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ 1 \\leq P \\leq 10^{10} $  \n3. $ 1 \\leq Q \\leq 10^5 $  \n4. $ \\gcd(P, Q) = 1 $  \n\n**Objective**  \nFind a nonempty subset $ S \\subseteq \\{1, 2, \\dots, N\\} $ such that  \n$$\n\\frac{\\sum_{x \\in S} x}{|S|} = \\frac{P}{Q}\n$$  \nor determine that no such subset exists.  \n\nEquivalently, find $ k \\in \\mathbb{Z}^+ $ and $ s \\in \\mathbb{Z} $ such that:  \n$$\ns = \\frac{P}{Q} \\cdot k \\quad \\text{and} \\quad s \\in \\mathbb{Z}, \\quad k \\leq N, \\quad \\exists S \\subseteq \\{1, \\dots, N\\}, |S| = k, \\sum S = s\n$$","simple_statement":null,"has_page_source":false}