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

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions: