该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你 $N$ 个由小写英文字母组成的字符串 $S_1, S_2, \ldots, S_N$ 和一个由小写英文字母组成的字符串 $T$ 。

在 $1$ 和 $N$ 之间有 $N^2$ 对 $(i, j)$ 整数。请打印其中满足以下条件的整数对的数目。

• 按此顺序排列的 $S_i$ 和 $S_j$ 的连接包含 $T$ 作为(不一定连续的)子序列。

输入格式

第一行输入变量$N$和字符串$T$，空格隔开

接下来$N$行，每行一个字符串$S_i$

输出格式

一个整数

3 bac
abba
bcb
aaca

3

5 xx
x
x
x
x
x

25

1 y
x

0

10 ms
mkgn
m
hlms
vmsle
mxsm
nnzdhi
umsavxlb
ffnsybomr
yvmm
naouel

68

说明/提示

对于 $20\%$ 的数据，$1\le N\le100$，字符串长度$\le 100$。

对于$100\%$的数据，$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$ 。