창고의 공통 묶음 단위

문제

한 물류 창고에는 출고를 기다리는 상자 N개가 있다. 각 상자에는 같은 종류의 부품이 양의 정수 개수만큼 들어 있다. 상자는 입력 순서대로 1번부터 N번까지 구별되며, 부품 수가 같더라도 서로 다른 상자이다. 창고 관리자는 이번 작업에 사용할 상자를 정확히 K개 골라 자동 포장 장치에 올리려 한다. 포장 장치는 선택한 모든 상자에 하나의 공통 묶음 단위 d를 적용한다. d는 양의 정수이며, 각 상자의 부품을 정확히 d개씩 나누어 묶었을 때 남는 부품이 없어야 한다. 상자마다 만들어지는 묶음 수는 달라도 된다. 다만 서로 다른 상자의 부품을 합치거나, 일부 부품을 빼거나, 한 상자에 여러 묶음 단위를 적용하는 일은 허용되지 않는다. 선택하지 않은 상자는 이번 작업의 조건에 아무런 영향을 주지 않는다. 관리자는 한 묶음에 가능한 한 많은 부품을 넣으려 한다. 따라서 정확히 K개의 상자를 선택하는 방법과 그 상자들에 적용할 공통 묶음 단위를 함께 고려하여, 가능한 d의 최댓값 D를 구해야 한다. 양의 정수 개수의 부품은 항상 1개씩 묶을 수 있으므로, 주어진 조건에서는 가능한 묶음 단위가 반드시 존재한다. 최대 묶음 단위만으로는 작업 계획을 고를 수 없으므로, D를 적용할 수 있는 상자 선택 방법의 수도 필요하다. 여기서 하나의 선택 방법은 서로 다른 상자 번호 K개로 이루어진 집합이다. 상자를 고르는 순서는 구별하지 않으며, 선택한 상자 중 하나라도 번호가 다르면 다른 방법으로 센다. 상자 안에서 부품을 묶는 순서나 각 묶음의 배치는 세지 않는다. 특히 부품 수가 같은 상자가 여러 개 있어도 각 상자의 번호는 별개로 취급한다. 가능한 최대 묶음 단위 D와, 그 단위를 적용할 수 있는 선택 방법의 수를 구한다. 방법의 수는 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ K ≤ N ≤ 50,000이다.
둘째 줄에 각 상자의 부품 수 A1, A2, ..., AN이 공백으로 주어진다. 모든 Ai는 정수이며 1 ≤ Ai ≤ 200,000이다.

출력

첫째 줄에 가능한 공통 묶음 단위의 최댓값 D를 출력한다. 둘째 줄에 D를 적용할 수 있는 상자 선택 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

6 3
6 10 15 30 30 18

15
1

5 3
12 12 24 24 36

12
10

4 1
7 20 20 3

20
2

출처: Devin.KR 자체 제작