Split in Sets
시간 제한1초메모리 제한512 MB
서로 다른 n개의 공을 k개의 서로 다른 빈 상자에 넣어 각 상자에 담긴 수들의 비트 AND 합을 최대로 만들고, 그 최댓값을 이루는 배치의 수를 10^9+7로 나눈 나머지를 구한다.
문제
Zenyk is given n balls with integers a1, . . . , an on them, and also k boxes. You have to put each ball in a box, and each box must have at least one ball in it. The value of a box is the bitwise AND of all integers on the balls in it.
Find the maximum total sum (regular) of all boxes and the number of ways to put balls in boxes that achieve the maximum sum. Note that the order of balls in a particular box is not important. However, all boxes are different, and all balls are also different, even if some balls have the same integer on them.
입력
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 105). The next line contains n integers a1, . . . , an (0 ≤ aj ≤ 109).
출력
Print two integers. The first integer should be the maximum total sum of all boxes. The second integer should be the number of ways to put balls in boxes modulo 109 + 7.