Migrated from Lutece 3278 Fairytale Requiem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tags: ACAM，字符串 Hash，数据分治

本题面由 空気力学の詩 友情提供

---

「夏蝉临终前一般的绝唱此起彼伏，化作一片波动的空气一般的大合唱，将我们送别」

「就好像安魂曲一样呢」

「我现在已经，是时候该告别“乐园”了」

「再也不见」

「我在心中悄悄告别道」

在惯例的疯狂的茶会中，爱丽丝给三月兔、帽匠、睡鼠以及作为客人的你提了个如下所示的刁钻的问题。

爱丽丝有 $n$ 种卡片，每种卡片都有无限张，第 $i$ 种卡片上写有一个由小写英文字母构成的字符串 $\textbf{s}_i$。

与此同时她还有一本神奇的魔法书，上面写满了密密麻麻的符号，经过辨认可以确定上面记载的内容为一个由小写英文字母构成的字符串 $T$。

爱丽丝可以从卡片中任意选出两张种类为 $i,j$（允许 $i=j$）的卡片，然后将它们拼接在一起，得到一张写有字符串 $\mathbb{C}_{i,j}=\textbf{s}_i\textbf{s}_j$ 的合成卡片。

定义 $f(\mathbb{C}_{i,j},T)$ 为某张合成卡片 $\mathbb{C}_{i,j}$ 与魔法书 $T$ 的 契合度，其值为字符串 $\mathbb{C}_{i,j}$ 在 $t$ 中出现的次数，例如 $f(\texttt{aa},\texttt{aaabacaa})=3,f(\texttt{aba},\texttt{ababa})=2$。

现在爱丽丝想要知道所有不同的选取方案的 契合度 之和是多少，形式化地，即求出以下式子的值：

$$\sum_{i=1}^n \sum_{j=1}^n f(\textbf{s}_i\textbf{s}_j,T) $$

三月兔、帽匠和睡鼠都被这个问题给难住了，因此只能靠你来解答爱丽丝的问题了。

Input

输入的第一行包括一个字符串 $t$，表示魔法书中记录的字符串。

输出的第二行包括一个正整数 $n$，表示爱丽丝拥有的卡片种类数。

接下来的 $n$ 行每行一个字符串 $\textbf{s}_i$，表示第 $i$ 种卡片上写有的字符串。

Output

输出一个整数，代表所有不同的选取方案的 契合度 之和。

Samples

ababa
3
aba
ab
ba

4

babaaabbaa
10
aa
ba
bba
b
a
a
abb
ba
b
b

105

Constraints

$1\le |t|\le 2\times 10^5,1\le n\le 2\times 10^5,1\le \sum_{i=1}^n |\textbf{s}_i|\le 2\times 10^5$，所有输入的字符串中只包含小写字母。

Resources

2024 UESTC ICPC Training for String