[COCI2011-2012#5] POPLOČAVANJE

注意：本题相对于原题缩小了空间限制，需要一些小技巧才能通过。

有一条由 $N$ 个英文小写字母组成的街道，市政府偶尔会更换街道上的瓷砖。但是，字母瓷砖的需求量很大，所以政府只有 $M$ 种字母瓷砖可供选择。 第 $i$ 个瓦片图案由 $L_{i}$ 个字母组成。瓷砖不能旋转，也不能打碎，而且只能放置在瓷砖字母与街道上连续的字母子序列重合的地方。 瓷砖可以重叠，且可以使用相同图案的多块瓷砖。如果一个街道不能被任何瓷砖覆盖，那么他就是不好的。 求有多少个不好的街道。

第一行，一个整数 $N$，表示街道上的字母数。 第二行有 $N$ 个小写字母，表示街道上的序列，由小写字母组成。 第三行，一个整数 $M$，表示瓷砖数量。 接着 $M$ 行，每行 $L_{i}$ 个小写字母，表示该瓷砖的图案。

一行，一个整数，表示方案数。

6
abcbab
2
cb
cbab

2

4
abab
2
bac
baba

4

6
abcabc
2
abca
cab

1

$1\le N\le 3\times 10^{5}$，$1\le M\le 5\times 10^{3}$，$1\le L_{i}\le 5\times 10^{3}$。 题目译自 [COCI 2011/2012 #5 T6](https://hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf)。