Bojanje

Ο Oliver είναι μια λαστιχένια πάπια που όχι μόνο βρίσκει ζωύφια, αλλά του αρέσει και να ζωγραφίζει. Ο τελευταίος του πίνακας έχει ~n~ μέρη, το καθένα χρωματισμένο με ένα μοναδικό χρώμα. Αφού δέχτηκε πολλές κριτικές, η ζωγραφική του είναι πολύ προβλέψιμη και αποφάσισε να τροποποιήσει τη ζωγραφική του σε επαναλήψεις. Σε κάθε επανάληψη θα κάνει τα εξής βήματα:

1. Ο Oliver θα επιλέξει ομοιόμορφα τυχαία έναν δείκτη ~i (1 \le i \le n)~ και θα απομνημονεύσει το χρώμα στο ~i~-οστό μέρος του πίνακα.
2. Και πάλι, ο Oliver θα επιλέξει ομοιόμορφα τυχαία έναν δείκτη ~j (1 \le j \le n)~. Θα ξαναβάψει το ~i~-οστό μέρος του πίνακα με το χρώμα του ~i~-οστού μέρους του πίνακα. Εάν το ~j~-οστό μέρος είναι ήδη βαμμένο σε αυτό το χρώμα, δεν υπάρχει καμία αλλαγή. Σημειώστε ότι το ~i~ μπορεί να είναι ίσο με ~j~.

Τώρα, ο Oliver φοβάται ότι η ζωγραφική του θα γίνει μονότονη ή βαρετή. Θεωρεί έναν πίνακα καλό αν υπάρχουν τουλάχιστον ~k~ διαφορετικά χρώματα πάνω του. Βοηθήστε το να υπολογίσει την πιθανότητα η ζωγραφική του να είναι καλή στο τέλος.

Είσοδος

Η πρώτη γραμμή περιέχει τους αριθμούς ~n~, ~t~ και ~k~ ~(2 \le k \le n \le 10, 1 \le t \le 10^{18})~.

Έξοδος

Στην πρώτη και μοναδική γραμμή τυπώνετε την απάντηση σε modulo ~10^9 + 7~.

Τυπικά, έστω ~m = 10^9 + 7~. Μπορεί να φανεί ότι η απάντηση μπορεί να εκφραστεί ως μη αναγωγικό κλάσμα ~\frac{p}{q}~, όπου ~p~ και ~q~ είναι ακέραιοι και ~q \not\equiv 0~ (mod ~m~). Έξοδος ακέραιος αριθμός ίσος με ~p \cdot q^{-1}~ mod ~m~. Με άλλα λόγια, τυπώστε έναν τέτοιο ακέραιο ~x~ ώστε ~0 \le x < m~ και ~x \cdot q \equiv p~ (mod ~m~).

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	30	~k = n~
2	40	~t \le 1000~
3	40	Κανένας επιπλέον περιορισμός.

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

input

2 1 2

output

500000004

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

Στον πίνακα υπάρχουν δύο χρώματα, άρα η πιθανότητα να παραμείνει ίδιο μετά από μία επανάληψη είναι ~\frac{1}{2}~.

input

10 2 5

output

1

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

Μετά από δύο επαναλήψεις, ο αριθμός των διαφορετικών χρωμάτων δεν μπορεί να πάει από ~10~ σε λιγότερο από ~5~, επομένως σε κάθε περίπτωση ο πίνακας θα έχει τουλάχιστον ~5~ διαφορετικά χρώματα.

input

3 141592653589793 2

output

468261332