AT_arc201_c [ARC201C] Prefix Covering

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 length $ 10^{100} $ has some element of $ X $ as a prefix. You 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.

The input is given from Standard Input in the following format: > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

Output $ N $ lines. The $ k $ -th line should contain the number, modulo $ 998244353 $ , of subsets of the set $ \lbrace S_1,S_2,\ldots,S_k\rbrace $ that are good sets.

### Sample Explanation 1 - For $ k=1 $ : There are no good subsets. - For $ k=2 $ : There is $ 1 $ good subset: $ \lbrace S_1,S_2\rbrace $ . - For $ k=3 $ : There are $ 2 $ good subsets: $ \lbrace S_1,S_2\rbrace $ , $ \lbrace S_1,S_2,S_3\rbrace $ . - 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 $ . ### Constraints - $ 1\leq N\leq 2\times 10^5 $ - $ S_1, S_2, \ldots, S_N $ are distinct AB strings. - $ \sum_{1\leq i\leq N}|S_i|\leq 5\times 10^5 $