#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / abs1(a) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  a += b;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
const int maxn = 122;
vector<pair<int, int> > con[maxn];
int n, ncon;
long long dp[100][100];
int le, ri;
bool jud(int rle, int all, int no1, int no2) {
  int l = rle - 1, r = n * 2 - (all - rle);
  for (int i = 0; i < (int)con[no1].size(); i++) {
    int no = con[no1][i].first, cate = con[no1][i].second;
    if (cate == 4) {
      if (no > l && no < r) return 0;
    } else if (cate == 3) {
      if (no > l && no < r && no != no1 && no != no2) return 0;
    } else if (cate == 2) {
      if (no != no1 && no != no2) return 0;
    } else if (cate == 1) {
      if (no <= l || no >= r) return 0;
    } else if (cate == 0) {
      if (no <= l || no >= r || no == no1 || no == no2) return 0;
    }
  }
  for (int i = 0; i < (int)con[no2].size(); i++) {
    int no = con[no2][i].first, cate = con[no2][i].second;
    if (cate == 4) {
      if (no > l && no < r) return 0;
    } else if (cate == 3) {
      if (no > l && no < r && no != no1 && no != no2) return 0;
    } else if (cate == 2) {
      if (no != no1 && no != no2) return 0;
    } else if (cate == 1) {
      if (no <= l || no >= r) return 0;
    } else if (cate == 0) {
      if (no <= l || no >= r || no == no1 || no == no2) return 0;
    }
  }
  return 1;
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &ncon);
  for (int i = 0; i < ncon; i++) {
    int a, b, cate;
    char str[10];
    scanf("%d%s%d", &a, str, &b);
    a--;
    b--;
    if (strlen(str) == 1) {
      if (str[0] == '=')
        cate = 2;
      else if (str[0] == '>')
        cate = 4;
      else
        cate = 0;
    } else {
      if (str[0] == '<')
        cate = 1;
      else
        cate = 3;
    }
    con[a].push_back(make_pair(b, cate));
    con[b].push_back(make_pair(a, 4 - cate));
  }
  long long ans = 0;
  for (int i = 0; i < n * 2 - 1; i++) {
    le = i, ri = n * 2 - 1 - i - 1;
    bool flag = 1;
    for (int j = 0; j < (int)con[i].size(); j++) {
      int no = con[i][j].first, cate = con[i][j].second;
      if (cate == 0) flag = 0;
      if (cate == 1 && no != i + 1 && no != i) flag = 0;
      if (cate == 2 && no != i + 1 && no != i) flag = 0;
      if (cate == 4 && (no == i + 1 || no == i)) flag = 0;
    }
    for (int j = 0; j < (int)con[i + 1].size(); j++) {
      int no = con[i + 1][j].first, cate = con[i + 1][j].second;
      if (cate == 0) flag = 0;
      if (cate == 1 && no != i + 1 && no != i) flag = 0;
      if (cate == 2 && no != i + 1 && no != i) flag = 0;
      if (cate == 4 && (no == i + 1 || no == i)) flag = 0;
    }
    if (!flag) continue;
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i < n - 1; i++) {
      for (int k = 0; k <= le; k++)
        if (dp[i][k]) {
          if (k <= le - 2 && jud(k, i * 2, k, k + 1))
            add(dp[i + 1][k + 2], dp[i][k]);
          if (k <= le - 1 && ri > i * 2 - k &&
              jud(k, i * 2, k, 2 * n - (i * 2 - k + 1)))
            add(dp[i + 1][k + 1], dp[i][k]);
          if (ri > i * 2 - k + 1 && jud(k, i * 2, 2 * n - (i * 2 - k + 1) - 1,
                                        2 * n - (i * 2 - k + 1)))
            add(dp[i + 1][k], dp[i][k]);
        }
    }
    add(ans, dp[n - 1][le]);
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

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

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

Print the sought number of ways.

Examples

Input

3 0


Output

9


Input

3 1
2 &gt; 3


