Dance

Sanggeun has been hooked on dancing for a few years. He has mastered swing, salsa, and hip hop, and now he wants to invent a new dance.

He plans to dance it for Jeongin at her wedding a month from now. N people dance, and there are N marks on the floor. Arrows are drawn between the marks: every mark has exactly one arrow leaving it, and exactly one arrow enters each mark. An arrow may lead back to the mark it starts from.

When the wedding begins, everyone picks a mark to stand on. Two people cannot stand on the same mark. Once the music starts they dance for 10 seconds, then move along the arrow to the next mark at Sanggeun's signal. Nobody bumps into anyone else while moving. A person standing on a mark whose arrow points back to that mark keeps dancing there.

A year has passed since Jeongin's wedding and another wedding is coming up. Sanggeun wants to perform the same dance, but he cannot find last year's arrangement of marks and arrows. He did find two wedding photos, one taken when the dance started and one taken when it ended. There were K signals in total, so everyone moved along an arrow exactly K times.

Given the two photos, write a program that counts how many ways the arrows can be drawn. Two ways are different if some mark has its arrow pointing to a different mark. The marks are numbered 1 to N as they appear in the first photo.

The first line contains N and K. ($2 \le N \le 10000$, $1 \le K \le 10^9$)

The second line contains N integers $a_1, a_2, \dots, a_N$ separated by spaces. ($1 \le a_i \le N$) $a_i$ is the number of the mark where the person who stood on mark i when the dance started was standing when the dance ended. Each number from 1 to N appears exactly once among $a_1$ through $a_N$.

Print the number of ways to draw the arrows, modulo 1,000,000,007. If no set of arrows produces the given arrangement after K moves, print 0.