Tetris

Το Tetris είναι ένα δημοφιλές παιχνίδι υπολογιστή που παίζεται σε μία περιοχή που αποτελείται από ~C~ στήλες και έναν απεριόριστο αριθμό σειρών. Με μία κίνηση, ένα από τα επτά παρακάτω κομμάτια πέφτει στην περιοχή:

Όταν το κομμάτι πέφτει, ο παίκτης είναι ελεύθερος να περιστρέψει το κομμάτι ~90~, ~180~ ή ~270~ μοίρες και να το μετακινήσει αριστερά ή δεξιά, αρκεί το κομμάτι να μείνει εξ ολοκλήρου στην περιοχή. Στη συνέχεια, το κομμάτι πέφτει μέχρι να κατακαθίσει στο κάτω μέρος της περιοχής ή σε ήδη κατειλημμένα τετράγωνα. Στην παραλλαγή μας του Tetris το κομμάτι πρέπει να πέσει έτσι ώστε όλα τα μέρη του κομματιού βρίσκονται στο κάτω μέρος της περιοχής ή σε ήδη κατειλημμένα τετράγωνα. Με άλλα λόγια, μετά την πτώση του κομματιού δεν μπορεί να υπάρχει ελεύθερο τετράγωνο τέτοιο ώστε να είναι κατειλημμένο κάποιο τετράγωνο από πάνω του.

Για παράδειγμα, ας έχει η περιοχή πλάτος έξι στηλών με αρχικά ύψη (ο αριθμός των ήδη κατειλημμένων τετραγώνων σε κάθε στήλη) ~2,\,1,\,1,\,1,\,0~ και ~1~. Το κομματι με αριθμό ~5~ μπορεί στη συνέχεια να πέσει στην περιοχή με πέντε διαφορετικούς τρόπους:

Σας δίνονται τα αρχικά ύψη όλων των στηλών και το σχήμα που θα πέσει στην περιοχή.

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

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~C~ και ~P, 1 \le C \le 100,\,1 \le P \le 7~, τον αριθμό των στηλών και τον αριθμό του κομματιού που πρόκειται να πέσει.

Η δεύτερη γραμμή περιέχει ακέραιους ~C~ που χωρίζονται από μεμονωμένα κενά, ο καθένας μεταξύ ~0~ και ~100~, συμπεριλαμβανομένου. Αυτά είναι τα αρχικά ύψη των στηλών.

Έξοδος

Τυπώστε σε μία γραμμή τον αριθμό των διαφορετικών τρόπων απόθεσης του κομματιού στην περιοχή.

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

input

6 5
2 1 1 1 0 1

output

5

input

5 1
0 0 0 0 0

output

7

input

9 4
4 3 5 4 6 5 7 6 6

output

1