You need to solve two independent (but similar) subproblems:

Problem 1: Given $n$ vectors of dimension $m$ over $\mathrm{GF}(3)$, let $V$ be the linear space spanned by these vectors. Find the number of ways to choose a set of vectors from the $n$ given vectors such that they form a basis for $V$. The result should be modulo $3$.

Problem 2: Given $n$ vectors of dimension $m$ over $\mathrm{GF}(2)$, let $V$ be the linear space spanned by these vectors. Each vector $i$ has a color $c_i$. Find the number of ways to choose exactly one vector from each color such that they form a basis for $V$. The result should be modulo $2$.

Note: To focus on the primary challenge, it is guaranteed that the dimension of $V$ is $m$.

Input

The first line contains a positive integer $taskid$, representing the problem number to be solved.

The second line contains two positive integers $n$ and $m$, with meanings as described above.

The next $n$ lines follow:

If $taskid = 1$, the $i$-th line contains $m$ non-negative integers $v_{i,1},v_{i,2},\dots,v_{i,m}$, describing the $i$-th vector.

If $taskid = 2$, the $i$-th line contains $m + 1$ non-negative integers $v_{i,1},v_{i,2},\dots,v_{i,m},c_i$, describing the $i$-th vector and its color.

Output

Output a single positive integer representing the answer.

Examples

Input 1

1
3 2
0 1
1 2
1 1

Output 1

0

Input 2

1
4 3
1 1 0
1 2 0
1 2 2
1 1 1

Output 2

1

Input 3

1
5 3
1 1 0
0 1 2
0 2 0
2 0 2
2 2 2

Output 3

2

Input 4

2
3 2
0 1 1
0 0 2
1 1 1

Output 4

0

Input 5

2
4 2
1 1 1
0 0 1
1 0 2
0 0 2

Output 5

1

Subtasks

For $100\%$ of the data, $taskid\in \{1, 2\}, 1 \leq n, m \leq 500$.

When $taskid = 1$, $v_{i,j}\in \{0,1,2\}$.

When $taskid = 2$, $v_{i,j}\in\{0, 1\}, c_i\in[1, m]$.

$\mathrm{subtask}\,1(50\,\mathrm{pts}) : taskid = 1$.

$\mathrm{subtask}\,2(50\,\mathrm{pts}) : taskid = 2$.