18733번 - Split in Sets 다국어

Zenyk is given n balls with integers a₁, . . . , a_n 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 ≤ 10⁵). The next line contains n integers a₁, . . . , a_n (0 ≤ a_j ≤ 10⁹).

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 10⁹ + 7.