시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 163 35 33 21.154%

문제

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

위 수열은 피보나치 수열로 너무 잘 알려져 있기 때문에 영훈이는 1 이상인 정수 n, 에 대한 함수 f(k, n) 를 다음과 같이 정의했다.

영훈이는 임의의 p×p 행렬 T가 주어졌을 때, 다음 조건을 만족시키는 순서쌍 (x, y)의 갯수가 궁금해졌다.

  • ti-1, j-1  := 행렬 Ti번째 행, j번째 열의 원소
  • f(x+i, y+j) = ti, j      (for all  0   i, j  < p)
  • 1 ≤  x, y    n - p + 1

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

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

택희 : ??

영훈 : ??

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

입력

첫째 줄에 np가 주어진다. (1 ≤ n ≤ 109, 1 ≤ p ≤ 1000)

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

출력

문제의 정답을 출력한다.

예제 입력 1

3 2
1 1
0 1

예제 출력 1

2

가능한 (x,y)는 (1,1), (2,2)이다.

예제 입력 2

7 3
1 1 2
0 1 1
1 0 1

예제 출력 2

5

예제 입력 3

1000000000 1
1

예제 출력 3

2999999997