Problem E
Unique Story
Input: Standard
Input
Output: Standard
Output
The land of Bommywood has a large film industry, where a lot of movies are made each year. This is possible due to a simple and inexpensive technique adopted by the producers. A story is made out of one or more scenes taken from a predefined set of scene. A bad implication of this method is that a lot of the movies appear to be similar to each other but not exactly same, because the individual elements in predefined set of scene are different and movie producers never select the exact same subset of scenes to make their movies. A scene can be used at most once in a particular movie. Another rule the producers follow is they do not break the order of the scene when arranging them. For example, if the predefined set consists of { scene1, scene2, scene3} and producer selects scene1 and scene3, then the story would consist of scene1 followed by scene3; scene3 followed by scene1 is not allowed since this would violate the order.
In the neighboring land of Dammywood, exact same procedure is followed by its movie producers. Unfortunately, both the industries have a lot of common scenes in their predefined set of scene. Therefore, it may happen that some of the movies produced in the two lands are exactly same.
In this problem, given the predefined set of scene for both the movie industry, you will have to determine the number of different movies each industry can produce that will surely not be common with the other industry.
Input
The first line of input will be a positive integer T<=50, which denotes the number of test cases. Each case consists of exactly two lines, each containing a single string. The first line represents the predefined set of scene used in Bommywood and the second represents those of Dammywood. The format of the predefined set of scene is described below.
- Each character in the string is either an uppercase letter or a digit.
- Each scene in the set is represented by an uppercase letter followed by zero or more digits.
- Each set will consist of at most 1000 scenes and length of each string will be at most 3000.
Output
For each case of input, there will be one line of output. It will first contain the case number followed by the total number of movies that are unique to a particular industry. Note that, the answers could be arbitrarily large, so you are required to give your answer modulo 10000007. Look at sample output for exact formatting.
Sample
Input Output
for Sample Input
|
2 |
Case
1: 4 |
Illustration of Sample:
Case 1 -> A11, A1 and A11A1 from first set and A11, B1 and A11B1 from second set. A11 is common, so the other 4 are unique.
Case 2 -> The only movie that can be made from either set is A, which is common to both so no movies can be made that are particular to a industry.
Problemsetter: Shamim Hafiz
Special Thanks to: Jane Alam Jan