Вы должно быть знаете, что Евклид был математиком. Ну, как оказалось, Морфей об этом тоже знал. Поэтому, когда он захотел разыграть Евклида, он послал ему соответствующий кошмар.
В своем плохом сне, у Евклида был набор \(S\) из \(n\) \(m\)-мерных векторов над полем \(\mathbb{Z}_2\), и он мог их складывать. Другими словами, у него были вектора с \(m\) координатами, каждая координата равнялась либо \(0\), либо \(1\). Сложение векторов определяется следующим образом: пусть \(u+v = w\), тогда \(w_i = (u_i + v_i) \bmod 2\).
Евклид может сложить любое подмножество векторов из \(S\) и сохранить получившийся \(m\)-мерный вектор над \(\mathbb{Z}_2\). В частности, он может сложить пустое подмножество векторов. В таком случае, все координаты получившегося вектора будут равны \(0\).
Пусть \(T\) будет множеством всех векторов, которые могут быть получены как сумма некоторого подмножества векторов из \(S\). Теперь Евклид интересуется, каков размер \(T\), и может ли он использовать только какое-то подмножество \(S'\) множества \(S\), чтобы получить все вектора из \(T\). Как всегда и бывает в таких ситуациях, он не проснется до тех пор, пока не выяснит это. Пока что дела для философа обстоят довольно мрачно. Однако, появилась надежда, когда он заметил, что все вектора из \(S\) содержат максимум \(2\) координаты, равные \(1\).
Помогите Евклиду вычислить \(|T|\), количество \(m\)-мерных векторов над \(\mathbb{Z}_2\), которые могут быть получены как сумма какого-то подмножества векторов из \(S\). Так как оно может быть довольно велико, выведите его по модулю \(10^9+7\). Также, вы должны найти \(S'\), минимальное такое подмножество \(S\), что все вектора из \(T\) могут быть получены как как сумма какого-то подмножества векторов из \(S'\). В случае, если существует несколько таких подмножеств с минимальным количеством элементов, выведите лексикографически минимальный по индексам взятых элементов.
Рассмотрим два множества \(A\) и \(B\), такие что \(|A| = |B|\). Пусть \(a_1, a_2, \dots a_{|A|}\) и \(b_1, b_2, \dots b_{|B|}\) будут возрастающие массивы индексов элементов, взятых в \(A\) и в \(B\), соответственно. \(A\) лексикографически меньше, чем \(B\), если существует такое \(i\), что \(a_j = b_j\) для всех \(j < i\) и \(a_i < b_i\).
Примечание
В первом примере нам даны три вектора:
Оказывается, что мы может представить все вектора из \(2\)-мерного пространства используя эти вектора:
- \(00\), сумма пустого подмножества векторов;
- \(01 = 11 + 10\), сумма первого и третьего векторов;
- \(10 = 10\), просто первый вектор;
- \(11 = 10 + 01\), сумма первого и второго векторов.
Поэтому, \(T = \{00, 01, 10, 11\}\). Мы можем выбрать любые два из трех векторов \(S\), и все еще будем способны получить все вектора из \(T\). В таком случае, мы выберем два первых вектора. Так как мы не можем получить все вектора из \(T\), используя только один вектор из \(S\), \(|S'| = 2\) и \(S' = \{10, 01\}\) (индексы \(1\) и \(2\)), как множество \(\{1, 2 \}\) — лексикографически минимально. Мы можем получить все вектора из \(T\), используя только вектора из \(S'\), как показано ниже:
- \(00\), сумма пустого подмножества;
- \(01 = 01\), просто второй вектор;
- \(10 = 10\), просто первый вектор;
- \(11 = 10 + 01\), сумма первого и второго вектора.