Split in Sets

Time limit1sMemory limit512 MB

Summary

Split n distinct balls into k nonempty boxes to maximize the sum of each box's bitwise AND, then count the optimal assignments modulo 10^9+7.

Level: Medium7 of 10
Topics: Bit manipulation, Combinatorics, Greedy
Solved: No attempts yet

Problem

Zenyk is given $n$ balls with integers $a_1, \ldots, a_n$ written on them, and also $k$ boxes. Put each ball in a box so that every box holds at least one ball. The value of a box is the bitwise AND of all integers on the balls in it. Find the maximum total sum of the values of all boxes, and the number of ways to put balls in boxes that achieve that maximum sum. The order of balls in a box does not matter. All boxes are distinct, and all balls are distinct, even when some balls have the same integer.

Input

The first line contains two integers $n$ and $k$ ( $1 \le k \le n \le 10^5$ ). The next line contains $n$ integers $a_1, \ldots, a_n$ ( $0 \le a_j \le 10^9$ ).

Output

Print two integers. The first is the maximum total sum of all boxes. The second is the number of ways to put balls in boxes that achieve this maximum, modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
3 2
4 7 5
```
Expected output
```
11 2
```
Example 2
Input
```
4 1
44 47 74 77
```
Expected output
```
8 1
```
Example 3
Input
```
4 4
44 47 74 77
```
Expected output
```
242 24
```