Sharp 2SAT

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

inputFormat

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}}$.

outputFormat

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

样例

3 2
-1 -2
1 -3

4