댄스

상근이는 몇 년 전부터 춤에 빠져 있다. 스윙, 살사, 힙합을 모두 마스터했고, 이제 새로운 춤을 만들려고 한다.

상근이는 한 달 뒤에 열리는 정인이의 결혼식에서 정인이를 위해 이 춤을 출 생각이다. 춤은 N명이 추고, 바닥에는 마크가 N개 표시되어 있다. 마크 사이에는 화살표가 그려져 있는데, 마크마다 나가는 화살표가 하나씩 있고 각 마크로 들어오는 화살표도 하나뿐이다. 자기 자신으로 돌아오는 화살표도 있을 수 있다.

결혼식이 시작할 때 모든 사람은 처음에 설 마크를 고른다. 한 마크 위에 두 사람이 설 수는 없다. 음악이 시작되면 10초 동안 춤을 추다가 상근이의 신호에 맞춰 화살표를 따라 다음 마크로 옮겨 간다. 이동하는 동안 사람끼리 부딪히는 일은 없다. 자기 자신을 향하는 화살표 위에 서 있던 사람은 그 마크에서 계속 춤을 춘다.

정인이의 결혼식으로부터 일 년이 지났고, 새로운 결혼식이 다가오고 있다. 상근이는 이번 결혼식에서도 그때 췄던 춤을 추려고 하지만, 작년의 마크와 화살표 배치를 찾지 못했다. 다행히 결혼식 사진 중에서 춤이 시작할 때 찍은 사진과 끝났을 때 찍은 사진을 찾았다. 신호는 모두 K번 있었다. 즉, 사람들은 화살표를 따라 K번 이동했다.

두 사진이 주어졌을 때, 화살표를 그리는 방법이 몇 가지인지 구하는 프로그램을 작성하시오. 마크 하나라도 화살표가 가리키는 마크가 다르면 서로 다른 방법으로 센다. 마크 번호는 첫 사진을 기준으로 1번부터 N번까지 붙였다.

첫째 줄에 N과 K가 주어진다. ($2 \le N \le 10000$, $1 \le K \le 10^9$)

둘째 줄에는 공백으로 구분된 정수 $a_1, a_2, \dots, a_N$이 주어진다. ($1 \le a_i \le N$) $a_i$는 춤이 시작할 때 i번 마크 위에 서 있던 사람이 춤이 끝났을 때 서 있던 마크의 번호이다. $a_1$부터 $a_N$까지에는 1부터 N까지의 수가 한 번씩 나타난다.

화살표를 그리는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다. K번 이동해서 주어진 배치를 만들 수 있는 화살표가 없으면 0을 출력한다.