ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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.
Tags: none