题目内容

连锁店统计 $n$ 家门店连续 $k$ 天的盈亏，单位是元。正数表示当天盈利，负数表示当天亏损。

两条记录属于同一类，当且仅当存在整数 $r$、$d$（$0 \le r < k$），把其中一条循环左移 $r$ 位，再将每个数加上 $d$，得到的结果与另一条逐项相同。循环左移 $1$ 位是把第一个数移到末尾，其余数依次前移。$r=0$ 表示不移动。$d$ 可以为负或 $0$。

求不同类的个数。

输入描述

第一行两个整数 $n$、$k$。

接下来 $n$ 行，每行 $k$ 个整数，表示一家门店 $k$ 天的盈亏。

约束

$1 \le n \le 2 \times 10^4$

$1 \le k \le 20$

$-10^9 \le$ 每天的盈亏 $\le 10^9$

输出描述

输出一个整数，为不同类的个数。

样例1

输入

4 3
3 -1 2
5 -2 0
0 0 0
-1 2 3

输出

3

说明

第一条 $3,-1,2$ 循环左移 $1$ 位得到 $-1,2,3$，与第四条相同。

第二条 $5,-2,0$ 与第一条对不上：

• $3,-1,2$ 加 $2$ 得到 $5,1,4$；
• $-1,2,3$ 加 $6$ 得到 $5,8,9$；
• $2,3,-1$ 加 $3$ 得到 $5,6,2$。

第三条 $0,0,0$ 也对不上：

• $3,-1,2$ 加 $-3$ 得到 $0,-4,-1$；
• $-1,2,3$ 加 $1$ 得到 $0,3,4$；
• $2,3,-1$ 加 $-2$ 得到 $0,1,-3$。

第二条、第三条各自成类。一共 $3$ 类。

样例2

输入

3 4
2 -3 1 4
4 7 5 0
-2 0 1 5

输出

2

说明

第一条 $2,-3,1,4$ 循环左移 $2$ 位得到 $1,4,2,-3$，每个数再加 $3$，得到 $4,7,5,0$，与第二条相同。

第三条 $-2,0,1,5$ 与第一条的四种左移都对不上：

• $2,-3,1,4$ 加 $-4$，得到 $-2,-7,-3,0$；
• $-3,1,4,2$ 加 $1$，得到 $-2,2,5,3$；
• $1,4,2,-3$ 加 $-3$，得到 $-2,1,-1,-6$；
• $4,2,-3,1$ 加 $-6$，得到 $-2,-4,-9,-5$。

因此一共 $2$ 类。