LCS means 'Longest Common Subsequence' that means two non-empty strings are given; the longest subsequence that are common. Subsequence means removing 0 or more characters from a string.

Now you are given two non-empty strings s and t, your task is to find the number of distinct LCS of s and t. Since the result can be very big, print the result modulo 1000007.

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case contains two lines, the first line is the string s and the second line is the string t. You may assume that the strings are non-empty and consist only of lowercase letters and the length of the each string is at most 1000.

For each case, print the case number and the number of distinct LCS of s and t modulo 1000007 (10⁶ + 7).