시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
При организации движения по сложным перекресткам, для того, чтобы траектории водителей, выполняющих различные маневры не пересекались, вводят ограничения на возможные маневры водителей, в зависимости от того, по какой полосе движения водитель подъехал к перекрестку. Для этого используется знак <<движение по полосам>>, на рисунке справа приведен пример такого знака, установленного перед одним из перекрестков в Санкт-Петербурге.
Рассмотрим дорогу, подходящую к перекрестку, на котором сходится $m$ дорог. Водитель, подъезжающий к перекрестку по этой дороге, потенциально может продолжить свое движение в $m$ различных направлениях --- обратно по дороге, по которой он приехал, а также по одной из оставшихся $m - 1$ дорог. Пронумеруем возможные направления числами от 1 до $m$ слева направо с точки зрения подъезжающего водителя, номер 1 получит разворот и возврат по дороге, по которой водитель подъезжал к перекрестку, номер 2 --- поворот на самую левую из дорог, и т. д.
Пусть дорога содержит $n$ полос для движения. Пронумеруем полосы от 1 до $n$ слева направо, самая левая полоса получит номер 1, следующая номер 2, и т. д. Знак <<движение по полосам>> разрешает каждой из полос движение по некоторым из $m$ возможных направлений. При этом должны выполняться следующие условия:
Инспекция по безопасности дорожного движения заинтересовалась, а сколько различных знаков <<движение по полосам>> можно установить перед таким перекрестком. Помогите им найти ответ на этот вопрос.
Входной файл содержит два целых числа: $m$ и $n$ ($2 \le m \le 50$, $1 \le n \le 15$).
В выходной файл выведите одно число --- количество возможных знаков <<движение по полосам>>, которые можно установить перед перекрестком.
4 2
7
В примере возможны следующие варианты знаков <<движение по полосам>>:
С левой полосы | С правой полосы |
---|---|
разворот | разворот, налево, прямо, направо |
разворот | налево, прямо, направо |
разворот, налево | налево, прямо, направо |
разворот, налево | прямо, направо |
разворот, налево, прямо | прямо, направо |
разворот, налево, прямо | направо |
разворот, налево, прямо, направо | направо |