Temukan banyaknya pohon biner (pohon biner adalah pohon berakar yang setiap verteksnya memiliki paling banyak satu anak kiri dan paling banyak satu anak kanan) dengan $N$ verteks berlabel $1, 2, \dots, N$ yang memenuhi semua kondisi berikut, dan keluarkan hasilnya modulo $998244353$.
- Untuk setiap $i = 1, 2, \dots, N$, indeks preorder dari verteks $i$ adalah $i$. Secara khusus, verteks $1$ adalah akarnya.
- Untuk setiap $i = 1, 2, \dots, M$, indeks inorder dari verteks $A_i$ adalah $B_i$.
Dua pohon biner dianggap berbeda jika terdapat sebuah verteks $v$ sedemikian sehingga setidaknya salah satu dari hal berikut berlaku:
- Keberadaan atau nomor verteks dari anak kiri $v$ berbeda.
- Keberadaan atau nomor verteks dari anak kanan $v$ berbeda.
Indeks preorder dan indeks inorder dari setiap verteks $v$ dalam sebuah pohon biner didefinisikan sebagai nilai yang tercatat masing-masing pada preorder[v] dan inorder[v], ketika menjalankan dfs(root) pada pseudocode berikut:
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)Masukan
Masukan diberikan dalam format berikut:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Semua nilai masukan adalah bilangan bulat.
- $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$)
Keluaran
Keluarkan jawaban pada satu baris.
Contoh
Masukan 1
3 1 2 1
Keluaran 1
2
Masukan 2
5 3 1 3 2 5 4 2
Keluaran 2
0
Masukan 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Keluaran 3
550222816
Catatan
Pada contoh pertama, terdapat tepat dua pohon biner yang memenuhi kondisi. Pohon pertama memiliki verteks $1$ sebagai akar, verteks $2$ sebagai anak kiri dari verteks $1$, dan verteks $3$ sebagai anak kanan dari verteks $2$. Pohon lainnya memiliki verteks $1$ sebagai akar, verteks $2$ sebagai anak kiri dari verteks $1$, dan verteks $3$ sebagai anak kanan dari verteks $1$. Indeks preorder dan inorder keduanya konsisten dengan batasan yang diberikan.
Pada contoh kedua, tidak ada pohon biner yang memenuhi kondisi.