题目描述

Cjwssb 得到了你的帮助，显得很开心，跟你道谢，你回谢了他。但随后他由于少听了一些词，对你的回谢造成了误会，这使你们两个产生了隔阂，你很不甘心，于是打算告诉他这句话有几种理解方式，以告诉他他误解你了。一句话的理解方式如下：

对于一句原句和听到的句子，理解方式是将听到的句子替换掉原句的相同部分，替换成 *，使得原句形成一个新的句子，以达到新的意思，你的任务是统计有多少种意思。

输入格式

第一行一个整数 $T$，表示 $T$ 组测试点。

每组测试点两个字符串，一个字符串一行，第一行字符串是原句，第二行是听到的句子。

输出格式

对于每一个测试点，输出一行 Case #x: y，$x$ 表示测试点，$y$ 表示答案，由于答案可能很大，你只需要输出答案取模 $10^9+7$。

4
hehehe
hehe
woquxizaolehehe
woquxizaole
hehehehe
hehe
owoadiuhzgneninougur
iehiehieh

Case #1: 3
Case #2: 2
Case #3: 5
Case #4: 1

提示

在第一个测试点，hehehe 有三个理解意思，分别是 *he，he*，hehehe。

在第三个测试点，hehehehe 有五个理解意思，分别是 *hehe，he*he，hehe*，**，hehehehe。

对于 $100$ 的数据

$T\le 30$

$|A|\le 10^5$

$|B|\le |A|$

By：2016 Mul