Cho \(N\) biến nhị phân \(x_1,x_2,...,x_N\).

Mỗi biến chỉ nhận một trong hai giá trị:

• \(0\)
• \(1\)

Có \(M\) ràng buộc. Mỗi ràng buộc có dạng \((a_1x_1 + a_2x_2 + ... + a_Nx_N) \bmod 2 = b\)

Trong đó:

• \(a_i\) và \(b\) chỉ có thể là \(0\) hoặc \(1\).
• Phép cộng được thực hiện thông thường, sau đó lấy phần dư modulo \(2\).

Hãy tính số bộ giá trị \((x_1,x_2,...,x_N)\) thỏa mãn tất cả các ràng buộc, kết quả lấy modulo \(1000000007\).

Input

Dòng đầu tiên chứa hai số nguyên \(N,\ M\).

Trong đó:

• \(N\) là số biến.
• \(M\) là số phương trình.

\(M\) dòng tiếp theo, mỗi dòng chứa \(N+1\) số nguyên \(a_1\ a_2\ ...\ a_N\ b\)

Output

• In ra số lượng nghiệm của hệ phương trình modulo \(1000000007\).

Constraints

• \(1 \le N \le 2000\)
• \(1 \le M \le 2000\)
• \(a_i,b \in \{0,1\}\)

Example

3 3
1 1 0 1
0 1 1 0
1 0 1 1

2