AT_ndpc2026_c 文字列

英小文字からなる $ 3 $ 個の文字列 $ S_1, S_2, S_3 $ が与えられます。 長さ $ N $ の英小文字からなる文字列 $ T $ であって $ S_1, S_2, S_3 $ のいずれも部分列として含まないものの個数を $ 998244353 $ で割った余りを求めてください。

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

長さ $ N $ の英小文字からなる文字列 $ T $ であって $ S_1, S_2, S_3 $ のいずれも部分列として含まないものの個数を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 長さ $ 2 $ の英小文字からなる文字列は $ 676 $ 個あり、そのうち $ S_2 $ = `de` を含む文字列は $ 1 $ 個、 $ S_3 $ = `f` を含む文字列は $ 51 $ 個で、両者は排反です。よって、 $ 676 - 1 - 51 = 624 $ 個が答えとなります。 ### Sample Explanation 2 条件にある「部分列」は「部分文字列」とは異なる点に注意してください。例えば `accb` は部分列として `ab` を含んでいるため条件を満たしません。 ### Constraints - $ 1 \leq N \leq 10^3 $ - $ S_1, S_2, S_3 $ は長さ $ 10 $ 以下の英小文字からなる空でない文字列 - $ N $ は整数