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

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

Вхідні дані

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

Вихідні дані

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

Обмеження

1 ≤ K ≤ N ≤ 100000 (105),

0 ≤ Aj ≤ 1000000000 (109).

Примітки

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

• {7}-{4,5}

• {4,5}-{7}