Periodni

Ο Luka βαριέται στο μάθημα της χημείας και κοιτάζει επίμονα έναν μεγάλο περιοδικό πίνακα χημικών στοιχείων που κρέμεται από έναν τοίχο πάνω από τον μαυροπίνακα. Για να "σκοτώσει" τον χρόνο του, ο Luka αποφάσισε να φτιάξει το δικό του πίνακα εντελώς διαφορετικό από αυτόν της τάξης.
Ο πίνακάς του αποτελείται από ~N~ στήλες, καθεμία με κάποιο ύψος, ευθυγραμμισμένες στο κάτω μέρος (βλ. παράδειγμα παρακάτω). Αφού σχεδιάσει τον πίνακα πρέπει να τον γεμίσει με στοιχεία. Πρώτα αποφάσισε να βάλει τα ευγενή αέρια, τα οποία είναι ~K~. Ο Luka πρέπει να τα βάλει στον πίνακα ώστε να μην είναι δύο ευγενή αέρια κοντά το ένα στο άλλο.
Δύο τετράγωνα στον πίνακα είναι κοντά το ένα στο άλλο αν βρίσκονται στην ίδια στήλη ή γραμμή και όλα τα τετράγωνα μεταξύ τους υπάρχουν. Στο παρακάτω παράδειγμα, τα τετράγωνα '~a~' δεν είναι κοντά, αλλά τα τετράγωνα '~b~' είναι.

Γράψτε ένα πρόγραμμα που, λαμβάνοντας υπόψη τα ~N~, ~K~ και τα ύψη των ~N~ στηλών, να υπολογίζει τον συνολικό αριθμό των τρόπων με τους οποίους μπορεί ο Luka να τοποθετήσει τα ευγενή αέρια στον πίνακα. Αυτός ο αριθμός μπορεί να είναι μεγάλος, οπότε τυπώστε το ως υπόλοιπο ακέραιας διαίρεσης (modulo) με το ~1\,000\,000\,007~.

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους ~N~ και ~K~ που χωρίζονται με ένα κενό ~(1 \le N \le 500,\; 1 \le K \le 500)~, τον αριθμό των στηλών στον πίνακα του Luka και τον αριθμό των ευγενών αερίων.
Η επόμενη γραμμή περιέχει ~N~ θετικούς ακέραιους, χωρισμένους με κενά. Αυτά είναι τα ύψη των στηλών από τα αριστερά προς τα δεξιά. Τα ύψη θα είναι το πολύ ~1\,000\,000~.

Έξοδος

Τυπώστε τον αριθμό των τρόπων με τους οποίους μπορεί να γεμίσει ο Luka τον πίνακά του με ευγενή αέρια, ως υπόλοιπο ακέραιας διαίρεσης (modulo) με το ~1\,000\,000\,007~.

Βαθμολογία

Στα αρχεία ελέγχου αξίας ~40%~ των πόντων, όλοι οι αριθμοί στην είσοδο θα είναι μικρότεροι από ~15~.
Στα αρχεία ελέγχου αξίας ~70%~ των πόντων, όλοι οι αριθμοί στην είσοδο θα είναι μικρότεροι από ~100~.

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

input

3 3
2 1 3

output

2

input

4 1
1 2 3 4

output

10

input

5 2
2 3 1 2 4

output

43

input

3 2
999999 999999 999999

output

990979013