Billiard Balls#7806
You have billiard balls and boxes. The balls are numbered from to , and the boxes are numbered from to . Each billiard ball has an integer written on it. Your task is to distribute the balls into the boxes so that each box contains at least one ball. Once distributed, you can calculate the value of each box as the sum of the numbers on the billiard balls it contains. Here, refers to the bitwise conjunction operation.
Your goal is to determine two things: the maximum possible sum of the values of all the boxes, and the number of ways to achieve this maximum sum, with the result given modulo . Two distributions are considered different if at least one ball is placed in a different box. Note that even if two balls have the same number, they are considered distinct.
The first line contains two integers and , separated by a space. The second line contains integers A_1, \ldots, A_N, separated by spaces, where A_j is the integer written on the -th ball.
Output two integers separated by a space: the maximum sum of the values of the boxes, and the remainder when dividing by the number of ways to achieve this maximum sum.
#### Constraints
1 \le K \le N \le 100000 (10^5),
0 \le A_j \le 1000000000 (10^9).
"' 3 2 4 5 7 "'
"' 11 2 "'
Esempio 1
Esempio 2
Esempio 3
In the first example, the maximum sum is 11 = 7 + (5 \text{ AND } 4). This can be achieved in the following ways:
• \{7\} - \{4,5\}
• \{4,5\} - \{7\}