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 CPP):

Solution:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

const ll MOD = 1e+9 + 7;
int n, m;
int memo[4][1010][2];
int node[1010][2];
vector<int> exist[1010];
int assign[1010];
bool visit[1010];
vector<int> g[1010];

int sign(int x) {
  if (x > 0) { return 1; }
  if (x < 0) { return -1; }
  return 0;
}
int OK(int index) {
  int x = abs(node[index][0]);
  int y = abs(node[index][1]);
  int ret = 0;
  if (assign[x] != 0) { ret |= sign(assign[x]) == sign(node[index][0]); }
  if (assign[y] != 0) { ret |= sign(assign[y]) == sign(node[index][1]); }
  return ret;
}

int calc(int sval, int from, int parent, int start) {
  visit[from] = true;
  int ok = OK(from);
  if (memo[sval][from][ok] != -1) { return memo[sval][from][ok]; }
  ll ret = 0;
  if (g[from].size() == 1) { return ok ? 2 : 1; }
  if (g[from].size() == 2 && g[from][0] == g[from][1]) {
    return ok ? 1 : 0;
  }
  FORIT(it, g[from]) {
    int to = *it;
    if (to == parent) { continue; }
    if (to == start) {
      ret = ok ? 1: 0;
      continue;
    }
    int target = -1;
    REP(i, 2) {
      REP(j, 2) {
        int x = abs(node[from][i]);
        int y = abs(node[to][j]);
        if (x == y) { target = x; }
      }
    }
    assert(assign[target] == 0);
    assign[target] = 1;
    ret = (ret + OK(from) * calc(sval, to, from, start)) % MOD;
    assign[target] = -1;
    ret = (ret + OK(from) * calc(sval, to, from, start)) % MOD;
    assign[target] = 0;
  }
  return memo[sval][from][ok] = ret;
}

int main() {
  while (scanf("%d %d", &n, &m) > 0) {
    MEMSET(memo, -1);
    MEMSET(assign, 0);
    MEMSET(visit, false);
    REP(i, 1010) {
      exist[i].clear();
      g[i].clear();
    }
    ll ans = 1;
    {
      int cnt = 0;
      REP(i, m) {
        int x, y;
        scanf("%d %d", &x, &y);
        if (x == y) { continue; }
        if (abs(x) == abs(y)) { ans = (ans * 2) % MOD; continue; }
        node[cnt][0] = x;
        node[cnt][1] = y;
        exist[abs(x)].push_back(cnt);
        exist[abs(y)].push_back(cnt);
        cnt++;
      }
      m = cnt;
    }
    REP(i, 1010) {
      if ((int)exist[i].size() <= 1) { continue; }
      int from = exist[i][0];
      int to = exist[i][1];
      g[from].push_back(to);
      g[to].push_back(from);
    }
    REP(iter, 3) {
      REP(i, m) {
        if (visit[i]) { continue; }
        if ((int)g[i].size() != iter) { continue; }
        visit[i] = true;
        if (g[i].empty()) { ans = (ans * 3) % MOD; continue; }
        ll lans = 0;
        REP(j, 4) {
          int x = abs(node[i][0]);
          int y = abs(node[i][1]);
          assign[x] = (j & 1) * 2 - 1;
          assign[y] = ((j >> 1) & 1) * 2 - 1;
          lans = (lans + OK(i) * calc(j, g[i][0], i, i)) % MOD;
        }
        ans = (ans * lans) % MOD;
      }
    }
    printf("%lld\n", ans);
  }
}