Задача №582. Движение по полосам

С каждой задачей нужно проделать следующие действия:
  1. выключить голову;
  2. написать тупой перебор и сдать его;
  3. включить голову;
  4. придумать решение задачи и закодить его;
  5. написать генератор тестов;
  6. запустить на многих тестах тупой перебор и умное решение;
  7. если стресс-тестирование нашло антитест к умному решению, то найти ошибку в умном решении, исправить её и перейти к предыдущему пункту;
  8. сдать код, в котором вызывается тупое решение, если ограничения маленькие, и умное решение, если ограничения большие.


Таким образом, по каждой задаче необходимо получить +1.

При организации движения по сложным перекресткам для того, чтобы траектории водителей, выполняющих различные маневры, не пересекались, вводят ограничения на возможные маневры водителей, в зависимости от того, по какой полосе движения водитель подъехал к перекрестку. Для этого используется знак "движение по полосам", на рисунке приведен пример такого знака, установленного перед одним из перекрестков в Санкт-Петербурге.


Пример
Рассмотрим дорогу, подходящую к перекрестку, на котором сходится \(m\) дорог. Водитель, подъезжающий к перекрестку по этой дороге, потенциально может продолжить свое движение в \(m\) различных направлениях - обратно по дороге, по которой он приехал, а также по одной из оставшихся (\(m\) - 1) дорог. Пронумеруем возможные направления числами от 1 до \(m\) слева направо с точки зрения подъезжающего водителя, номер 1 получит разворот и возврат по дороге, по которой водитель подъезжал к перекрестку, номер 2 - поворот на самую левую из дорог и т. д.

Пусть дорога содержит \(n\) полос для движения. Пронумеруем полосы от 1 до \(n\) слева направо, самая левая полоса получит номер 1, следующая номер 2 и т. д. Знак "движение по полосам" разрешает каждой из полос движение по некоторым из m возможных направлений. При этом должны выполняться следующие условия:

1. если с \(i\)-й полосы разрешено движение в \(a\)-м направлении, а с \(j\)-й полосы - в \(b\)-м направлении, причем \(i\) < \(j\), то \(a\) <= \(b\);
2. с каждой полосы разрешено движение хотя бы в одном направлении;
3. в каждом направлении разрешено движение хотя бы с одной полосы.


Инспекция по безопасности дорожного движения заинтересовалась: а сколько различных знаков "движение по полосам" можно установить перед таким перекрестком. Помогите им найти ответ на этот вопрос.

Входные данные

На вход программы поступают два целых числа: \(m\) и \(n\) (2 <= \(m\) <= 50, 1 <= \(n\) <= 15).

Выходные данные

Выведите одно число - количество возможных знаков "движение по полосам", которые можно установить перед перекрестком.

Пояснение к примеру

В примере возможны следующие варианты знаков "движение по полосам":

Пример

Примеры
Входные данные
4 2
Выходные данные
7
Сдать: для сдачи задач необходимо войти в систему