E. 击毙你~~~

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

大G 由于常年接触禁忌知识(如向量空间,最小费用最大流,拉普拉斯变换)和不健康的交友环境(比如周围有人私底下一个人偷偷内卷),对 T 这个词语产生了PTSD。

现在某无良教练在 ACM 课堂上给出了 个词语,分别记为 ,与此同时脾气暴躁且大权在握的大G 把所有词语两两配对,将一个词语塞到另一个词语的后面生成一个新的词语,如果拼成的词语的子序列中包含 ,他就会将这个新的词语拉出去枪毙(词语可以和自己配对,并且在词语 和词语 的结合中, 的后面和 的后面是两种情况,如果是词语 和自己配对,那么只会有一种情况)。

大G 想知道自己枪毙了多少个配对出来的新词语。

注意:字符串 的子序列不要求字母连续。

输入格式

第一行一个整数 和一个字符串

接下来 行,每行一个字符串 代表

输出格式

共一行,输出一个数字表示被大G 枪毙的词语数量

样例

样例输入1:

3 bac
abba
bcb
aaca

样例输出1:

3

样例输入2:

5 xx
x
x
x
x
x

样例输出2:

25

样例输入3:

1 y
x

样例输出3:

0

样例输入4:

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

样例输出4:

68

数据范围与提示

数据范围

对于所有数据,满足:

  • 是整数

  • 的长度

  • 所有 的总长度