# 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


• NumberTheory

### Statistics

61% Solution Ratio

ovis96Earliest, Nov '19

likhon5Fastest, 0.1s

ovis96Lightest, 1.4 MB

kzvd4729Shortest, 981B

### Submit 