Бильярдные шары
У вас есть N бильярдных шаров и K коробок. Шары пронумерованы от 1 до N, а коробки — от 1 до K. На каждом шаре написано некоторое целое число. Ваша задача — распределить шары по коробкам так, чтобы в каждой коробке оказался хотя бы один шар. После этого для каждой коробки можно вычислить её значение как AND сумму чисел бильярдных шаров, находящихся в этой коробке. Операция AND — это побитовая конъюнкция.
Вам нужно определить максимальную возможную сумму значений всех коробок и остаток от деления на 1000000007 количества способов, которыми можно достичь этой максимальной суммы. Два способа считаются различными, если хотя бы один шар помещён в разные коробки. Обратите внимание, что шары с одинаковыми числами считаются различными.
Входные данные
Первая строка содержит два целых числа N и K, разделённых пробелом. В следующей строке расположены N целых чисел A[1], ..., A[N], разделённых пробелами, где A[j] — это число, написанное на j-ом шаре.
Выходные данные
Выведите два целых числа через пробел: максимальную сумму значений коробок и остаток от деления на 1000000007 количества способов, которыми можно её достичь.
Ограничения
1 ≤ K ≤ N ≤ 100000 (10^5),
0 ≤ A[j] ≤ 1000000000 (10^9).
Примечания
В первом примере максимальная сумма равна 11 = 7 + (5 AND 4). Её можно получить следующими способами:
• {7}-{4,5}
• {4,5}-{7}