Problem: Problem statement

$ (X_ {1,1} ∨X_ {1,2}) ∧ (X_ {2,1} ∨X_ {2,2}) ∧ ... ∧ (X_ {M, 1} ∨X_ {M,2 }) Given a logical expression represented by $. However, it is $ X_ {i, j} \ in \\ {x_1, x_2, ..., x_N, ~ x_1, ~ x_2, ..., ~ x_N \\} $.
I want to assign a boolean value to each variable $ x_i $ ($ 1 \ leq i \ leq N $) so that the given formula is true. Find out how many such allocations are available.

Constraint

* $ 1 \ leq N \ leq 1000 $
* $ N / 2 \ leq M \ leq N $
* $ 1 \ leq | Y_ {i, j} | \ leq N $
* Each variable appears only once or twice in the formula. That is, $ (i, i, j} = ~ x_k $ or $ X_ {i, j} = ~ x_k $ for any $ k $ ($ 1 \ leq k \ leq N $). j) There are only one or two pairs of $.



input

Input follows the following format. All given numbers are integers.


$ N $ $ M $
$ Y_ {1,1} $ $ Y_ {1,2} $
$ Y_ {2,1} $ $ Y_ {2,2} $
$ ... $
$ Y_ {M, 1} $ $ Y_ {M, 2} $

When $ Y_ {i, j}> 0 $, $ X_ {i, j} = x_ {Y_ {i, j}} $, and when $ Y_ {i, j} <0 $, $ X_ { i, j} = ~ x_ {-Y_ {i, j}} $.

output

Divide the remainder by dividing by $ 10 ^ 9 + 7 $ how many ways to assign the boolean value of each variable that makes the logical expression true, and output it on one line.

Examples

Input

2 1
1 -2


Output

3


Input

3 2
-1 -2
1 -3


Output

4

Solution (in JAVA):

Solution:
     

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

	static final int MOD = 1000000007;
	static Scanner sc = new Scanner(System.in);
	static int N, M;
	static int[][] pos;
	static int[][] Y;

	static long solveCycle(ArrayList<Cell> list) {
		long ret = 0;

		// start = 0
		long[][] dp = new long[list.size()][2];
		dp[0][0] = 0;
		dp[0][1] = 1;
		for (int i = 1; i < list.size(); ++i) {
			if (list.get(i - 1).s == list.get(i).f) {
				dp[i][0] = dp[i - 1][1];
			} else {
				dp[i][0] = dp[i - 1][0];
			}
			dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
		}
		if (list.get(list.size() - 1).s == list.get(0).f) {
			ret += dp[list.size() - 1][0];
		} else {
			ret += dp[list.size() - 1][1];
		}

		// start = 1
		dp = new long[list.size()][2];
		dp[0][0] = 1;
		dp[0][1] = 1;
		for (int i = 1; i < list.size(); ++i) {
			if (list.get(i - 1).s == list.get(i).f) {
				dp[i][0] = dp[i - 1][1];
			} else {
				dp[i][0] = dp[i - 1][0];
			}
			dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
		}
		if (list.get(list.size() - 1).s == list.get(0).f) {
			ret += dp[list.size() - 1][1];
		} else {
			ret += dp[list.size() - 1][0];
		}

		return ret % MOD;
	}

	static long solveChain(ArrayList<Cell> list) {
		long[][] dp = new long[list.size()][2];
		dp[0][0] = 1;
		dp[0][1] = 2;
		for (int i = 1; i < list.size(); ++i) {
			if (list.get(i - 1).s == list.get(i).f) {
				dp[i][0] = dp[i - 1][1];
			} else {
				dp[i][0] = dp[i - 1][0];
			}
			dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
		}
		return (dp[list.size() - 1][0] + dp[list.size() - 1][1]) % MOD;
	}

	public static void main(String[] args) {
		N = sc.nextInt();
		M = sc.nextInt();
		pos = new int[N + 1][2];
		Y = new int[M][2];
		for (int[] a : pos) {
			Arrays.fill(a, -1);
		}
		for (int i = 0; i < M; ++i) {
			Y[i][0] = sc.nextInt();
			int x = Math.abs(Y[i][0]);
			if (pos[x][0] == -1) {
				pos[x][0] = i;
			} else {
				pos[x][1] = i;
			}
			Y[i][1] = sc.nextInt();
			x = Math.abs(Y[i][1]);
			if (pos[x][0] == -1) {
				pos[x][0] = i;
			} else {
				pos[x][1] = i;
			}
		}
		boolean[] used = new boolean[M];
		long ans = 1;
		for (int i = 0; i < M; ++i) {
			if (Math.abs(Y[i][0]) == Math.abs(Y[i][1])) {
				used[i] = true;
				if (Y[i][0] == -Y[i][1]) {
					ans *= 2;
					ans %= MOD;
				}
			}
		}
		while (true) {
			boolean update = false;
			for (int i = 0; i < M; ++i) {
				if (used[i]) continue;
				update = true;
				ArrayList<Cell> forward = new ArrayList<Cell>();
				ArrayList<Cell> backward = new ArrayList<Cell>();
				forward.add(new Cell(Y[i][0], Y[i][1]));
				used[i] = true;

				boolean cycle = false;
				int cur = i;
				int x = Math.abs(Y[cur][1]);
				while (true) {
					int otherI = pos[x][0] == cur ? 1 : 0;
					if (pos[x][otherI] == -1) break;
					cur = pos[x][otherI];
					if (used[cur]) {
						cycle = true;
						break;
					}
					used[cur] = true;
					int inI = x == Math.abs(Y[cur][0]) ? 0 : 1;
					x = Math.abs(Y[cur][1 - inI]);
					forward.add(new Cell(Y[cur][inI], Y[cur][1 - inI]));
				}
				if (cycle) {
					ans *= solveCycle(forward);
					ans %= MOD;
					continue;
				}

				cur = i;
				x = Math.abs(Y[cur][0]);
				while (true) {
					int otherI = pos[x][0] == cur ? 1 : 0;
					if (pos[x][otherI] == -1) break;
					cur = pos[x][otherI];
					if (used[cur]) {
						throw new RuntimeException();
					}
					used[cur] = true;
					int inI = x == Math.abs(Y[cur][0]) ? 0 : 1;
					x = Math.abs(Y[cur][1 - inI]);
					backward.add(new Cell(Y[cur][1 - inI], Y[cur][inI]));
				}
				Collections.reverse(backward);
				backward.addAll(forward);
				ans *= solveChain(backward);
				ans %= MOD;
			}
			if (!update) break;
		}
		System.out.println(ans);
	}

	static class Cell {
		int f;
		int s;

		Cell(int f, int s) {
			this.f = f;
			this.s = s;
		}
	}

}