問題文

$N$ 人の人がじゃんけんをします。このじゃんけんには $0, 1, 2$ の $3$ 種類の手があります。

このじゃんけんにおける引き分けを、出た手が $2$ 種類以外のときと定義します。つまり、出た手が $1$ 種類だけのときと、 $3$ 種類すべて出たときは引き分けです。

このじゃんけんをする人たちは、パターンが好きなので、全員あるパターンに沿って手を出します。 $i$ 番目の人は、長さ $M_i$ のパターン $A_{i0}, A_{i1}, \ldots, A_{iM_i}$ に沿って、 $j$ 回目には $A_{i(j \bmod M_i)}$ を出します。

$K$ 回じゃんけんをしたとき、引き分けが何回あったか答えてください。

制約

• $1 \le N \le 1000$
• $1 \le M_i \le 10$
• $0 \le A_{ij} \lt 3$
• $1 \le K \le 10^{18}$
• 入力はすべて整数である

入力

出力

答えを $1$ 行に出力せよ。

入出力例

2 10
3 2
0 1 2
0 1

4

出た手を順番に見ると、 $\{0\}, \{1\}, \{0, 2\}, \{0, 1\}, \{0, 1\}, \{1, 2\}, \{0\}, \{1\}, \{0, 2\}, \{0, 1\}$ です。このうち、手が $2$ 種類でない回は $4$ 回あります。

3 5
1 2 3
0
1 2
2 0 1

1

出た手を順番に見ると、 $\{0, 1, 2\}, \{0, 2\}, \{0, 1\}, \{0, 2\}, \{0, 1\}$ となります。 $\{0, 1, 2\}$ のときも引き分けとなることに注意してください。

10 1000000000000000000
1 2 3 4 5 6 7 8 9 10
1
2 0
2 1 2
2 0 2 1
2 2 1 1 2
1 1 0 2 1 2
1 1 0 2 2 1 1
0 2 0 1 2 0 2 2
2 1 2 0 1 1 2 1 0
0 0 0 1 0 2 1 0 2 1

928571428571428570