콘서트 관람 일정

존은 A부터 Z까지 26개 밴드의 공연을 즐겨 듣는다. 다가오는 시즌의 일정을 확인해 보니 앞으로 $n$일 동안 매일 정확히 한 번의 공연이 열린다. 존은 이 중에서 정확히 $k$번의 공연을 정해진 순서대로 보려고 한다. 같은 밴드의 공연을 여러 번 봐도 된다.

밴드마다 공연 비용이 다르기 때문에, 존은 밴드 $b$의 공연을 본 뒤에는 다음 공연을 보기 전까지 최소 $h_b$일을 집에서 쉬기로 했다. 즉 $d$일에 밴드 $b$의 공연을 봤다면, 그다음으로 보는 공연의 날짜는 $d + h_b + 1$일 이후여야 한다.

존이 원하는 순서대로 공연을 볼 수 있는 일정이 몇 가지인지 구하여라. 그 수가 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 $k$와 $n$이 공백으로 구분되어 주어진다. ($1 \le k \le 300$, $1 \le n \le 10^5$)

둘째 줄에 $h_A$부터 $h_Z$까지 26개의 값이 공백으로 구분되어 주어진다. ($0 \le h_b \le 10^5$)

셋째 줄에 존이 보고 싶은 공연의 밴드를 순서대로 나열한 길이 $k$의 문자열이 주어진다. 예를 들어 AFJAZ는 A, F, J, A, Z 순서로 보고 싶다는 뜻이다.

넷째 줄에 앞으로 $n$일 동안 매일 공연하는 밴드를 같은 방식으로 나열한 길이 $n$의 문자열이 주어진다.

두 문자열은 모두 알파벳 대문자로만 이루어진다.

존이 원하는 순서대로 공연을 볼 수 있는 일정의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.