ในการพิจารณาว่าต้นไม้มีรากสมสัณฐานกัน (isomorphic) หรือไม่ (ในโจทย์ข้อนี้ คุณไม่จำเป็นต้องมีความรู้เรื่องการสมสัณฐานของต้นไม้มาก่อน) อัลกอริทึมหนึ่งที่นิยมใช้คือการแฮชต้นไม้ (tree hashing) หากใช้ฟังก์ชันแฮชที่เหมาะสม ต้นไม้มีรากที่ไม่สมสัณฐานกันก็มักจะให้ค่าแฮชที่แตกต่างกัน แต่การชนกันของค่าแฮช (hash collision) ก็ยังยากที่จะหลีกเลี่ยง
ฟังก์ชันแฮชมีการนำไปใช้งานหลากหลายรูปแบบ แต่การออกแบบฟังก์ชันแฮชบางแบบก็ไม่ค่อยถูกต้องนัก Little C มีฟังก์ชันแฮชที่ "ไม่ค่อยถูกต้องนัก" อยู่ฟังก์ชันหนึ่ง ซึ่งนิยามดังนี้: ให้ $sz_x$ เป็นจำนวนจุดที่อยู่ในต้นไม้ย่อยของ $x$ และ $son_x$ เป็นเซตของโหนดลูกทั้งหมดของ $x$ สำหรับต้นไม้มีรากที่มี $r$ เป็นราก ค่าแฮช $h(r)$ ของมันนิยามว่า:
$$h(r) = 1 + \sum_{v \in son_r} h(v) \times f(sz_v)$$
โดยที่ $f$ แทนการส่งค่า (mapping) ใด ๆ จากเซตของจำนวนเต็มบวกไปยังเซตของจำนวนเต็มบวก กล่าวคือ $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$ โดยเฉพาะอย่างยิ่ง ค่าแฮชของต้นไม้มีรากที่มีเพียงโหนดเดียวคือ $1$
ถัดไป Little C นิยามว่าสำหรับต้นไม้มีรากสองต้น หากสำหรับทุกการเลือก $f$ เป็นไปไม่ได้เลยที่จะคำนวณได้ค่าแฮชที่แตกต่างกัน จะกล่าวว่าต้นไม้ทั้งสองต้นนั้นแยกแยะไม่ได้ (indistinguishable) มิฉะนั้น หากมีการเลือก $f$ ที่ทำให้ต้นไม้ทั้งสองต้นคำนวณได้ค่าแฮชที่แตกต่างกัน จะกล่าวว่าต้นไม้ทั้งสองต้นนั้นแยกแยะได้ (distinguishable)
Little C ต้องการใช้ฟังก์ชันแฮชนี้เพื่อสร้างต้นไม้ทวิภาคมีราก (rooted binary trees) ให้ได้มากที่สุดเท่าที่จะเป็นไปได้ ซึ่งก็คือต้นไม้มีรากที่แต่ละโหนดมีโหนดลูกไม่เกินสองโหนด Little C หวังว่าคุณจะสามารถคำนวณจำนวนสูงสุดของต้นไม้ทวิภาคมีรากที่มี $n$ โหนดและแยกแยะออกจากกันได้ทั้งหมด แน่นอนว่าคำตอบอาจมีค่าใหญ่มาก ดังนั้น Little C จึงได้เตรียมค่ามอดุลัส $p$ ไว้ให้คุณ และคุณต้องนำผลลัพธ์ที่ได้มาหาเศษเหลือมอดุโล $p$
ข้อมูลนำเข้า
โจทย์ข้อนี้มีหลายชุดข้อมูลทดสอบ บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็ม $T$ ($1 \le T \le 10000$) แทนจำนวนชุดข้อมูลทดสอบ
สำหรับแต่ละชุดข้อมูลทดสอบ ข้อมูลนำเข้าประกอบด้วยบรรทัดเดียวที่มีจำนวนเต็มสองจำนวน คือ $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$) แทนจำนวนโหนดในต้นไม้มีรากและค่ามอดุลัสที่ Little C เตรียมไว้ให้ตามลำดับ
รับประกันว่าผลรวมของ $n$ จากทุกชุดข้อมูลทดสอบรวมกันไม่เกิน $10000$
ข้อมูลส่งออก
สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลหนึ่งบรรทัดที่มีจำนวนเต็มหนึ่งจำนวน แทนผลลัพธ์ของคำตอบมอดุโล $p$
ตัวอย่าง
ข้อมูลนำเข้าตัวอย่าง 1
8 1 1000000009 5 1000000009 10 1000000009 15 1000000009 100 1000000009 150 1000000009 1000 1000000009 1500 1000000009
ข้อมูลส่งออกตัวอย่าง 1
1 6 207 10904 478868953 202933416 152259136 264735211