Problem1349--PIPI的字符串

1349: PIPI的字符串

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 386  Solved: 148
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有一个由'0'、'1'两种字符组成的字符串s, 然后有一个有 '0' , '1' , '?' 三种字符组成的字符串t , PIPI可以把 t 串中的 '?' 替换成为 '0' 或者 '1' ,现在PIPI考虑所有可能的字符串 t ,请问你这些字符串中有多少种能在s中完成匹配?

Input

输入包含多组测试用例(组数不超过10)。
对于每一组测试用例,第一行输入串 s ,第二行输入串 t 。(|s|<=50000, |t| <=50)

Output

对于每组测试用例,输出能够被匹配的种数。

Sample Input

00010001
??

Sample Output

3

HINT

t串能够变成 '00' '01' '10' '11'
除了'11' ,其他三种都能在 s 中找到匹配。

Source/Category

简单