题目描述

给定三个字符串 $S_1, S_2, S_3$，每个字符串均由小写英文字母组成。请你计算有多少个长度为 $N$ 的字符串 $T$（同样仅由小写英文字母组成），使得 $S_1, S_2, S_3$ 都不会作为 $T$ 的子序列出现。请将结果对 $998244353$ 取模后输出。

输入格式

第一行输入一个整数 $N$

第二行输入三个字符串 $S_1$ $S_2$ $S_3$

输出格式

输出一个整数，表示长度为 $N$ 的，仅由小写英文字母组成，且 $S_1, S_2, S_3$ 都不会作为子序列出现的字符串 $T$ 的数量，对 $998244353$ 取模。

2
abc de f

624

4
ab ab ab

453125

1000
atcoder algorithm lectures

669410767

提示

样例 1 解释

共有 $676$ 个长度为 $2$ 的字符串，由小写英文字母组成。其中有 $1$ 个字符串包含 $S_2 = \texttt{de}$，有 $51$ 个字符串包含 $S_3 = \texttt{f}$。这两类字符串不会相互重叠。因此答案为 $676 - 1 - 51 = 624$。

数据范围

• 对于 $20\%$ 的数据满足：$1 \leq N \leq 3$。
• 对于 $40\%$ 的数据满足：$|S_1|=|S_2|=|S_3|=1$。
• 对于 $100\%$ 的数据满足：$1 \leq N \leq 10^3$。

对于所有的数据保证 $S_1, S_2, S_3$ 是非空字符串，由小写英文字母组成，长度不超过 $10$