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

Рассмотрим дорогу, подходящую к перекрестку, на котором сходится \(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. в каждом направлении разрешено движение хотя бы с одной полосы.


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

Учительница математики попросила школьников составить арифметическое выражение так, чтобы его значение было равно данному числу \(N\), и записать его в тетради. В выражении могут быть использованы натуральные числа, не превосходящие \(K\), операции сложения и умножения, а также скобки. Петя очень не любит писать, и хочет придумать выражение, содержащее как можно меньше символов. Напишите программу, которая поможет ему в этом.

На окружности отметили \(N\) точек и пронумеровали их последовательно числами от 1 до \(N\). Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами \(i\) и \(j\).

Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).

Даны \(N\) целых чисел \(X_1\), \(X_2\), ..., \(X_N\). Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

В таблице из \(N\) строк и \(N\) столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (\(N\), \(N\)), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.