## LCC '18 Contest 5 J4 - How Many 5s?

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Mrs. Krasteva is known to be very good at guessing the number of people in her class that get a score of 5 on the AP exam. So good in fact that she has always been correct or 1-2 students off. Everyone wants to know her current guess so she has a challenge for you.

She will give you a list of numbers in which each number on the list produces the same remainder $$R$$ when dividing the unknown number of people. You will also be given the value of the remainder $$R$$. She also says that the number of people is the smallest possible number greater than its divisors which satisfies these conditions.

Find the number of people that score a 5 on the AP exam!

#### Input Specification

The first line will contain the amount of numbers $$N$$ and the shared remainder $$R$$

The next $$N$$ lines will contain a number $$M$$ which produces the remainder $$R$$ when dividing the number of people.

#### Output Specification

Output the smallest number of people that score a 5 on the AP exam $$S \bmod 10^9+7$$, satisfying the constraint that the number of people must not be less than $$\min{M}$$.

$$N\le 10, \ R \le 100, \ M \le 100$$

$$N\le 25, \ R \le 1000, \ M \le 1000$$

$$N\le 5, \ R < 10^{10}, \ M < 10^{10}$$

#### Sample Input 1

2 4
5
6

#### Sample Output 1

34

#### Sample Input 2

5 10
20
66
43
34
45

#### Sample Output 2

1447390