羊驼 是羊驼大陆情报局的特工，代号 "007"。羊驼大陆情报局经常会给特工们分配一些任务，任务分为 种，代号分别为 ~ ，作为羊驼大陆情报局深资老特工的 已经完美完成了无数次各类任务了，它曾经甚至和传说中的 "龙神" 对质过 。

然而，人到中年，体力总是力不从心，面对情报局给他安排的任务表， 逐渐学会了如何摸鱼。具体的， 已经对 种任务感到厌倦、无聊，如果 在完成当前任务的同时，下一个任务属于这 种，那么 可以选择去完成任务，也可以选择跳过而去完成下下个任务，而对于其他种类的任务，比如去暗杀 "龙神"， 觉得还是有那么点意思的，为了给枯燥的生活添加一些乐趣， 一定会做这种任务。注意: 在跳过一个任务的时候，必须完成所跳过的任务的后一个任务；如果被跳过的任务为最后一个任务，则所有任务被认为已完成； 所接到的第一个任务，必须完成，不能跳过。

现在，对于情报局新下发给 的任务时间表， 想要知道他有几种完成整张任务时间表的方案。

答案对 取模。

第一行两个整数 ，  （ ） ，表示任务时间表长度为 ， 对  种任务感到厌倦。

第二行一个字符串  长度为  ，保证出现的字符均为大写英文字母。

第三行一个字符串  长度为 ，表示  厌倦的  种任务。

一个整数，表示  完成整张任务时间表的方案数。

5 1
ABCAB
A

2