أوجد عدد الأشجار الثنائية (الشجرة الثنائية هي شجرة مجذرة يكون فيها لكل رأس ابن أيسر واحد على الأكثر وابن أيمن واحد على الأكثر) المكونة من $N$ رؤوس مرقمة $1, 2, \dots, N$ والتي تحقق جميع الشروط التالية، واطبع النتيجة بباقي القسمة على $998244353$.
- لكل $i = 1, 2, \dots, N$، يكون دليل المرور القبلي (preorder index) للرأس $i$ هو $i$. وعلى وجه الخصوص، الرأس $1$ هو الجذر.
- لكل $i = 1, 2, \dots, M$، يكون دليل المرور البيني (inorder index) للرأس $A_i$ هو $B_i$.
تُعتبر شجرتان ثنائيتان مختلفتين إذا وجد رأس $v$ يتحقق فيه شرط واحد على الأقل مما يلي:
- وجود الابن الأيسر للرأس $v$ أو رقم رأسه مختلف.
- وجود الابن الأيمن للرأس $v$ أو رقم رأسه مختلف.
يُعرَّف دليل المرور القبلي ودليل المرور البيني لكل رأس $v$ في شجرة ثنائية على أنهما القيمتان المسجلتان في preorder[v] و inorder[v] على التوالي عند تنفيذ dfs(root) في الكود الزائف التالي:
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$. تتوافق أدلة المرور القبلي والبيني لهما مع القيود المعطاة.
في المثال الثاني، لا توجد أي شجرة ثنائية تحقق الشروط.