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

见题面

见题面