To read the problem statement in English, choose the language using the flag on the navigation bar.

FireGhost và những người bạn đang lên kế hoạch du lịch ở thành phố VNOI!

Có ~n~ điểm du lịch nổi tiếng trong thành phố. Để lên kế đi hoạch du lịch, những người bạn cần lên danh sách các địa điểm sẽ thăm quan. Vì vậy có tổng cộng ~2^n~ kế hoạch du lịch khác nhau, từ không thăm quan một địa điểm nào cả, cho đến thăm quan tất cả các địa điểm trong thành phố.

Tuy nhiên, không phải kế hoạch nào cũng làm hài lòng tất cả các bạn. FireGhost có ~m~ người bạn. Mỗi người sẽ có một danh sách các nguyện vọng, trong đó mỗi nguyện vọng sẽ có dạng "Tôi muốn tham quan điểm du lịch thứ ~p~" hoặc "Tôi không muốn tham quan điểm du lịch thứ ~p~". May mắn thay, mọi người đều dễ tính, nên mỗi người bạn sẽ cảm thấy hài lòng về chuyến đi khi ít nhất một nguyện vọng của mình được thỏa mãn trong kế hoạch du lịch.

FireGhost tò mò muốn biết có bao nhiêu cách để làm hài lòng tất cả bạn bè, các bạn hãy giúp FireGhost nhé!

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n \le 10^5~, ~1 \le m \le 20~) lần lượt là số điểm du lịch và số người bạn của FireGhost.

Dòng thứ ~i~ trong ~m~ dòng tiếp theo bắt đầu bằng số nguyên dương ~k~ (~1 \leq k \leq n~) là số nguyện vọng của người bạn thứ ~i~, và theo sau là ~k~ số nguyên ~a_1, a_2, \ldots, a_k~ (~1 \le |a_j| \le n~) là mô tả các nguyện vọng.

• nếu ~a_j > 0~, người bạn thứ ~i~ có nguyện vọng tham quan địa điểm ~a_j~.

• ngược lại, nếu ~a_j < 0~, người bạn thứ ~i~ có nguyện vọng không tham quan địa điểm ~|a_j|~.

Dữ liệu đảm bảo ~|a_{u}| \neq |a_{v}|~ với mọi ~1 \le u < v \le k~.

Output

Một dòng duy nhất chứa số lượng kế hoạch du lịch làm hài lòng tất cả bạn bè của FireGhost. Vì số lượng kế hoạch có thể rất lớn, in ra kết quả theo modulo ~10^9 + 7~.

Scoring

• Subtask 1, tương ứng với ~30~ điểm, có ~n \leq 20~ và ~m \leq 5~

• Subtask 2, tương ứng với ~94~ điểm, có ~n \leq 10^3~ và ~m \leq 15~

• Subtask 3, tương ứng với ~180~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán có ~304~ điểm.

Sample Input 1

4 2
2 1 -4
1 3

Sample Output 1

6

Sample Input 2

7 1
2 -2 6

Sample Output 2

96

Sample Input 3

6 3
3 1 4 -2
2 2 3
3 -5 2 -6

Sample Output 3

36

Notes

Ở test mẫu đầu tiên, những kế hoạch du lịch sau (danh sách các địa điểm) sẽ làm hài lòng tất cả bạn bè:

1. ~\{3\}~,

2. ~\{1, 3\}~,

3. ~\{2, 3\}~,

4. ~\{1, 2, 3\}~,

5. ~\{1, 3, 4\}~,

6. ~\{1, 2, 3, 4\}~.

Các kế hoạch du lịch còn lại sẽ làm ai đó không hài lòng. Ví dụ:

• Kế hoạch ~\{3, 4\}~ sẽ làm cho người bạn đầu tiên không hài lòng, vì bạn đầu tiên không muốn thăm quan địa điểm thứ ~4~.

• Kế hoạch ~\{1\}~ sẽ làm bạn thứ hai không hài lòng, khi mà địa điểm duy nhất mà bạn thứ hai muốn tham quan là địa điểm thứ ~3~.

• Kế hoạch ~\{4\}~ không làm ai hài lòng cả.