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

Author
Discussion