Billiard Balls
You have N billiard balls and K boxes. The balls are numbered from 1 to N, and the boxes are numbered from 1 to K. 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 AND sum of the numbers on the billiard balls it contains. Here, AND 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 1000000007. 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.
Input
The first line contains two integers N and K, separated by a space. The second line contains N integers A[1], A[2], ..., A[N], separated by spaces, where A[j] is the integer written on the j-th ball.
Output
Output two integers separated by a space: the maximum sum of the values of the boxes, and the remainder when dividing by 1000000007 the number of ways to achieve this maximum sum.
Constraints
1 ≤ K ≤ N ≤ 100000 (10^5)0 ≤ A[j] ≤ 1000000000 (10^9)
Notes
In the first example, the maximum sum is 11 = 7 + (5 AND 4). This can be achieved in the following ways:
{7}-{4,5}{4,5}-{7}