Тетріс – улюблена гра марини Віталіївни. Вона складається з С стовпчиків та необмеженої кількості рядочків.

Коли фігура випадає, гравець може повертати її на 90. 180 або 270 градусів, а потім перемістити її вліво або вправо, поки фігура залишається повністю у полі. Потім вона падає, поки вона не доторкнеться до дна поля або до іншої фігури. У нашій модифікації тетрісу фігура повинна падати так, щоб усі частини фігури були на дні поля або доторкалися знизу до інших фігур. Іншими словами, після того як частина падає, не може бути вільного квадрати, над яким є фігура.

Наприклад, нехай поле має шість стовпчиків із початковими висотами (число вже зайнятих квадратиків у кожному стовпчику) 2, 1, 1, 1,0 та 1. Фігурка з номером 5 може впасти п'ятьма різними способами:

У вас є початкові висоти усіх стовпчиків та номер фігури, яка випаде на поле. Напишіть програму, яка обчислює кількість різних способів випадання, тобто кількість різних конфігурацій поля, які можна отримати, не порушуючи правила.

Формат вхідних даних:

У першому рядку задано два числа С та Р(1 ≤ С ≤ 100, 1≤ Р≤ 7) - кількість стовпчиків та номер фігури, що випаде.

У другому рядку задано С чисел у діапазоні [0, 100]. Це початкові висоти стовпчиків.

Формат вихідних даних:

Виведіть кількість можливих конфігурацій поля.