Description

题目描述

给你 $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$

输出格式

一个整数

输入输出样例 #1

输入 #1

3 bac
abba
bcb
aaca

输出 #1

3

输入输出样例 #2

输入 #2

5 xx
x
x
x
x
x

输出 #2

25

输入输出样例 #3

输入 #3

1 y
x

输出 #3

0

输入输出样例 #4

输入 #4

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

输出 #4

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$ 。