{"raw_statement":[{"iden":"problem statement","content":"A non-empty string where every character is `A` or `B` is called an **AB string**.\nA set $X$ consisting of AB strings is called a **good set** when it satisfies the following:\n\n*   Every AB string of length $10^{100}$ has some element of $X$ as a prefix.\n\nYou are given distinct AB strings $S_1, S_2, \\ldots, S_N$. For each $k=1,2,\\ldots,N$, find the number, modulo $998244353$, of subsets of the set $\\lbrace S_1,S_2,\\ldots,S_k\\rbrace$ that are good sets."},{"iden":"constraints","content":"*   $1\\leq N\\leq 2\\times 10^5$\n*   $S_1, S_2, \\ldots, S_N$ are distinct AB strings.\n*   $\\sum_{1\\leq i\\leq N}|S_i|\\leq 5\\times 10^5$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$"},{"iden":"sample input 1","content":"6\nA\nB\nBA\nBB\nAA\nAB"},{"iden":"sample output 1","content":"0\n1\n2\n5\n10\n25\n\n*   For $k=1$: There are no good subsets.\n*   For $k=2$: There is $1$ good subset: $\\lbrace S_1,S_2\\rbrace$.\n*   For $k=3$: There are $2$ good subsets: $\\lbrace S_1,S_2\\rbrace$, $\\lbrace S_1,S_2,S_3\\rbrace$.\n*   For $k=4$: There are $5$ good subsets: $\\lbrace S_1,S_2\\rbrace$, $\\lbrace S_1,S_2,S_3\\rbrace$, $\\lbrace S_1,S_2,S_4\\rbrace$, $\\lbrace S_1,S_3,S_4\\rbrace$, $\\lbrace S_1,S_2,S_3,S_4\\rbrace$."},{"iden":"sample input 2","content":"10\nA\nB\nAABA\nAABB\nAB\nAA\nAAA\nBB\nAAB\nBA"},{"iden":"sample output 2","content":"0\n1\n2\n4\n8\n20\n41\n82\n170\n425"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}