Любимая игра Марины Витальевны
Тетрис — это любимая игра Марины Витальевны, в которой игровое поле состоит из С столбцов и неограниченного количества строк.
Когда фигура появляется, игрок может повернуть её на 90, 180 или 270 градусов, а затем перемещать влево или вправо, пока она полностью остаётся в пределах поля. После этого фигура падает вниз, пока не достигнет дна поля или другой фигуры. В нашей версии тетриса фигура должна падать так, чтобы все её части либо касались дна поля, либо находились на других фигурах. Иными словами, после падения фигуры не должно оставаться свободных клеток под её частями.
Например, если поле состоит из шести столбцов с начальными высотами (число уже занятых клеток в каждом столбце) 2, 1, 1, 1, 0 и 1, то фигура под номером 5 может быть размещена пятью различными способами:
Вам даны начальные высоты всех столбцов и номер фигуры, которая выпадет на поле. Напишите программу, которая определит количество различных способов размещения фигуры, то есть количество различных конфигураций поля, которые можно получить, соблюдая правила.
Формат входных данных:
В первой строке указаны два числа С и Р (1 ≤ С ≤ 100, 1 ≤ Р ≤ 7) — количество столбцов и номер фигуры, которая выпадет.
Во второй строке приведены С чисел в диапазоне [0, 100]. Это начальные высоты столбцов.
Формат выходных данных:
Выведите количество возможных конфигураций поля.