Совсем недавно скоропостижно скончался король Берляндии Берл IV. Да здравствует Берл V! В знак высочайших заслуг усопшего короля новый король решил установить мавзолей с телом Берла IV на главной площади столицы.

Мавзолей будет сооружён из 2n блоков, каждый из которых имеет форму прямоугольного параллелепипеда. Каждый из блоков имеет в нижнем основании квадрат 1 × 1 метр. Среди блоков ровно два имеют высоту один метр, ровно два имеют высоту два метра, ..., ровно два имеют высоту n метров.

Блоки будут установлены в ряд без промежутков один за другим. Конечно, не каждый порядок блоков имеет форму мавзолея. Для того, чтобы заданный порядок имел форму мавзолея, необходимо, чтобы при прохождении вдоль мавзолея от одного конца до другого высоты блоков сначала неубывали (то есть возрастали или оставались неизменными), а затем — невозрастали (то есть убывали или оставались неизменными). Допустимо, что любой из этих двух участков будет отсутствовать. Например, под это требование попадают следующие последовательности высот блоков:

• [1, 2, 2, 3, 4, 4, 3, 1];
• [1, 1];
• [2, 2, 1, 1];
• [1, 2, 3, 3, 2, 1].

Внезапно появились дополнительные k требований. Каждое из требований имеет вид: «h[x_i] знак_i h[y_i]», где h[t] — высота t-го слева блока, а знак_i — один из пяти возможных знаков '=' (равно), '<' (меньше), '>' (больше), '<=' (меньше либо равно), '>=' (больше либо равно). Таким образом, каждое из k дополнительных требований задаётся парой индексов x_i, y_i (1 ≤ x_i, y_i ≤ 2n) и знаком знак_i.

Найдите количество возможных способов расставить блоки, чтобы одновременно выполнялось как требование о форме мавзолея (см. третий абзац), так и k дополнительных требований.