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.

Input

In the first line of input, there are two integers n, m (1 ≤ n, m ≤ 5 ⋅ 10^5) denoting the number of vectors in S and the number of dimensions. 

Next n lines contain the description of the vectors in S. In each of them there is an integer k (1 ≤ k ≤ 2) and then follow k distinct integers x_1, ... x_k (1 ≤ x_i ≤ m). This encodes an m-dimensional vector having 1s on coordinates x_1, ... x_k and 0s on the rest of them.

Among the n vectors, no two are the same.

Output

In the first line, output two integers: remainder modulo 10^9+7 of |T| and |S'|. In the second line, output |S'| numbers, indices of the elements of S' in ascending order. The elements of S are numbered from 1 in the order they are given in the input.

Examples

Input


3 2
1 1
1 2
2 2 1


Output


4 2
1 2 


Input


2 3
2 1 3
2 1 2


Output


4 2
1 2 


Input


3 5
2 1 2
1 3
1 4


Output


8 3
1 2 3 

Note

In the first example we are given three vectors: 

  * 10 
  * 01 
  * 11 



It turns out that we can represent all vectors from our 2-dimensional space using these vectors: 

  * 00 is a sum of the empty subset of above vectors; 
  * 01 = 11 + 10, is a sum of the first and third vector; 
  * 10 = 10, is just the first vector; 
  * 11 = 10 + 01, is a sum of the first and the second vector. 



Hence, T = \{00, 01, 10, 11\}. We can choose any two of the three vectors from S and still be able to obtain all the vectors in T. In such a case, we choose the two vectors which appear first in the input. Since we cannot obtain all vectors in T using only a single vector from S, |S'| = 2 and S' = \{10, 01\} (indices 1 and 2), as set \{1, 2 \} is lexicographically the smallest. We can represent all vectors from T, using only vectors from S', as shown below: 

  * 00 is a sum of the empty subset; 
  * 01 = 01 is just the second vector; 
  * 10 = 10 is just the first vector; 
  * 11 = 10 + 01 is a sum of the first and the second vector. 
import java.util.ArrayList;

public class Main {

	public static void main(final String[] args) {
		new Main();
	}

	public Main() {
		final FastScanner fs = new FastScanner();
		final java.io.PrintWriter out = new java.io.PrintWriter(System.out);
		solve(fs, out);
		out.flush();
	}

	public void solve(final FastScanner fs, final java.io.PrintWriter out) {
		final int n = fs.nextInt(), m = fs.nextInt();
		final UnionFind uf = new UnionFind(m);
		final ArrayList<Integer> ans = new ArrayList<>();
		final int MOD = 1_000_000_007;
		for (int i = 0;i < n;++ i) {
			final int k = fs.nextInt();
			if (k == 1) {
				final int x1 = fs.nextInt() - 1;
				if (uf.setOne(x1)) ans.add(i + 1);
			} else {
				final int x1 = fs.nextInt() - 1, x2 = fs.nextInt() - 1;
				if (uf.getOne(x1) && uf.getOne(x2)) continue;
				if (uf.merge(x1, x2)) ans.add(i + 1);
			}
		}
		out.println(IntMath.pow(2, ans.size(), MOD) + " " + ans.size());
		out.print(ans.get(0));
		for (int i = 1;i < ans.size();++ i) out.print(" " + ans.get(i));
		out.println();
	}
}

class UnionFind {
	int[] parent;
	boolean[] useOne;
	UnionFind(final int n) {
		parent = new int[n];
		for (int i = 0;i < n;++ i) parent[i] = -1;
		useOne = new boolean[n];
	}
	int top(final int x) {
		return parent[x] < 0 ? x : (parent[x] = top(parent[x]));
	}
	boolean merge(int l, int r) {
		l = top(l);
		r = top(r);
		if (l == r) return false;
		if (parent[l] < parent[r]) {
			parent[l] += parent[r];
			parent[r] = l;
			useOne[l] |= useOne[r];
		} else {
			parent[r] += parent[l];
			parent[l] = r;
			useOne[r] |= useOne[l];
		}
		return true;
	}
	boolean setOne(int x) {
		x = top(x);
		if (useOne[x]) return false;
		useOne[x] = true;
		return true;
	}
	boolean getOne(final int x) {
		return useOne[top(x)];
	}
}

class FastScanner {

	private final java.io.InputStream in = System.in;
	private final byte[] buffer = new byte[8192];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) return true;
		ptr = 0;
		try {
			buflen = in.read(buffer);
		} catch (final java.io.IOException e) {
			e.printStackTrace();
		}
		return buflen > 0;
	}

	private byte readByte() {
		return hasNextByte() ? buffer[ptr++ ] : -1;
	}

	private static boolean isPrintableChar(final byte c) {
		return 32 < c || c < 0;
	}

	private static boolean isNumber(final int c) {
		return '0' <= c && c <= '9';
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++ ;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		final StringBuilder sb = new StringBuilder();
		byte b;
		while (isPrintableChar(b = readByte()))
			sb.appendCodePoint(b);
		return sb.toString();
	}

	public final char nextChar() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		return (char)readByte();
	}

	public final long nextLong() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		long n = 0;
		try {
			byte b = readByte();
			if (b == '-') {
				while (isNumber(b = readByte()))
					n = n * 10 + '0' - b;
				return n;
			} else if (!isNumber(b)) throw new NumberFormatException();
			do
				n = n * 10 + b - '0';
			while (isNumber(b = readByte()));
		} catch (final java.util.NoSuchElementException e) {}
		return n;
	}

	public final int nextInt() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		int n = 0;
		try {
			byte b = readByte();
			if (b == '-') {
				while (isNumber(b = readByte()))
					n = n * 10 + '0' - b;
				return n;
			} else if (!isNumber(b)) throw new NumberFormatException();
			do
				n = n * 10 + b - '0';
			while (isNumber(b = readByte()));
		} catch (final java.util.NoSuchElementException e) {}
		return n;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

