Kocke

Για τα δέκατα τρίτα γενέθλιά του, οι γονείς του Ντόναλντ του αγόρασαν ένα ολοκαίνουργιο σετ από κυβάκια Lego. Στο σετ υπάρχουν ~n~ κυβάκια ίσου μεγέθους, όπου το ~i~-οστό κυβάκι είναι χρώματος ~i~. Χρησιμοποιώντας αυτά τα κυβάκια αποφάσισε να χτίσει ένα τείχος.

Ο Ντόναλντ θα χτίσει το τείχος του πάνω σε μια βάση Lego που μοιάζει με σειρά και έχει ~k~ θέσεις όπου μπορούν να τοποθετηθούν κυβάκια.

Τοποθετεί τα κυβάκια με τον ακόλουθο τρόπο:

• Πρώτον, τοποθετεί το κυβάκι με χρώμα ~1~ σε ένα τυχαίο σημείο στη βάση.
• Κάθε κυβάκι από το ~2~ έως το ~n~, το τοποθετεί σε ένα σημείο που να γειτονεύει με τη θέση που είχε τοποθετηθεί κυβάκι προηγουμένως. Αν το σημείο αυτό δεν είναι άδειο, τοποθετεί το νέο κυβάκι πάνω από όλα τα άλλα.

Αφού έχτισε τον τοίχο, ο Ντόναλντ έγραψε σε ένα χαρτί μια ακολουθία μήκους ~k~: στην ~i~-οστή θέση της ακολουθίας έγραψε το χρώμα του κορυφαίου κύβου στην ~i~-οστή θέση του τέιχους, ή ~0~ αν δεν υπάρχει κυβάκι στη θέση αυτή.

Αμέσως αναρωτήθηκε πόσες διαφορετικές ακολουθίες θα μπορούσε να έχει γράψει στο χαρτί. Δύο ακολουθίες θεωρούνται διαφορετικές αν υπάρχει μια θέση στην οποία διαφέρουν. Μετά από κάποιο χρονικό διάστημα, κατάφερε να υπολογίσει τη λύση, αλλά δεν είναι σίγουρος αν είναι σωστή, γι' αυτό ζητάει τη βοήθειά σας.

Είσοδος

Η μια και μοναδική γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~n~ και ~k\;(2 \le n,k \le 5000)~, τον αριθμό των κύβων και το μήκος της βάσης.

Έξοδος

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

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~20~	~n,\;k \le 18~
~2~	~30~	~n,\;k \le 50~
~3~	~30~	~n,\;k \le 500~
~4~	~30~	Κανένας επιπλέον περιορισμός.

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

input

4 3

output

8

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

Όλες οι πιθανές ακολουθίες είναι: ~(0,\;3,\;4)~, ~(2,\;3,\;4)~, ~(0,\;4,\;3)~, ~(1,\;4,\;3)~, ~(4,\;3,\;0)~, ~(4,\;3,\;2)~, ~(3,\;4,\;0)~, ~(3,\;4,\;1)~.

input

3 5

output

14

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

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

input

100 200

output

410783331