Problem G: good poem

Problem G: good poem

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 22  Solved: 4
[Submit] [Status] [Web Board] [Creator:]

Description

“众里寻他千百度。蓦然回首,那人却在,灯火阑珊处” 
“衣带渐宽终不悔,为伊消得人憔悴” 
 春意盎然,情歌之王某云飞难免有些悸动,于是他想着给自己的女朋友们写诗(我酸了),但是他的女朋友们要求也是很高的,女朋友们喜欢长度为N的诗句,并且其中不要有自己不喜欢的诗句在其中。但是被春天冲昏头脑的某云飞表示:“才这么短?没问题,小意思!我分分钟给你写出很多句~” 
那么问题来了,某云飞到底写了多少句呢?由于答案可能很大,所以答案对1000000007取余 

Input

测试数据多组。 
第一行输入一个正整数N,表示女朋友们喜欢的句子长度 (1 <= N <= 1e9) 
第二行输入一个字符串集s1,表示某云飞可以使用字符串集中的字符进行组合句子 (字符集不重复,且字典序从小到大)
第三行输入一个字符串s2,表示女朋友们不喜欢的诗句 (1<= s2.size() <= 50)

Output

输出某云飞能写多少句情诗呢?答案%1000000007

Sample Input Copy

3
ab
aa

Sample Output Copy

5

HINT

字符集为{a, b} 可组成长度为3的文章有8篇: {aaa, aab, abb, aba, bbb, bba, baa, bab} 其中不含子串"aa"的有5篇