ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1810. Antiequations

Time limit: 1.0 second
Memory limit: 64 MB
There is a system of linear antiequations modulo 3:
a11 · x1 + a12 · x2 + … + a1n · xnb1 mod 3
a21 · x1 + a22 · x2 + … + a2n · xnb2 mod 3

ak1 · x1 + ak2 · x2 + … + akn · xnbk mod 3
Find the number of different solutions of this system assuming that xi are integers and 0 ≤ xi ≤ 2.

Input

First line contains two integers: the amount of antiequations k and the amount of variables n (1 ≤ k, n ≤ 30). The i-th of the following k lines contains integers ai1, ai2, …, ain, bi (0 ≤ aij, bi ≤ 2).

Output

Output the number of solutions of the system.

Samples

inputoutput
3 3
2 2 1 1
2 1 0 0
1 2 2 2
8
4 3
2 2 1 1
2 1 0 0
1 2 2 2
1 0 1 2
6
Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010.