Paleta

Ο μικρός Mirko περνά τον ελεύθερο χρόνο του ζωγραφίζοντας. Για αυτό το χόμπι, του αρέσει να χρησιμοποιεί πινέλα και μια παλέτα που περιέχει συνολικά K χρώματα. Ο φίλος του Slavko αποφάσισε να χρησιμοποιήσει το ταλέντο του Mirko και του έδωσε το νέο του βιβλίο ζωγραφικής για να χρωματίσει ο Mirko. Το βιβλίο ζωγραφικής περιέχει ~N~ εικόνες με αριθμημένες ως ~1,\;2,\;\ldots\;,\;N~.

Ο Mirko αποφάσισε να ζωγραφίσει κάθε εικόνα σε ένα ακριβώς χρώμα από τα πιθανά ~K~ χρώματα από την παλέτα του. Ωστόσο, του αρέσουν πολύ τα πολύχρωμα πράγματα. Επέλεξε ~N~ αριθμούς ~f_i~ και αποφάσισε να ζωγραφίσει την εικόνα αριθμημένη ~i~ διαφορετικά από τις εικόνες αριθμημένες ~f_i~, εκτός από την περίπτωση που ~f_i = i~. Αν ~f_i = i~, αυτό σημαίνει ότι μπορεί να ζωγραφίσει την εικόνα με αριθμό ~f_i~ όποιο χρώμα του αρέσει, αρκεί να πληρούνται όλες οι άλλες προϋποθέσεις.

Ο Mirko θέλει να μάθει τον αριθμό των πιθανών τρόπων για να χρωματίσει το βιβλίο ζωγραφικής του Slavko και χρειάζεται απεγνωσμένα τη βοήθειά σας! Υπολογίστε τον αριθμό των πιθανών τρόπων χρωματισμού του βιβλίου. Δεδομένου του γεγονότος ότι η έξοδος μπορεί να είναι πολύ μεγάλη, εκτυπώστε την απάντηση modulo (το υπόλοιπο της διαίρεσης με) ~1\,000\,000\,007~.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει θετικούς ακέραιους ~N,\;K\;(1 \leq N,\;K \leq 1\,000\,000)~.
Η επόμενη γραμμή περιέχει ~N~ αριθμούς ~f_i\;(1 \leq f_i \leq N)~, τον αριθμό που αναφέρεται στο κείμενο.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον αριθμό των πιθανών τρόπων χρωματισμού του βιβλίου του Slavko.

Βαθμολογία

Σε δεδομένα δοκιμής αξίας ~50~% των συνολικών πόντων, όλοι οι αριθμοί ~f_i~ θα είναι διαφορετικοί.

Παραδείγματα

input

2 3
2 1

output

6

Επεξήγηση του 1ου παραδείγματος:

Ο Mirko έχει τρία χρώματα και αποφάσισε ότι η εικόνα με αριθμό 2 δεν πρέπει να είναι του ίδιου χρώματος με την εικόνα με αριθμό 1. Οι πιθανοί χρωματισμοί είναι ~(1,\;2),\;(1,\;3),\;(2,\;1),\;(2,\;3),\;(3,\;1),\;(3,\;2)~, όπου ο πρώτος αριθμός στις παρενθέσεις αντιπροσωπεύει το χρώμα της πρώτης εικόνας και ο δεύτερος αριθμός το χρώμα της δεύτερης εικόνας.

input

3 4
2 3 1

output

24

Επεξήγηση του 2ου παραδείγματος:

Ο Mirko έχει τέσσερα χρώματα. Δεν υπάρχουν προϋποθέσεις σχετικά με την πρώτη εικόνα, μπορεί να βαφτεί σε οποιοδήποτε χρώμα. Το δεύτερο πρέπει να είναι διαφορετικό από το πρώτο και το τρίτο διαφορετικό από το δεύτερο. Αυτό σημαίνει ότι αυτές οι δύο εικόνες μπορούν να χρωματιστούν με τα υπόλοιπα 3 χρώματα. Αυτό μας δίνει συνολικά 36 συνδυασμούς.

input

3 4
2 1 1

output

36

input

3 4
1 1 2

output

36