class Arrays {

	public static void sort(final int[] array) {
		int l, min = 0xFFFFFFFF, max = 0;
		for (l = 0; l < array.length; ++l) {
			final int i = array[l];
			min &= i;
			max |= i;
			if ((i & 0x80000000) == 0) break;
		}
		for (int r = l + 1; r < array.length; ++r) {
			final int i = array[r];
			min &= i;
			max |= i;
			if ((i & 0x80000000) != 0) {
				array[r] = array[l];
				array[l++ ] = i;
			}
		}
		final int use = min ^ max, bit = Integer.highestOneBit(use & 0x7FFFFFFF);
		if (bit == 0) return;
		sort(array, 0, l, use, bit);
		sort(array, l, array.length, use, bit);
	}

	private static void sort(final int[] array, final int left, final int right, final int use, int digit) {
		if (right - left <= 96) {
			for (int i = left + 1; i < right; ++i) {
				final int tmp = array[i];
				int tmp2, j;
				for (j = i; j > left && (tmp2 = array[j - 1]) > tmp; --j)
					array[j] = tmp2;
				array[j] = tmp;
			}
			return;
		}
		int l = left;
		while (l < right && (array[l] & digit) == 0)
			++l;
		for (int r = l + 1; r < right; ++r) {
			final int i = array[r];
			if ((i & digit) == 0) {
				array[r] = array[l];
				array[l++ ] = i;
			}
		}
		if ((digit = Integer.highestOneBit(use & digit - 1)) == 0) return;
		sort(array, left, l, use, digit);
		sort(array, l, right, use, digit);
	}

	public static void sort(final long[] array) {
		int l;
		long min = 0xFFFFFFFFFFFFFFFFL, max = 0;
		for (l = 0; l < array.length; ++l) {
			final long i = array[l];
			min &= i;
			max |= i;
			if ((i & 0x8000000000000000L) == 0) break;
		}
		for (int r = l + 1; r < array.length; ++r) {
			final long i = array[r];
			min &= i;
			max |= i;
			if ((i & 0x8000000000000000L) != 0) {
				array[r] = array[l];
				array[l++ ] = i;
			}
		}
		final long use = min ^ max, bit = Long.highestOneBit(use & 0x7FFFFFFFFFFFFFFFL);
		if (bit == 0) return;
		sort(array, 0, l, use, bit);
		sort(array, l, array.length, use, bit);
	}

	private static void sort(final long[] array, final int left, final int right, final long use, long digit) {
		if (right - left <= 96) {
			for (int i = left + 1, j; i < right; ++i) {
				final long tmp = array[i];
				long tmp2;
				for (j = i; j > left && (tmp2 = array[j - 1]) > tmp; --j)
					array[j] = tmp2;
				array[j] = tmp;
			}
			return;
		}
		int l = left;
		while (l < right && (array[l] & digit) == 0)
			++l;
		for (int r = l + 1; r < right; ++r) {
			final long i = array[r];
			if ((i & digit) == 0) {
				array[r] = array[l];
				array[l++ ] = i;
			}
		}
		if ((digit = Long.highestOneBit(use & digit - 1)) == 0) return;
		sort(array, left, l, use, digit);
		sort(array, l, right, use, digit);
	}
}

class IntMath {

	public static int gcd(int a, int b) {
		while (a != 0)
			if ((b %= a) != 0) a %= b;
			else return a;
		return b;
	}

	public static int gcd(final int... array) {
		int ret = array[0];
		for (int i = 1; i < array.length; ++i)
			ret = gcd(ret, array[i]);
		return ret;
	}

	public static long gcd(long a, long b) {
		while (a != 0)
			if ((b %= a) != 0) a %= b;
			else return a;
		return b;
	}

	public static long gcd(final long... array) {
		long ret = array[0];
		for (int i = 1; i < array.length; ++i)
			ret = gcd(ret, array[i]);
		return ret;
	}

	public static long lcm(final long a, final long b) {
		return a / gcd(a, b) * b;
	}

	public static int pow(final int a, int b) {
		int ans = 1;
		for (int mul = a; b > 0; b >>= 1, mul *= mul)
			if ((b & 1) != 0) ans *= mul;
		return ans;
	}

	public static long powLong(final long a, long b) {
		long ans = 1;
		for (long mul = a; b > 0; b >>= 1, mul *= mul)
			if ((b & 1) != 0) ans *= mul;
		return ans;
	}

	public static int pow(final int a, int b, final int mod) {
		if (b < 0) b = b % (mod - 1) + mod - 1;
		long ans = 1;
		for (long mul = a; b > 0; b >>= 1, mul = mul * mul % mod)
			if ((b & 1) != 0) ans = ans * mul % mod;
		return (int)ans;
	}

	public static int floorsqrt(final long n) {
		return (int)Math.sqrt(n + 0.1);
	}

	public static int ceilsqrt(final long n) {
		return n <= 1 ? (int)n : (int)Math.sqrt(n - 0.1) + 1;
	}
}
