Description

Cjwssb was very happy after receiving your help and thanked you, and you thanked him back. However, because he missed some words, he misunderstood your reply. This created a rift between you. Unwilling to accept this, you decide to tell him how many different ways that sentence can be understood, to show that he misunderstood you.

Given an original sentence and the heard sentence, an interpretation is formed by choosing any set of pairwise non-overlapping occurrences of the heard sentence inside the original sentence and replacing each chosen occurrence with a single *, thereby turning the original sentence into a new sentence to convey a new meaning. Your task is to count how many different meanings there are.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case, there are two strings, one per line. The first line is the original sentence, and the second line is the heard sentence.

Output Format

For each test case, output one line in the form Case #x: y, where $x$ is the test case number and $y$ is the answer. Since the answer may be large, output it modulo $10^9+7$.

4
hehehe
hehe
woquxizaolehehe
woquxizaole
hehehehe
hehe
owoadiuhzgneninougur
iehiehieh

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

Hint

In the first test case, hehehe has three interpretations: *he, he*, hehehe.

In the third test case, hehehehe has five interpretations: *hehe, he*he, hehe*, **, hehehehe.

Constraints for $100\%$ of the testdata:

$T \le 30$.

$|A| \le 10^5$.

$|B| \le |A|$.

By: 2016 Mul.

Translated by ChatGPT 5