Page not loading? Try clicking here.
Placeholder

#4763

복잡한 일반항 문제 1s 512MB

Problems

1 ≤​ An ≤​ N 범위에서 정의되는 수열 An은 다음과 같이 정의된다.

  • A1 = 1

  • A2 = 2

  • An = B[An-1][An-2] (n ≥ 3)

행렬 B와 K가 주어졌을 때, Ak의 값을 구하여라.​ 


Input

1번 줄 : N K

2번 ~ N + 1번 줄 : B[i][1] B[i][2] ... B[i][N]

제약조건

  • 2 ≤ N ≤ 500

  • 1 ≤ K ≤ 1,000,000,000,000,000,000 (1018)

  • 1 ≤ B[i][j] ≤ N

  • B[i][i] = 0

  • B[i][j] ≠ i​ 


Output

첫 번째 줄에 Ak의 값을 출력하여라.​


Example #1

2 4

0 2

1 0
2

A1 = 1, A2 = 2, A3 = 1, A4 = 2이다.


Example #2

4 7

0 4 3 2

4 0 4 1

2 1 0 1

3 2 3 0
3

A1 = 1, A2 = 2, A3 = 4, A4 = 2, A5 = 1, A6 = 4, A7 = 3이다.


Source

COCI 2020 Contest5 #2

You must sign in to write code.