text: # Problem You may know that Euclid was a mathematician.Well, as it turns out, Morpheus knew it too.So when he wanted to play a mean trick on Euclid, he sent him an appropriate nightmare.In his bad dream Euclid has a set S of n m-dimensional vectors over the Z_2 field and can perform vector addition on them.In other words he has vectors with m coordinates, each one equal either 0 or 1.Vector addition is defined as follows: let u+v = w, then w_i = (u_i + v_i) mod 2.Euclid can sum any subset of S and archive another m-dimensional vector over Z_2.In particular, he can sum together an empty subset; in such a case, the resulting vector has all coordinates equal 0.Let T be the set of all the vectors that can be written as a sum of some vectors from S.Now Euclid wonders the size of T and whether he can use only a subset S' of S to obtain all the vectors from T.As it is usually the case in such scenarios, he will not wake up until he figures this out.So far, things are looking rather grim for the philosopher.But there is hope, as he noticed that all vectors in S have at most 2 coordinates equal 1.Help Euclid and calculate |T|, the number of m-dimensional vectors over Z_2 that can be written as a sum of some vectors from S.As it can be quite large, calculate it modulo 10^9+7.You should also find S', the smallest such subset of S, that all vectors in T can be written as a sum of vectors from S'.In case there are multiple such sets with a minimal number of elements, output the lexicographically smallest one with respect to the order in which their elements are given in the input.Consider sets A and B such that |A| = |B|.Let a_1, a_2, ...a_{|A|} and b_1, b_2, ...b_{|B|} be increasing arrays of indices elements of A and B correspondingly.A is lexicographically smaller than B iff there exists such i that a_j = b_j for all j < i and a_i < b_i.