DNA 비밀번호

평소 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 등장하는 문자가 'A', 'C', 'G', 'T' 네 가지뿐인 문자열이다. 예를 들어 "ACKA"는 DNA 문자열이 아니지만 "ACCA"는 DNA 문자열이다. 이 문자열에 완전히 매료된 민호는 DNA 문자열을 하나 만들고, 그 문자열의 부분문자열을 비밀번호로 쓰기로 마음먹었다.

하지만 민호는 이 방법에 큰 문제가 있다는 것을 발견했다. 부분문자열을 아무렇게나 뽑으면 "AAAA"처럼 보안에 취약한 비밀번호가 만들어질 수 있기 때문이다. 그래서 민호는 부분문자열에 각 문자가 정해진 개수 이상 들어 있어야 비밀번호로 쓸 수 있다는 규칙을 만들었다.

DNA 문자열이 "AAACCTGCCAA"이고 뽑을 부분문자열의 길이가 4라고 하자. 그리고 부분문자열에 'A'가 1개 이상, 'C'가 1개 이상, 'G'가 1개 이상, 'T'가 0개 이상 들어 있어야 비밀번호로 쓸 수 있다고 하자. 이때 "ACCT"는 'G'가 1개 이상이어야 한다는 조건을 만족하지 못해 비밀번호로 쓸 수 없다. 반면 "GCCA"는 모든 조건을 만족하므로 비밀번호로 쓸 수 있다.

민호가 만든 DNA 문자열과 비밀번호로 쓸 부분문자열의 길이, 그리고 'A', 'C', 'G', 'T'가 각각 몇 개 이상 등장해야 비밀번호로 쓸 수 있는지가 순서대로 주어질 때, 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하자. 단 부분문자열이 등장하는 위치가 다르면 부분문자열이 같아도 서로 다른 문자열로 취급한다.

첫째 줄에 민호가 만든 DNA 문자열의 길이 $|S|$와 비밀번호로 쓸 부분문자열의 길이 $|P|$가 주어진다. ($1 \le |P| \le |S| \le 1{,}000{,}000$)

둘째 줄에 민호가 만든 DNA 문자열이 주어진다.

셋째 줄에 부분문자열에 들어 있어야 할 'A', 'C', 'G', 'T'의 최소 개수가 공백으로 구분되어 주어진다. 각 수는 $|S|$ 이하의 음이 아닌 정수이고, 네 수의 합은 $|S|$ 이하임이 보장된다.

첫째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력한다.