飞天德（Darkwing Duck）又遇到麻烦了！他一回到自己的小镇，就听说反派 Negaduck 正在袭击这里。作为一个合格的恶棍，Negaduck 计划抢劫一组连续排列的建筑物，然后带着赃物逃跑。

小镇的全景可以用一个字符串 $s$ 表示，其中每个字符代表对应建筑物的形状。不同的建筑物可能具有相同的形状，因此在字符串中用相同的字符表示。Negaduck 选择了一个字符串 $p$ 作为他的抢劫计划。幸运的是，警方已经得知了这个字符串 $p$。现在他们想要找出所有处于危险之中的建筑物，但在此过程中遇到了一个难题。

根据新市长的命令，小镇上的一些建筑物将被拆除。它们将按照在字符串 $s$ 中出现的顺序（从左到右）依次被拆除。这个拆除计划在城市里是众所周知的。

抢劫可以在任何时间发生：在所有计划的拆除之前、在所有拆除之后，或者在拆除计划中任意两个相邻建筑物的拆除之间。然而，在抢劫过程中不能发生任何拆除。

Negaduck 严格按照他的抢劫计划从左到右抢劫建筑物。除了已被拆除的建筑物外，他不会跳过任何建筑物。他只能执行完整的计划。尽管如此，仍然可能存在许多处于被抢劫危险中的建筑物子集。

正式地，考虑通过从 $s$ 中移除对应于已拆除建筑物的字符而得到的字符串 $t$。请注意，字符串 $t$ 最初等于 $s$，但在每次拆除后都会发生变化。如果存在某个时刻，一个建筑物子集在 $t$ 中构成一个子串，且该子串等于字符串 $p$，则 Negaduck 可以抢劫该建筑物子集。

你的任务是求出处于被抢劫危险中的建筑物子集的精确数量。

输入格式

输入的第一行包含一个非空字符串 $s$，由英文大小写字母、数字以及字符 ,、!、_、. 和 - 组成，代表小镇从左到右的建筑物。该字符串的长度不超过 $1\,000\,000$。

输入的第二行包含一个字符串 $p$，由英文大小写字母、数字以及字符 ,、!、_、. 和 - 组成，代表 Negaduck 从左到右的计划。该字符串的长度不超过 $1\,000\,000$。

注意，英文大小写字母被视为不同的字符。

输入的第三行包含一个整数 $m$（$0 \le m \le |s|$），表示市长拆除计划的长度。

第四行包含一个递增的整数序列 $x_1, x_2, \dots, x_m$（$1 \le x_1 < x_2 < \dots < x_m \le |s|$），表示按拆除顺序排列的建筑物下标（基于 1 的索引）。

输出格式

输出一个整数：根据 Negaduck 的计划，可能被抢劫的不同建筑物子集的数量。

样例

输入样例 1

aabbcc
abc
3
2 4 5

输出样例 1

2

说明

对于给定的样例，答案为 $2$，因为以下可能的建筑物序列可能会被抢劫：

• $1, 3, 5$（在拆除两个建筑物之后）
• $1, 3, 6$（在拆除所有三个建筑物之后）