33ος ΠΔΠ Καμπ (κοινά)
ROOMALLOC (roomalloc)

Οι μαθητές¹ μίας τάξης ενός σχολείου σχεδιάζουν την πενθήμερη εκδρομή τους. Η τάξη αποτελείται από \(N\) μαθητές, αριθμημένους από το \(1\) έως και το \(N\). Το ξενοδοχείο στο οποίο θα μείνουν έχει \(K\) δωμάτια, αριθμημένα από το \(1\) έως και το \(K\). Κάθε μαθητής θα πάει σε κάποιο από αυτά τα δωμάτια. Όπως ίσως ξέρετε, στις πενθήμερες εκδρομές οι μαθητές ενδιαφέρονται περισσότερο να πάνε στο δωμάτιο που είναι οι φίλοι τους — δεν τους ενδιαφέρει πολύ η χωρητικότητα των δωματίων και γι’ αυτό θα υποθέσουμε σε αυτό το πρόβλημα ότι μπορούν να χωρέσουν και όλοι οι μαθητές στο ίδιο δωμάτιο.

Οι προσωπικές σχέσεις των μαθητών είναι περίπλοκες. Ορισμένοι μαθητές έχουν κάποιον άλλο μαθητή που αντιπαθούν (ακριβώς έναν, σε αυτό το πρόβλημα) και δεν πρόκειται να καταλήξουν στο ίδιο δωμάτιο που βρίσκεται αυτός.

Βρείτε με πόσους διαφορετικούς τρόπους είναι δυνατό να καταλήξουν οι μαθητές σε δωμάτια. Δύο τρόποι θεωρούνται διαφορετικοί αν τουλάχιστον ένας μαθητής καταλήγει σε διαφορετικό δωμάτιο.

Αρχεία Εισόδου (roomalloc.in):

Η πρώτη γραμμή της εισόδου θα περιέχει δύο θετικούς ακέραιους αριθμούς \(N\) και \(K\), χωρισμένους με ένα κενό διάστημα: το πλήθος των μαθητών και το πλήθος των δωματίων. Η επόμενη γραμμή θα περιέχει \(N\) ακέραιους αριθμούς \(F_1, F_2, \ldots F_N\) χωρισμένους ανά δύο με ένα κενό διάστημα, τέτοιους ώστε \(1 \leq F_i \leq N\).

Αν \(F_i = j \neq i\), αυτό σημαίνει ότι ο μαθητής \(i\) αντιπαθεί το μαθητή \(j\) και δε θα καταλήξει στο ίδιο δωμάτιο με εκείνον. Αν \(F_i = i\), αυτό σημαίνει ότι ο μαθητής \(i\) δεν αντιπαθεί κανέναν άλλο μαθητή.

Αρχεία Εξόδου (roomalloc.out):

Η έξοδος πρέπει να περιέχει μία γραμμή με ακριβώς έναν ακέραιο αριθμό: το πλήθος των δυνατών τρόπων με τους οποίους μπορεί να καταλήξουν οι μαθητές στα δωμάτια. Επειδή ο αριθμός αυτός μπορεί να είναι πολύ μεγάλος, ζητείται να τυπώσετε το υπόλοιπο της ακέραιας διαίρεσής του (modulo) με τον αριθμό \(10^9 + 7\).

Παραδείγματα Αρχείων Εισόδου - Εξόδου:

1^o

roomalloc.in	roomalloc.out
2 3 2 1	6

Εξήγηση 1^ου παραδείγματος: Υπάρχουν \(2\) μαθητές και \(3\) δωμάτια. Οι μαθητές αντιπαθούν ο ένας τον άλλον, άρα πρέπει να πάνε σε διαφορετικό δωμάτιο. Οι δυνατές αντιστοιχίσεις είναι: \((1, 2)\), \((1, 3)\), \((2, 1)\), \((2, 3)\), \((3, 1)\), \((3, 2)\), όπου οι αριθμοί μέσα στις παρενθέσεις είναι τα δωμάτια των δύο μαθητών, αντίστοιχα.

2^o

roomalloc.in	roomalloc.out
3 4 2 3 1	24

3^o

roomalloc.in	roomalloc.out
3 4 2 1 1	36

Περιορισμοί:

\(1 \leq N, K \leq 1.000.000\).
Όριο χρόνου εκτέλεσης: \(1\) sec.
Όριο μνήμης: \(64\) MB.

Subtasks

Για περιπτώσεις ελέγχου συνολικής αξίας 30%, θα είναι \(1 \leq N, K \leq 10\).
Για περιπτώσεις ελέγχου συνολικής αξίας 60%, θα είναι \(1 \leq N \leq 1.000\) και \(1 \leq K \leq 20\).
Για περιπτώσεις ελέγχου συνολικής αξίας 59%, οι αριθμοί \(F_i\) θα είναι όλοι διαφορετικοί.