eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Більярдні кулі

Більярдні кулі

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У Вас є N більярдних кульок та К коробок. Кулі пронумеровані від 1 до N, а коробки — від 1 до К. На кожній більярдній кулі написано деяке ціле число. Вам необхідно розкласти кулі в коробки так, щоб у кожній коробці була принаймні одна куля. Після цього для кожної коробки можна порахувати її значення як AND суму чисел більярдних кульок, що знаходяться у коробці. Тут AND — операція побітової кон’юнкції.

Вам необхідно визначити яку максимальну суму (звичайну) значень коробок Ви можете отримати та остачу від ділення на 1000000007 кількості способів, якими можна отримати максимальну суму. Два способи вважаються різними, якщо згідно них принаймні одна кулька знаходиться у різних коробках. Зауважте, що кулі з однаковими числами вважаються різними.

Вхідні дані

У першому рядку два цілих числа N та К через пробіл. У наступному рядку N цілих чисел А[1],..., А[N] через пробіл. Тут A[j] — ціле число, що написано на j-тій кульці.

Вихідні дані

Два цілих числа через пробіл — максимальна сума значень коробок та остача від ділення на 1000000007 кількості способів, якими можна її отримати.

####Обмеження1 ≤ K ≤ N ≤ 100000 (10^5),

0 ≤ Aj ≤ 1000000000 (10^9).

####Примітки

У першому прикладі максимальна сума рівна 11 = 7 + (5 AND 4). ЇЇ можна отримати такими способами:

{7}-{4,5}

{4,5}-{7}

Приклад

Вхідні дані #1
3 2
4 7 5
Вихідні дані #1
11 2
Вхідні дані #2
4 1
44 47 74 77
Вихідні дані #2
8 1
Вхідні дані #3
4 4
44 47 74 77
Вихідні дані #3
242 24
Джерело Літня школа програмування, Ужгород 2016, День 1, Контест Василя БІлецького