AT_ndpc2026_c 文字列

You are given three strings $ S_1, S_2, S_3 $ , each consisting of lowercase English letters. Find the number of strings $ T $ of length $ N $ (also consisting of lowercase English letters) such that none of $ S_1, S_2, S_3 $ appear as a subsequence of $ T $ . Output the answer modulo $ 998244353 $ .

The input is given from standard input in the following format: > $ N $ $ S_1 $ $ S_2 $ $ S_3 $

Print the number of strings $ T $ of length $ N $ consisting of lowercase English letters such that none of $ S_1, S_2, S_3 $ appear as a subsequence of $ T $ , modulo $ 998244353 $ .

### Sample Explanation 1 There are $ 676 $ strings of length $ 2 $ consisting of lowercase English letters. Among them, $ 1 $ string contains $ S_2 $ = `de`, and $ 51 $ strings contain $ S_3 $ = `f`. These sets do not overlap. Therefore, the answer is $ 676 - 1 - 51 = 624 $ . ### Sample Explanation 2 Note that **subsequence** in the condition is different from **substring**. For example, `accb` contains `ab` as a subsequence, so it does not satisfy the condition. ### Constraints - $ 1 \leq N \leq 10^3 $ - $ S_1, S_2, S_3 $ are non-empty strings of lowercase English letters with length at most $ 10 $ - $ N $ is an integer