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 ≤ 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).

Sample

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