← 返回题目列表

Codeforces · 567/F

F. 陵墓

中文机器翻译题面 查看原题

贝尔兰国王贝尔四世最近去世。贝尔五世万岁!作为已故国王最高成就的标志,新国王决定在首都的主广场上为贝尔四世的遗体建造一座陵墓。

陵墓将由 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[xi]signi h[yi]”,其中h[t]是第t个块的高度,signi是五个可能的符号之一:'='(等于)、'<'(小于)、'>'(大于)、'<='(小于或等于)、'>='(大于或等于)。因此,k 个附加要求中的每一个都由一对索引 xi、yi (1 ≤ xi, yi ≤ 2n) 和符号signi 给出。

找出重新排列块的可能方法的数量,以便满足有关陵墓形状的要求(参见第 3 段)和 k 个附加要求。

输入

输入的第一行包含整数 n 和 k (1 ≤ n ≤ 35, 0 ≤ k ≤ 100) — 块对的数量和附加要求的数量。

接下来的 k 行包含列出的附加要求,每行一个,格式为“xi Signi yi”(1 ≤ xi,yi ≤ 2n),并且该符号位于五个可能符号的列表中。

输出

打印所寻求的方法数。

示例

输入 #1

3 0

输出 #1

9

输入 #2

3 1
2 > 3

输出 #2

1

输入 #3

4 1
3 = 6

输出 #3

3