Find Number of Compatible Substrings

Given a history string and several product strings of equal length, count the starting positions of contiguous substrings that can be formed by concatenating all product strings, each used once, in any order. Duplicate products are used as many times as they appear, and overlapping positions are counted separately.

输入格式

The first line contains history, the second line the number of products p, followed by p lines of product strings. This site uses lowercase strings, 1≤|history|≤100000, 1≤p≤10000, product length 1..30 with all products of equal length, and total product length ≤100000.

输出格式

Output a single integer, the answer.

样例 1

输入：

abcdefdefabcghidefabcxyz
3
abc
def
ghi

输出：

3

样例 2

输入：

aaaa
2
a
a

输出：

3

样例 3

输入：

abb
2
ab
ab

输出：

0

样例说明

The answers are 3, 3 and 0.