Output

1


Input

4 1
3 = 6


Output

3

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / abs1(a) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  a += b;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
const int maxn = 122;
vector<pair<int, int> > con[maxn];
int n, ncon;
long long dp[100][100];
int le, ri;
bool jud(int rle, int all, int no1, int no2) {
  int l = rle - 1, r = n * 2 - (all - rle);
  for (int i = 0; i < (int)con[no1].size(); i++) {
    int no = con[no1][i].first, cate = con[no1][i].second;
    if (cate == 4) {
      if (no > l && no < r) return 0;
    } else if (cate == 3) {
      if (no > l && no < r && no != no1 && no != no2) return 0;
    } else if (cate == 2) {
      if (no != no1 && no != no2) return 0;
    } else if (cate == 1) {
      if (no <= l || no >= r) return 0;
    } else if (cate == 0) {
      if (no <= l || no >= r || no == no1 || no == no2) return 0;
    }
  }
  for (int i = 0; i < (int)con[no2].size(); i++) {
    int no = con[no2][i].first, cate = con[no2][i].second;
    if (cate == 4) {
      if (no > l && no < r) return 0;
    } else if (cate == 3) {
      if (no > l && no < r && no != no1 && no != no2) return 0;
    } else if (cate == 2) {
      if (no != no1 && no != no2) return 0;
    } else if (cate == 1) {
      if (no <= l || no >= r) return 0;
    } else if (cate == 0) {
      if (no <= l || no >= r || no == no1 || no == no2) return 0;
    }
  }
  return 1;
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &ncon);
  for (int i = 0; i < ncon; i++) {
    int a, b, cate;
    char str[10];
    scanf("%d%s%d", &a, str, &b);
    a--;
    b--;
    if (strlen(str) == 1) {
      if (str[0] == '=')
        cate = 2;
      else if (str[0] == '>')
        cate = 4;
      else
        cate = 0;
    } else {
      if (str[0] == '<')
        cate = 1;
      else
        cate = 3;
    }
    con[a].push_back(make_pair(b, cate));
    con[b].push_back(make_pair(a, 4 - cate));
  }
  long long ans = 0;
  for (int i = 0; i < n * 2 - 1; i++) {
    le = i, ri = n * 2 - 1 - i - 1;
    bool flag = 1;
    for (int j = 0; j < (int)con[i].size(); j++) {
      int no = con[i][j].first, cate = con[i][j].second;
      if (cate == 0) flag = 0;
      if (cate == 1 && no != i + 1 && no != i) flag = 0;
      if (cate == 2 && no != i + 1 && no != i) flag = 0;
      if (cate == 4 && (no == i + 1 || no == i)) flag = 0;
    }
    for (int j = 0; j < (int)con[i + 1].size(); j++) {
      int no = con[i + 1][j].first, cate = con[i + 1][j].second;
      if (cate == 0) flag = 0;
      if (cate == 1 && no != i + 1 && no != i) flag = 0;
      if (cate == 2 && no != i + 1 && no != i) flag = 0;
      if (cate == 4 && (no == i + 1 || no == i)) flag = 0;
    }
    if (!flag) continue;
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i < n - 1; i++) {
      for (int k = 0; k <= le; k++)
        if (dp[i][k]) {
          if (k <= le - 2 && jud(k, i * 2, k, k + 1))
            add(dp[i + 1][k + 2], dp[i][k]);
          if (k <= le - 1 && ri > i * 2 - k &&
              jud(k, i * 2, k, 2 * n - (i * 2 - k + 1)))
            add(dp[i + 1][k + 1], dp[i][k]);
          if (ri > i * 2 - k + 1 && jud(k, i * 2, 2 * n - (i * 2 - k + 1) - 1,
                                        2 * n - (i * 2 - k + 1)))
            add(dp[i + 1][k], dp[i][k]);
        }
    }
    add(ans, dp[n - 1][le]);
  }
  cout << ans << endl;
  return 0;
}

```