17084번 - f(k, n)

문제

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

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

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

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

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

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

택희 : ??

영훈 : ??

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

입력

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

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

출력

문제의 정답을 출력한다.

제한

힌트