归途与征程

时间限制:2s      空间限制:128MB

题目描述

给出一个长度为N的由小写字母’a’~’z’和’*’组成的字符串A,一个长度为M的仅由小写字母’a’~’z’组成的字符串B。一个’*’可以匹配任意多个字符(包括0个)。求在B的所有循环同构串中,有多少个能够与A匹配。
循环同构串:就是把B的前k个字母(0<=k<M)移到结尾所得到的M个字符串。例如abc的循环同构串有abc、bca和cab。
A与B匹配:若除了A中的’*’号可以匹配B中的任意多个字符外,其余字符一一对应,则称A与B匹配。例如a*b*c与aadbc是匹配的,其中第一个*对应ad,第二个*对应空串。


输入格式


第一行为字符串A。
第二行为字符串B。


输出格式


输出在B的所有循环同构串中,有多少个能够与A匹配。


样例输入

样例输入1
aaaa
aaaa

样例输入2
a*a
aaaaaa

样例输入3
*a*b*c*
abacabadabacaba



样例输出

样例输出1
4

样例输出2
6

样例输出3
15

 

提示


对于100% 的测试点,1<=N<=100,1≤M≤100000。


题目来源

Poetize12

Menuappsclose