DIGSHIFT - Digit Shifts


You will be given a non-negative integer X. You need to perform Q queries on that integer. Each query will consist of a single decimal digit D. After every query, you need to move all occurrences of digit D in the integer to the end, while keeping the relative position of every other digit intact.

For example, suppose X = 123123, and suppose Q = 3.

  1. For the first query, D = 1, then after the digits are shifted X = 232311.
  2. For the second query, D = 2, then after the digits are shifted X = 331122.
  3. For the third query, D = 3, then after the digits are shifted X = 112233.

After every query, you need to output the value of the integer X. Since it can be really large, output it modulo 1000000007 (109 + 7).

Please note that if at any point after a query, X contains leading zeros, then the leading zeros should be discarded. Therefore, if X = 2022 and if D = 2, then after the query, X will become 222.

Input

The first line will contain a single integer T (1 ≤ T ≤ 20). Each starts with a single line, which will contain the integer X. Then, in the next line there is a single integer Q (1 ≤ Q ≤ 105), denoting the number of queries. Each of the next Q lines denotes a query, containing a decimal digit D (0 ≤ D ≤ 9). You can safely assume that X won’t contain leading zeros initially and that X will never have more than 105 digits.

Output

For each test case, first print the case number in a single line like “Case V:”. Then for each query, output the value of X modulo 1000000007. Refer to the sample I/O for more clarity.

Sample Input

1
123123
3
1
2
3

Sample Output

Case 1:
232311
331122
112233

hide comments
lalit_nit: 2022-11-29 11:07:57

in Sample Output "Case 1", in Problem Output Description "Case V". Case no. is in roman or integer?, at least provide 2/3 test cases for better understanding.
[Simes]: look at the example output. If it were Roman, it would be "Case I:", not "Case 1:"

Last edit: 2024-02-26 19:49:37

Added by:sgtlaugh
Date:2022-08-19
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem