В детстве я любил роботов и лабиринты. Я строил лабиринты из кубиков и запускал в них роботов. Для каждого робота я составлял программу путешествия: это была строчка букв «Л», «П», «В» и «Н», которые обозначали соответственно шаги влево, вправо, вверх и вниз в некоторой дискретной системе координат с квадратами размером в один кубик. Жаль, мои роботы были игрушечные и мне приходилось исполнять эти программы за них. Я называл программу корректной, если она не приводила к врезанию в стену или выходу за пределы лабиринта. Как-то раз я построил очередной лабиринт, поместил в него робота и задумался, сколько всего существует корректных программ, которые приведут этого робота на его изначальное место. Я быстро догадался, что их бесконечно много. Стоило бы на этом остановиться, но я задумался, сколько корректных программ, не превышающих длины $$$l$$$, оставят робота на месте. Именно такую задачу вам и придётся сейчас решить. Лабиринт представляет собой прямоугольное поле размером $$$n$$$ на $$$m$$$ квадратов. Каждый квадрат может быть либо стеной, либо проходом.

Повзрослевший Автор

P. S. Интересно, в какие игры вы играли в детстве.