집합으로 나누기

시간 제한1초메모리 제한512 MB

요약

서로 다른 n개의 공을 비어 있지 않은 k개의 상자에 나눠 담아, 각 상자의 비트 AND 합을 최대로 하는 방법의 수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 7점
유형: 비트 연산, 조합론, 그리디
정답자: 아직 제출이 없습니다

문제

Zenyk는 정수 $a_1, \ldots, a_n$ 이 적힌 공 $n$ 개와 상자 $k$ 개를 가지고 있다. 모든 상자에 공이 최소 한 개 들어가도록 모든 공을 상자에 나눠 담아라. 상자의 값은 그 상자에 든 공에 적힌 정수들의 비트 AND이다. 모든 상자 값의 합의 최댓값과, 그 최댓값을 달성하는 공의 배치 방법의 수를 구하라. 상자 안에서 공의 순서는 구분하지 않는다. 상자는 모두 서로 다르고, 같은 정수가 적힌 공이 있더라도 공은 모두 서로 다르다.

입력

첫 줄에 정수 $n$ 과 $k$ ( $1 \le k \le n \le 10^5$ )가 주어진다. 다음 줄에는 정수 $a_1, \ldots, a_n$ ( $0 \le a_j \le 10^9$ )이 주어진다.

출력

정수 두 개를 출력하라. 첫 번째는 모든 상자 값의 합의 최댓값이다. 두 번째는 그 최댓값을 달성하는 배치 방법의 수를 $10^9 + 7$ 로 나눈 나머지이다.

예제3

예제 1
입력
```
3 2
4 7 5
```
예상 출력
```
11 2
```
예제 2
입력
```
4 1
44 47 74 77
```
예상 출력
```
8 1
```
예제 3
입력
```
4 4
44 47 74 77
```
예상 출력
```
242 24
```