У Валеры есть бесконечная в обе стороны полоска, состоящая из клеток. Клетки пронумерованы целыми числами. В клетке с номером 0 стоит робот.
У робота есть инструкция — последовательность ходов, которые он должен совершить. За один ход робот перемещается на одну клетку влево или вправо, согласно инструкции. До начала движения робота Валера размещает препятствия в каких-то клетках полоски, исключая клетку с номером 0. Если в какой-то из ходов робот по инструкции должен пойти в клетку с препятствием, то он пропускает этот ход.
Кроме того Валера указывает номер финишной клетки, в которой робот должен оказаться после выполнения всей инструкции. Финишная клетка должна быть отлична от стартовой. Считается, что робот успешно выполнил инструкцию, если в процессе ее выполнения он посетил финишную клетку ровно один раз — своим последним ходом. Причем, последний ход не должен быть пропущен.
Предположим, что минимальное количество препятствий, которое необходимо поставить Валере, чтобы робот смог выполнить всю последовательность ходов и оказаться в какой-то финишной клетке равно k. Вам требуется посчитать, сколькими способами Валера может выбрать k препятствий и финишную клетку так, чтобы робот смог успешно выполнить инструкцию.
Примечание
В первом примере Валера не должен ставить никаких препятствий, а в качестве финишной клетки выбрать клетку с номером 2.
Во втором примере Валере необходимо поставить препятствие в клетку с номером 1, а финишной клеткой назначить клетку с номером - 1. В этом случае он пропустит первые два хода, а на третьем сразу перейдет из своей стартовой клетки в финишную. Если же Валера не поставит никаких препятствий, или поставит препятствие в другую клетку, то он посетит финишную клетку более одного раза.