В самолете есть n рядов от кабины до хвоста, в каждом ряду — одно место. На самолет сядут m человек.
В самолете есть вход в начала перед всеми рядами, а также есть вход в конце после всех рядов.
У каждого человека есть место. Возможно, что у нескольких людей места совпадают. Люди будут садиться на борт по одному, начиная с человека 1. Каждый человек независимо войдет либо через передний вход, либо через задний.
Когда человек входит в самолет, он пройдет сразу к своему месту. Затем, пока место, около которого он стоит, занято, он будет проходить на одно место в том же направлении. Пассажир разозлится, если он дойдет до конца ряда (т.е. до противоположного входа), так и не найдя свободного места.
Найдите число способов назначить каждому пассажиру место и выполнить посадку так, чтобы никто не разозлился. Два способа считаются различными, если есть пассажир, у которого в двух способах разные места, либо есть пассажир, который входит через разные входы в двух способах. Выведите это число по модулю 109 + 7.
Примечание
Здесь будем обозначать пассажиров номером места и входом (либо «F», либо «B» для переднего и заднего входа, соответственно).
Например, один из корректных способов посадки это 3B, 3B, 3B (т.е. у всех пассажиры место 3, и они зашли через задний вход). Другой способ это, например, 2F, 1B, 3F.
Некорректный способ, это, например, 2B, 2B, 2B, потому что третий пассажир доберется до переднего входа, не найдя свободного места.