G. Новый ЛРТ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В знаменитом городе открылся новый ЛРТ (легкорельсовый транспорт). Он представляет собой поезд, который едет по прямой.

Вам даны два числа $$$n$$$ и $$$m$$$, и массив $$$c$$$, состоящий из $$$m$$$ целых чисел. Вы находитесь на позиции $$$0$$$, и вам нужно попасть на позицию $$$n$$$. Если вы находитесь на позиции $$$i$$$, вы можете проехать на поезде следующим образом:

  • Выберите положительное число $$$x$$$ такое, что $$$m\& x = x$$$, где $$$\&$$$ обозначает операцию побитового И.
  • Переместитесь с позиции $$$i$$$ на $$$i + x$$$, заплатив $$$c_x$$$ монет.
Цена поездки это общее количество монет, которое пришлось заплатить, чтобы добраться из позиции $$$0$$$ в позицию $$$n$$$. Две поездки считаются различными, если порядок или сами перемещения отличаются. Ваша задача — определить сумму цен всех возможных поездок. Поскольку ответ может быть большим, выведите его по модулю $$$10^9 + 7$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит числа $$$n$$$ и $$$m$$$ ($$$1\le n, m\lt 2^{20}$$$).

Вторая строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$c_1, c_2, \ldots, c_m$$$ ($$$1\le c_i\le 10^9$$$).

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходят $$$2^{20}$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — ответ на задачу по модулю $$$10^9 + 7$$$.

Пример
Входные данные
4
3 3
2 2 1
4 5
3 1 2 4 5
5 3
9 1 5
8 3
1000000000 1000000000 1000000000
Выходные данные
15
16
271
999997081
Примечание

В первом наборе входных данных существует $$$4$$$ пути доехать до позиции $$$n$$$:

  • $$$0\rightarrow 1\rightarrow 2\rightarrow 3$$$. Цена этого пути равна $$$c_1 + c_1 + c_1 = 6$$$.
  • $$$0\rightarrow 1\rightarrow 3$$$. Цена этого пути равна $$$c_1 + c_2 = 4$$$.
  • $$$0\rightarrow 2\rightarrow 3$$$. Цена этого пути равна $$$c_2 + c_1 = 4$$$.
  • $$$0\rightarrow 3$$$. Цена этого пути равна $$$c_3 = 1$$$.
Таким образом, ответ равен $$$6 + 4 + 4 + 1 = 15$$$.