Mausoleum
Contest: Codeforces Round #Pi (Div. 2)
Difficulty rating: 2400
Tags: dp

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 2n 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[xi] signi h[yi]", where h[t] is the height of the t-th block, and a signi 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 xi, yi (1 ≤ xi, yi ≤ 2n) and sign signi.

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.

Input format:
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 "xi signi yi" (1 ≤ xi, yi ≤ 2n), and the sign is on of the list of the five possible signs.

Output format:
Print the sought number of ways.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3 0

Example output:
9

Example input:
3 1
2 > 3

Example output:
1

Editorial:
Consider that we are placing blocks by pairs, one pair by one, starting from leftmost and rightmost places. Thus, for example, two blocks of height 1 we could place in positions 1 and 2, 1 and 2n, or 2n - 1 and 2n. The segment of unused positions will be changed that way and the next block pairs should be placed on new leftmost and rightmost free places. At last only two positions will be free and we should place two blocks of height n on them.
Any correct sequence of blocks could be builded that way. Let's try to review the requirements consider such way of placing blocks. As soon as we place blocks one by one, the requirements are now only describes the order of placing blocks. For example, requirement "3 >= 5" means that we should place block in position 3 only if block in position 5 is already placed (and thus it have lesser height), or we place pair of blocks of same height on them at one moment.
For counting required number of sequences we will use dynamic programming approach. Let's count dp[l][r] — the number of ways to place some blocks in the way that only positions at segment [l..r] are free. The height of current placed pair of blocks is counted from the segment borders itself ($${ \frac { ( l + ( n - r ) ) } { 2 } }$$. Fix one way of placing current block pair (exclusion is l =  = r + 1). Now check if such placing meets the requirements. We will consider only requirements that meets one of the current-placing positions. For every "current" position "<" must be true only for free positions (positions in [l..r], which do not equal to current positions), ">" must be true for already-placed positions (out of [l..r]) and "=" must be true only for second current position.
This DP could be easily calculated using "lazy" approach.