Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Trong truyền thuyết, có 1 con khỉ võ nghệ cao cường, tinh thông 72 phép thuật, tên Tôn Ngộ Có, được người đời xới danh Tề Thiên Tiểu Thánh. Có một cuốn bí kíp bí truyền từ tổ tiên loài khỉ xa xưa để lại – Bí Kíp Luyện Code. Tương truyền rằng, nếu luyện thành công món này, có thể bá chủ thiên hạ. Và tất nhiên Tôn Ngộ Có đã lập tức bắt chân vào tu luyện.

Nhưng trước hết để tu luyện thì phải xây dựng được trận đồ nhất quái. Trận đồ bát quái gồm n cặp cây Gậy như ý, tức 2*n cây gậy, trong đó có 2 cây cao 1m, 2 cây cao 2m, …… , 2 cây cao n mét. Các gậy như ý được xếp thẳng đứng song song và liên tiếp nhau. Trận đồ nhất quái là trận đồ mà tất cả các gậy như ý được xếp sao cho các đỉnh gậy tạo thành 1 ngon có 2 sườn dốc. Tức là dãy các gậy như ý sẽ bao gồm 2 đoạn, đoạn đầu sẽ cao dần và đoạn sau sẽ thấp dần,

Ví dụ: Đây là 1 số trận đồ nhất quái:  

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

Chưa xong, muốn tu luyện được Bí Kíp Luyện Code thì phải thêm 1 bước nữa, đó là xây dựng lên Trận đồ nhị quái. Trận đồ nhị quái tương tự như trận đồ nhất quái, nhưng kèm thêm k yêu cầu có dạng: “x[i] sign y[i]”. Trong đó x[i], y[i] là vị trí các cột trong trận đồ (được đánh số từ 1 -> 2*n), sign là 1 trong dấu so sánh: ‘=’ (bằng); ‘<’ (bé hơn); ‘<=’(bé hơn hoặc bằng); ‘=’(bằng); ‘>=’(lớn hơn hoặc bằng), ‘>’(lớn hơn).

Ví dụ: yêu cầu 2 > 5 tức là cột ở vị trí 2 bắt buộc phải cao hơn cột vị trí 5
           yêu cầu 4 <= 5 tức là cột ở vị trí 4 bắt buộc phải thấp hơn hoặc cao bằng cột ở vị trí 5.

Hãy giúp Tôn Ngộ Có tính toán xem có tất cả bao nhiêu Trận đồ nhị quái!

Input

Dòng thứ nhất bao gồm 2 số tự nhiên n, k (1 <= n <= 35, 0 <= k <= 100) – Số cặp gậy như ý và số yêu cầu cho trận đồ nhị quái

k dòng tiếp theo, mỗi dòng có dạng “x[i] sign y[i]” (1 <= x[i], y[i] <= 2*n) và sign là 1 trong 5 dấu so sánh ở trên.

Output

In ra kết quả bài toán là số Trận đồ nhị quái có thể tạo được.

Example

Test 1:

Input:

1 0

Output:

1

Test 2:

Input:

5 2

2 < 3

4 > 5

Output:

10

Test 3:

Input:

4 1

3 = 6

Output:

3

Bảng xếp hạng ACM PTIT (NEW)