f(k, n)

1 이상의 정수 $n$에 대하여 수열 $fib(n)$은 다음과 같이 정의되어 있다.

피보나치 수열은 너무 잘 알려져 있으므로, 영훈이는 1 이상의 정수 $k$, $n$에 대한 함수 $f(k, n)$을 다음과 같이 정의했다.

영훈이는 임의의 $p \times p$ 행렬 $T$가 주어졌을 때, 다음 조건을 만족하는 순서쌍 $(x, y)$의 개수가 궁금해졌다.

• $t_{i-1, j-1}$: 행렬 $T$의 $i$번째 행, $j$번째 열의 원소
• $f(x+i, y+j) = t_{i,j}$ (모든 $0 \le i, j < p$에 대하여)
• $1 \le x, y \le n - p + 1$

택희: "...이 문제는 수학 지식을 너무 많이 요구하니 출제하지 말자."

영훈: "아냐, 잘 봐. 이게 무슨 뜻이냐면.."

택희: "??"

영훈: "??"

택희: "괜찮은 문제였구나.."

첫째 줄에 $n$, $p$가 주어진다. ($1 \le n \le 10^9$, $1 \le p \le 1000$)

둘째 줄부터 $p$개의 줄에 걸쳐 $p$개의 정수가 주어진다. 이 중 $i$번째 줄 $j$번째 정수는 $t_{i-1, j-1}$을 의미하며, 모두 절댓값이 $10^{18}$ 이하인 정수이다.

문제의 정답을 출력한다.