다음 조건을 모두 만족하는, $1, 2, \dots, N$의 번호가 붙은 $N$개의 정점을 가진 이진 트리(이진 트리란 각 정점이 최대 하나의 왼쪽 자식과 최대 하나의 오른쪽 자식을 가지는 루트 있는 트리를 말합니다)의 개수를 구하고, 그 결과를 $998244353$으로 나눈 나머지를 출력하세요.
- 각 $i = 1, 2, \dots, N$에 대하여, 정점 $i$의 전위 순회 인덱스(preorder index)는 $i$입니다. 특히, 정점 $1$은 루트입니다.
- 각 $i = 1, 2, \dots, M$에 대하여, 정점 $A_i$의 중위 순회 인덱스(inorder index)는 $B_i$입니다.
두 이진 트리는 다음 중 적어도 하나가 성립하는 정점 $v$가 존재할 때 서로 다른 것으로 간주합니다:
- $v$의 왼쪽 자식의 존재 여부 또는 정점 번호가 다릅니다.
- $v$의 오른쪽 자식의 존재 여부 또는 정점 번호가 다릅니다.
이진 트리의 각 정점 $v$의 전위 순회 인덱스와 중위 순회 인덱스는 다음 의사코드에서 dfs(root)를 실행했을 때 각각 preorder[v]와 inorder[v]에 기록되는 값으로 정의됩니다:
pre_cnt = 1; in_cnt = 1
def dfs(v):
preorder[v] = pre_cnt; pre_cnt += 1
if v has a left child:
dfs(left child of v)
inorder[v] = in_cnt; in_cnt += 1
if v has a right child:
dfs(right child of v)입력
입력은 다음 형식으로 주어집니다:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- 모든 입력값은 정수입니다.
- $1 \le M \le N \le 500$
- $1 \le A_i, B_i \le N$
- $A_i \ne A_j$ ($i \ne j$)
- $B_i \ne B_j$ ($i \ne j$)
출력
정답을 한 줄에 출력합니다.
예제
예제 입력 1
3 1 2 1
예제 출력 1
2
예제 입력 2
5 3 1 3 2 5 4 2
예제 출력 2
0
예제 입력 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
예제 출력 3
550222816
노트
첫 번째 예제에서는 조건을 만족하는 이진 트리가 정확히 두 개 있습니다. 하나는 정점 $1$을 루트로 하고, 정점 $2$를 정점 $1$의 왼쪽 자식으로, 정점 $3$을 정점 $2$의 오른쪽 자식으로 가집니다. 다른 하나는 정점 $1$을 루트로 하고, 정점 $2$를 정점 $1$의 왼쪽 자식으로, 정점 $3$을 정점 $1$의 오른쪽 자식으로 가집니다. 두 트리의 전위 순회 및 중위 순회 인덱스는 주어진 제약 조건과 일치합니다.
두 번째 예제에서는 조건을 만족하는 이진 트리가 없습니다.