{"problem":{"name":"Prefix Covering","description":{"content":"A non-empty string where every character is `A` or `B` is called an **AB string**. A set $X$ consisting of AB strings is called a **good set** when it satisfies the following: *   Every AB string of ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc201_c"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc201_c","tags":[],"sample_group":[["6\nA\nB\nBA\nBB\nAA\nAB","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$."],["10\nA\nB\nAABA\nAABB\nAB\nAA\nAAA\nBB\nAAB\nBA","0\n1\n2\n4\n8\n20\n41\n82\n170\n425"]],"created_at":"2026-03-03 11:01:14"}}