Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Solve This Giveaway Problem First

By Hasinur_ · Limits 1s, 512 MB

This problem is straightforward and easy. You will be given two integers N, P and a list L of positive integers.

You have to count how many numbers in the range [1, NP] are divisible by at least one of the numbers from the list L.

Input

The first line of the input will contain an integer T. Then there will be T test cases.
The first line of each case will contain two integer numbers N and P. The second line of each case will contain an integer S, size of the list L. The third line of each case will contain S space-separated positive integer numbers.

1 <= T <= 105
1 <= N <= 10100000
1 <= P <= 105
1 <= S <= 5
1 <= numbers in the list L <= 109

N.B: It is guaranteed that multiplication of all numbers in the list L will not exceed 109 and the summation of the length of number N over all test cases will not exceed 106.

Output

For each test case, print “Case x: y” (without quotation marks) where x is the test case number and y is the required answer modulo 1000000007.

See the sample input-output for better understanding.

Sample

InputOutput
2
4 2
2
2 4
4 2
2
1 2
Case 1: 8
Case 2: 16


Discussion
Statistics

60% Solution Ratio

ovis96Earliest, 1w ago

BossssFastest, 0.2s

ovis96Lightest, 1.4 MB

kzvd4729Shortest, 981B

Submit

Login to submit