# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Pias and His Infinite String

Pias makes a string **P** by choosing some **distinct** lowercase letters. Then he makes another string **Q** by repeating **P** infinite
number of times. He calls **Q** an Infinite string.

For example, if **P** is “axyz” , then his Infinite string will look something like this “axyzaxyzaxyzaxyzaxyz…………”.

Pias has a friend named Faysal who has another string **S**. Pias wants to know how many ways a subsequence can be found in **S** such that it appears as a substring in **Q**.

Can you help him find the answer?

#### Input

The first line of the input contains **T**, the number of test cases. Each of the following **T** lines contain two strings **S** and **P**.

**T**≤ 10Both

**S**and**P**contains only lowercase letters.Characters in

**P**are distinct.Size of

**S**≤ 100000

#### Output

You have to print the answer. Since the answer can be large, print it modulo **1000000007 (10 ^{9} + 7)**.

#### Samples

Input | Output |
---|---|

4 abcba ab cat dog toph toph prog rock | 10 0 10 3 |

For, **S= “abcba”** , **P = “ab”**
Infinite string **Q** will look like **“abababababab……”**

The following subsequences appears as a substring in **Q**

{1} = “a”

{1,2} = “ab”

{1,4}= “ab”

{1,2,5}= “aba”

{1,4,5} =“aba”

{2} = “b”

{2,5}=”ba”

{4}=”b”

{4,5} = “ba”

{5}=”a”

So, the answer is 10

Login to submit