Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

WPE - E Team (basic)

In team programming contests, teams solve problems denoted with digits and uppercase and lowercase letters. It is thus easy to calculate that there are 2 * 26 + 10 = 62 problems. During the competition, every team submits various problems for verification. Therefore, the sequence of a team's submissions is a sequence of digits and uppercase and lowercase letters, where characters may be repeated.

The coach of one of the teams, a certain Professor M., recently came up with a crazy idea to boost the performance of his team: he devised a minimum and maximum plan for the team. The minimum plan is a sequence of submissions that the team has to make in order not to disappoint Professor M. In between the submissions belonging to the minimum plan, the team is allowed to make other submissions. However, it needs to remember not to exceed the maximum plan, meaning that the sequence of submissions needs to be a subsequence of the maximum plan. Otherwise, the professor will also be disappointed. We will call a sequence of submissions admissible if it doesn't disappoint Professor M. For example, if the minimum plan is BBAb and the maximum plan is CBBAbAb, then some admissible sequences are BBAb, CBBAbb and BBbAb.

The team is wondering how many admissible sequences of submissions there are. Help them!

Multiple test cases

The first line of the input contains Z ≤ 20 - the number of test cases. Z descriptions of single test cases follow.

Single test case

The first line contains the maximum plan, the second line the minimum plan. The plans are nonempty and consist of digits and uppercase and lowercase letters. The lines contain no spaces.


Basic: each plan has length at most 200.
Professional: each plan has length at most 2000.


Print a line containing one number X mod (109 + 7), where X is the number of admissible sequences of submissions.

Sample input


Sample output



Added by:gawry
Time limit:0.100s-1.528s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
© All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.