시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 17 13 10 71.429%

문제

Adam and Carol are having a great time playing the Game of Matchings. The game is played on a string S composed of |S| lowercase English letters, s1s2 . . . s|S| . The goal is to find all matchings of a special kind of pattern P in S. The pattern has length N and is defined by a sequence of integers between 1 and 26.

We consider a contiguous substring sisi+1 . . . si+N−1 starting at position i of S a matching of pattern P if there is a mapping from the numbers in P to lowercase English letters such that the pattern is mapped to sisi+1...si+N−1 but no two distinct numbers are mapped to the same letter.

For instance, if S is ”awawww” and P is [10, 21, 10], the matchings of P are the substrings of S of length three starting at positions 1 and 2: ”awa” and ”waw”. Note that ”www” is not an occurence because pattern numbers 10 and 21 would both map to ’w’.

Adam and Carol lost the answer sheet and are not sure if they are finding all occurrences for some of the strings in the game. Given S and P can you find the number of matchings for them?

입력

The first line contains a non-empty string S of at most 5 × 105 characters. Each character of S is a lowercase English letter from ’a’ to ’z’. The second line contains an integer N representing the size of the pattern (1 ≤ N ≤ |S|). The third line contains N integers P1, P2, . . . , PN denoting the pattern (1 ≤ Pi ≤ 26 for i = 1, 2, . . . , N).

출력

Output a line with one integer representing the number of matchings of P found in S.

예제 입력

awawww
3
10 21 10

예제 출력

2

예제 입력 2

abcdefghij
10
1 2 3 4 5 6 7 8 9 1

예제 출력 2

0

예제 입력 3

abbabaabbaababba
4
1 2 2 1

예제 출력 3

5

예제 입력 4

aabcddabccefkkgem
5
10 10 3 14 9

예제 출력 4

4

힌트