AT_arc201_c [ARC201C] Prefix Covering

どの文字も `A` または `B` であるような空でない文字列を **AB 文字列**と呼ぶことにします。 AB 文字列からなる集合 $ X $ が次を満たすとき、**良い集合**であるということにします。 - 長さ $ 10^{100} $ であるような AB 文字列は必ずある $ X $ の要素を接頭辞に持つ。 相異なる AB 文字列 $ S_1, S_2, \ldots, S_N $ が与えられます。各 $ k=1,2,\ldots,N $ について、集合 $ \lbrace S_1,S_2,\ldots,S_k\rbrace $ の部分集合であって良い集合であるものの個数を $ 998244353 $ で割った余りを求めて下さい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

$ N $ 行出力して下さい。 $ k $ 行目には、集合 $ \lbrace S_1,S_2,\ldots,S_k\rbrace $ の部分集合であって良い集合であるものの個数を $ 998244353 $ で割った余りを出力して下さい。

### Sample Explanation 1 - $ k=1 $ の場合：良い部分集合はありません。 - $ k=2 $ の場合：良い部分集合は $ \lbrace S_1,S_2\rbrace $ の $ 1 $ 個です。 - $ k=3 $ の場合：良い部分集合は $ \lbrace S_1,S_2\rbrace $ , $ \lbrace S_1,S_2,S_3\rbrace $ の $ 2 $ 個です。 - $ k=4 $ の場合：良い部分集合は $ \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 $ の $ 5 $ 個です。 ### Constraints - $ 1\leq N\leq 2\times 10^5 $ - $ S_1, S_2, \ldots, S_N $ は相異なる AB 文字列 - $ \sum_{1\leq i\leq N}|S_i|\leq 5\times 10^5 $