#3059. 归途与征程

题目描述

给出一个长度为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匹配。例如abc与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。