CF567F.Mausoleum

King of Berland Berl IV has recently died. Hail Berl V! As a sign of the highest achievements of the deceased king the new king decided to build a mausoleum with Berl IV's body on the main square of the capital.

The mausoleum will be constructed from 2_n_ blocks, each of them has the shape of a cuboid. Each block has the bottom base of a 1 × 1 meter square. Among the blocks, exactly two of them have the height of one meter, exactly two have the height of two meters, ..., exactly two have the height of n meters.

The blocks are arranged in a row without spacing one after the other. Of course, not every arrangement of blocks has the form of a mausoleum. In order to make the given arrangement in the form of the mausoleum, it is necessary that when you pass along the mausoleum, from one end to the other, the heights of the blocks first were non-decreasing (i.e., increasing or remained the same), and then — non-increasing (decrease or remained unchanged). It is possible that any of these two areas will be omitted. For example, the following sequences of block height meet this requirement:

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

Suddenly, k more requirements appeared. Each of the requirements has the form: "h[x__i] sign_i_ h[y__i]", where h[t] is the height of the t-th block, and a sign_i_ is one of the five possible signs: '=' (equals), '<' (less than), '>' (more than), '<=' (less than or equals), '>=' (more than or equals). Thus, each of the k additional requirements is given by a pair of indexes x__i, y__i (1 ≤ x__i, y__i ≤ 2_n_) and sign sign_i_.

Find the number of possible ways to rearrange the blocks so that both the requirement about the shape of the mausoleum (see paragraph 3) and the k additional requirements were met.

贝尔兰德王国国王贝尔四世近日驾崩，贝尔五世登基！为彰显已故国王的至高功绩，新国王决定在首都主广场上为其修建一座陵墓，安放贝尔四世的遗体。

该陵墓将由 $2n$ 个长方体形状的石块构成。每个石块底面均为 $1 \times 1$ 米的正方形。在这些石块中，恰好有两个高度为 $1$ 米的石块，恰好有两个高度为 $2$ 米的石块，……，恰好有两个高度为 $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]\ \text{sign}_i\ h[y_i]$”，其中 $h[t]$ 表示第 $t$ 个石块的高度，$\text{sign}_i$ 是以下五种符号之一：‘=’（等于）、‘<’（小于）、‘>’（大于）、‘<=’（小于等于）、‘>=’（大于等于）。因此，每条额外约束均由一对下标 $x_i,\ y_i$（满足 $1 \le x_i,\ y_i \le 2n$）及一个符号 $\text{sign}_i$ 给出。

请计算满足以下两个条件的石块排列方案总数：
（1）陵墓形态要求（见上文第 3 段）；
（2）全部 $k$ 条额外约束条件。

The first line of the input contains integers n and k (1 ≤ n ≤ 35, 0 ≤ k ≤ 100) — the number of pairs of blocks and the number of additional requirements.

Next k lines contain listed additional requirements, one per line in the format "x__i sign_i_ y__i" (1 ≤ x__i, y__i ≤ 2_n_), and the sign is on of the list of the five possible signs.

输入的第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 35$，$0 ≤ k ≤ 100$）——分别表示方块对的数量以及额外约束条件的数量。

接下来的 $k$ 行每行描述一个额外约束条件，格式为 “$x_i$ $\text{sign}_i$ $y_i$”（其中 $1 ≤ x_i, y_i ≤ 2n$），符号 $\text{sign}_i$ 是以下五种可能符号之一。

Print the sought number of ways.

输出所求的方案数。