Concert Attendance Schedules

John listens to 26 bands, labeled A through Z. He checked the schedule for the coming season and found that exactly one concert is held on each of the next $n$ days. He wants to attend exactly $k$ of those concerts in a fixed order, and he may attend concerts of the same band more than once.

Some bands charge more than others, so after attending a concert by band $b$ John rests at home for at least $h_b$ days before he attends another concert. If he attends a concert of band $b$ on day $d$, the next concert he attends is on day $d + h_b + 1$ or later.

Count the schedules that let John attend the concerts in the order he wants. The count can be very large, so print it modulo $10^9 + 7$.

The first line contains $k$ and $n$, separated by a space ($1 \le k \le 300$, $1 \le n \le 10^5$).

The second line contains the 26 values $h_A$ through $h_Z$, separated by spaces ($0 \le h_b \le 10^5$).

The third line contains a string of length $k$ listing the bands whose concerts John wants to attend, in order. For example, AFJAZ means A first, then F, then J, then A, then Z.

The fourth line contains a string of length $n$ written the same way, giving the band that performs on each of the next $n$ days.

Both strings consist of uppercase letters only.

Print the number of schedules that let John attend the concerts in the order he wants, modulo $10^9 + 7$, on one line.