시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB0000.000%

문제

Открытый в 2345 году химический элемент млуран очень радиоактивен. Неправильное обращение с млураном может привести к непредсказуемым последствиям, поэтому при его использовании, хранении и транспортировке необходимо соблюдать особую осторожность.

Существует много различных изотопов млурана, каждый из которых характеризуется одним натуральным числом — своей атомной массой. При длительном хранении вместе любой пары изотопов, сумма масс которых равна одному из k «критических чисел», эта пара изотопов вступает в реакцию и происходит взрыв. Известно, что все критические числа являются неотрицательными степенями двойки.

В ядерной лаборатории Флатландии образцы млурана хранятся на двух специальных складах. Ученым удалось получить n различных изотопов млурана, массы которых являются числами от 1 до n. Теперь необходимо распределить изотопы по складам для хранения. Безопасными называются такие способы хранения, при которых каждый изотоп хранится ровно на одном складе, а любые два различных изотопа, сумма масс которых равна одному из «критических чисел», хранятся на разных складах.

Помогите ученым выяснить, сколько существует различных безопасных способов хранения млурана.

입력

Входные данные к задаче содержат несколько тестовых наборов. Описание каждого набора состоит из двух строк.

Первая строка описания содержит два целых числа n и k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 61) — количество изотопов, которые необходимо хранить, и количество «критических чисел». Следующая строка содержит k различных натуральных чисел, каждое из которых является степенью двойки и не превышает 2n — критические числа. Критические числа отделены друг от друга пробелами.

Количество наборов данных в каждом тесте не превышает 10000. Последняя строка теста содержит два нуля.

출력

Для каждого тестового набора на отдельной строке выведите количество безопасных способов хранения всех изотопов на двух складах, взятое по модулю 109 + 7.

예제 입력 1

5 1
1
4 2
4 2
0 0

예제 출력 1

32
8