John 喜欢听几支乐队的演唱会，我们用 A 到 Z 来表示这些乐队。他想要参加几场演唱会，于是他开始了解即将到来的演出季的日程安排。他发现接下来的 $n$ 天（$n \le 10^4$）里，每天恰好有一场演唱会。他决定按给定的顺序参加恰好 $k$ 场演唱会（$k \le 10^3$），并且他可能会参加同一支乐队的多场演唱会。

然而，有些乐队的演唱会比其他乐队更昂贵，因此，在参加完乐队 $b$（$b$ 为 A 到 Z 之间的字母）的演唱会后，John 决定在参加下一场演唱会之前至少在家休息 $h_b$ 天。

请帮助 John 计算他有多少种方式可以按照期望的顺序安排他的行程。由于这个数字可能非常大，结果请对 $10^9 + 7$ 取模。

输入格式

第一行包含 $k$ 和 $n$。 第二行包含 26 个 $h_b$ 的值，以空格分隔。 第三行包含 John 想要参加的 $k$ 场演唱会的乐队序列，例如 AFJAZ，表示先参加 A，然后是 F，以此类推。 第四行包含接下来的 $n$ 天的日程安排，以相同的方式给出。

输出格式

他可以安排行程的方式总数（对 $10^9 + 7$ 取模）。

样例

样例输入 1

2 10 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
AB 
ABBBBABBBB

样例输出 1

10