AT_abc324_e [ABC324E] Joint Two Strings

给定 $N$ 个仅由小写英文字母组成的字符串 $S_1,\ S_2,\ \ldots,\ S_N$，以及一个仅由小写英文字母组成的字符串 $T$。 共有 $N^2$ 个由 $1$ 到 $N$ 之间的两个整数组成的有序对 $(i,\ j)$，请输出其中满足以下条件的有序对的个数： - 将 $S_i$ 和 $S_j$ 按顺序连接得到的字符串包含 $T$ 作为（不要求连续的）子序列。

输入以如下格式从标准输入读入。 > $N$ $T$ $S_1$ $S_2$ $\vdots$ $S_N$

请输出答案。

## 限制条件 - $N$ 是整数。 - $1 \leq N \leq 5 \times 10^5$。 - $S_i$ 和 $T$ 均为长度在 $1$ 到 $5 \times 10^5$ 之间的仅由小写英文字母组成的字符串。 - $S_1,\ S_2,\ \ldots,\ S_N$ 的总长度不超过 $5 \times 10^5$。 ## 样例解释 1 满足题目条件的有序对 $(i,\ j)$ 有以下 $3$ 个：$(1,\ 2),\ (1,\ 3),\ (2,\ 3)$。 - 对于 $(i,\ j) = (1,\ 2)$，将 $S_1$ 和 $S_2$ 按顺序连接得到的字符串 `abbabcb` 包含 `bac` 作为子序列。 - 对于 $(i,\ j) = (1,\ 3)$，将 $S_1$ 和 $S_3$ 按顺序连接得到的字符串 `abbaaaca` 包含 `bac` 作为子序列。 - 对于 $(i,\ j) = (2,\ 3)$，将 $S_2$ 和 $S_3$ 按顺序连接得到的字符串 `bcbaaca` 包含 `bac` 作为子序列。 由 ChatGPT 4.1 翻译