Sonmoy has taken up a course on regular expressions and is very fascinated by their power. His favorite part is + operator. When applied on a character, it represents all the strings which have more than or equal to one occurrence of that character. For example, a+ represents a, aa, aaa, ... and so on. Therefore, a string containing + can represent many strings. For example. a+ab+c represents aabc, aaabc, aaabbc, aabbc, .. etc, but it does not represent abc, ab, bc, aac etc
Now, he gives you two strings S and P. S can contain lowercase English alphabets ('a'-'z') and '+'. P contains only lowercase English alphabets ('a'-'z'). He calls a string beautiful if the at least one of the substring of that string can be represented by S. He asks you the the number of different subsequences of P that are beautiful. Two subsequences are said to be different if there exist an index i which belongs to one of them but not to other.
Note: You can find definition of subsequence here and substring here.
Input
- The first line contains a single integer representing number of test cases T
- Each test case is described by two lines. First of which describes S and the second line describes P
- For each test case, you need to output a single line containing an integer which is the answer for that case modulo 109 + 7.
- 1 ≤ T ≤ 100
- 1 ≤ |S|, |P| ≤ 300
- In the first test case, a, ab, ac, abc are beautiful
- In the second test case, aab, ab, ab arebeautiful. Note that ab is counted multiple times as it occurs multiple times as subsequence.
