Magneti

Ο μικρός Marko βαρέθηκε να παίζει με "σκοτεινά" κρυπτονομίσματα, όπως το Shiba Inu ή το XRC, γι' αυτό αποφάσισε να παίξει με μαγνήτες. Έχει ~n~ διαφορετικούς μαγνήτες και μια πλακέτα που έχει ~l~ διαθέσιμες κενές υποδοχές στη σειρά, στις οποίες μπορούν να τοποθετηθούν οι μαγνήτες. Κάθε ζεύγος γειτονικών υποδοχών απέχει ακριβώς ένα εκατοστό. Καθένας από τους ~n~ μαγνήτες δημιουργεί μαγνητικό πεδίο, που δρα σε ακτίνα ίση με ~r_i~. Αυτό σημαίνει ότι θα προσελκύσει όλους τους μαγνήτες που βρίσκονται σε ακτίνα αυστηρά μικρότερη από ~r_i~ εκατοστά (ανεξάρτητα από το εύρος του μαγνητικού πεδίου του άλλου μαγνήτη). Είναι πιθανό ορισμένοι μαγνήτες να έχουν ίδιο εύρος μαγνητικού πεδίου, αλλά θα θεωρούνται διαφορετικοί μαγνήτες.

Στον Μάρκο δεν αρέσει όταν οι μαγνήτες έλκονται μεταξύ τους, γι' αυτό τον ενδιαφέρει ο αριθμός των τρόπων τοποθέτησης των μαγνητών στον πίνακα έτσι ώστε κανένας μαγνήτης να μην έλκει κανέναν άλλο. Όλοι οι μαγνήτες πρέπει να τοποθετηθούν στον πίνακα και κάθε κενή υποδοχή μπορεί να περιέχει το πολύ ένα μαγνήτη. Δύο τρόποι τοποθέτησης των μαγνητών θεωρούνται διαφορετικοί εάν ο μαγνήτης της πρώτης τοποθέτησης βρίσκεται σε διαφορετική θέση σε σχέση με τη δεύτερη τοποθέτηση. Καθώς ο απαιτούμενος αριθμός μπορεί να είναι αρκετά μεγάλος, θα πρέπει να εξάγετε το υπόλοιπο της ακέραιας διαίρεσης του αριθμού (modulo) με το ~10^9 + 7~.

Είσοδος

Η πρώτη γραμμή περιέχει θετικούς ακέραιους αριθμούς ~n~ και ~l~, τον αριθμό των μαγνητών και τον αριθμό των κενών υποδοχών.

Η δεύτερη γραμμή περιέχει ~n~ θετικούς ακέραιους ~r_i~ ~(1 \le r_i \le l)~, το εύρος του μαγνητικού πεδίου των ~n~ μαγνητών.

Έξοδος

Εκτυπώστε το απαιτούμενο πλήθος των τρόπων τοποθέτησης των μαγνητών στον πίνακα ώστε κάθε μαγνήτης να μην προσελκύει κανέναν άλλο (τυπώνετε το αποτέλεσμα στη μορφή modulo ~10^9 + 7~.

Βαθμολογία

Σε κάθε υποπρόβλημα ισχύει ότι ~1 \le n \le 50~ και ~n \le l \le 10\,000~.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~r_1 = r_2 = \ldots = r_n~
2	20	~1 \le n \le 10~
3	30	~1 \le n \le 30, n \le l \le 300~
4	50	Κανένας επιπλέον περιορισμός.

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

input

1 10
10

output

10

input

4 4
1 1 1 1

output

24

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

Όλες οι μεταθέσεις των μαγνητών είναι έγκυρες γιατί κανένας μαγνήτης δεν μπορεί να έλξει τον άλλο.

input

3 4
1 2 1

output

4

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

Αν συμβολίσουμε τους μαγνήτες με 1, 2 και 3 και την κενή υποδοχή με μια κάτω παύλα _, οι πιθανές διατάξεις των μαγνητών είναι 13_2, 31_2, 2_13 και 2_31.