จงหาจำนวนของต้นไม้ทวิภาค (ต้นไม้ทวิภาคคือต้นไม้มีรากที่แต่ละจุดยอดมีลูกทางซ้ายได้ไม่เกินหนึ่งจุดและมีลูกทางขวาได้ไม่เกินหนึ่งจุด) ที่มีจุดยอด $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$ ดัชนีแบบปรีออร์เดอร์และอินออร์เดอร์ของทั้งสองต้นสอดคล้องกับเงื่อนไขที่กำหนดให้
ในตัวอย่างที่สอง ไม่มีต้นไม้ทวิภาคใดที่สอดคล้องกับเงื่อนไข