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

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

1 секунда

64 мегабайти

Дуже складна

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

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

Вхідні дані

У першому рядку два цілі числа $N$ та $K$ через пробіл. У наступному рядку $N$ цілих чисел $A_{1}, \dots, A_{N}$ A_1, \ldots, A_N через пробіл. Тут $A_{j}$ A_j — ціле число, що написано на $j$ -тій кулі.

Вихідні дані

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

Обмеження

$1 \leq K \leq N \leq 100000$ 1 \le K \le N \le 100000 $(1 0^{5})$ (10^5),

$0 \leq A_{j} \leq 1000000000$ 0 \le A_j \le 1000000000 $(1 0^{9})$ (10^9).

Приклади

3 2
4 5 7

11 2

Приклад 1

Приклад 2

Приклад 3

Примітка

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

• ${7} - {4, 5}$ \{7\} - \{4,5\}

• ${4, 5} - {7}$ \{4,5\} - \{7\}