Janje

Ο νεαρός Bojan,, σήμερα επιτυχημένος φοιτητής ηλεκτρολόγων μηχανικών, λάτρευε το χρωματισμό από τότε που ήταν μικρό αγόρι. Ενθυμούμενος ανέμελες μέρες από την παιδική του ηλικία, αποφάσισε να αγοράσει ένα βιβλίο ζωγραφικής και ~K~ χρώματα και να πιάσει δουλειά. Είναι ενδιαφέρον ότι στον Bojan δεν αρέσουν οι πολύχρωμες εικόνες, γι' αυτό αποφάσισε να χρωματίσει κάθε εικόνα χρησιμοποιώντας το πολύ τρία διαφορετικά χρώματα. Επιπλέον, ο Bojan δεν θα χρωματίσει ποτέ δύο γειτονικές περιοχές χρησιμοποιώντας το ίδιο χρώμα, επειδή, όπως το θέτει, "σε τι χρησιμεύει αυτή η γραμμή στο μεταξύ;" Δύο περιοχές θεωρούνται γειτονικές εάν οι άκρες τους έχουν τουλάχιστον ένα σημείο άρθρωσης. Για παράδειγμα, οι περιοχές που συμβολίζονται με το 4 και το 3 (δείτε την παρακάτω εικόνα) είναι γειτονικές, ενώ οι περιοχές 1 και 2 δεν είναι. Επιπλέον, ο χρωματισμός της παρακάτω εικόνας είναι σύμφωνος με όλες τις απαιτήσεις του Bojan.

Πριν αρχίσει να χρωματίζει μια εικόνα, ο Bojan, αναρωτιέται με πόσους τρόπους μπορεί να χρωματίσει αυτήν την εικόνα, ώστε να πληροί όλες τις προϋποθέσεις του. Δεδομένου του γεγονότος ότι ο Bojan σπουδάζει ηλεκτρολόγος μηχανικός, είναι κατανοητό ότι η συνδυαστική δεν είναι το δυνατό του σημείο, οπότε σας ζήτησε βοήθεια.

Είσοδος

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

Μπορείτε να βρείτε το βιβλίο ζωγραφικής με τις αριθμημένες εικόνες στην επόμενη σελίδα.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον αριθμό των τρόπων με τους οποίους ο Bojan μπορεί να χρωματίσει τη \(Ν\)-οστή εικόνα από το βιβλίο ζωγραφικής εάν έχει στη διάθεσή του ~K~ διαφορετικά χρώματα. Δύο χρωματισμοί είναι διαφορετικοί εάν διαφέρουν ως προς το χρώμα σε τουλάχιστον μία περιοχή.

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

input

2 2

output

0

input

7 3

output

96

                    Εικόνα 2. Ένα εξοχικό στη θάλασσα            Εικόνα 3. Ένα πολύ γνωστό λογότυπο

                  Εικόνα 4. Φρόστι ο Χιονάνθρωπος              Εικόνα 5. Μια αφηρημένη μπάλα

                            Εικόνα 6. Πυραμίδα                Εικόνα 7. Μαργαρίτα

Εικόνα 8. Τραμπολίνο (το γκρι μέρος δεν θεωρείται περιοχή και δεν πρέπει να είναι χρωματισμένο)