# 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

Limits: 2s, 256 MB

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 ≤ 10

• Both 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 (109 + 7).

#### Samples

InputOutput
```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

Discussion