ออกแบบต้นไม้ (acm15_design_tree)


Time limit:
1000 ms
Memory limit:
32 MB

คุณเป็นนักตกแต่งสวนอันดับหนึ่งของโลก ผู้คนต่างต้องการให้คุณมาออกแบบสวนที่บ้านของพวกเขา ทำให้คุณนั้นมีงานและเงินมากมาย จนวันหนึ่งคุณรู้สึกว่างานของคุณมันน่าเบื่อ คุณจึงพยายามคิดค้นการตกแต่งต้นไม้แบบใหม่ โดยเรียกมันว่า “ต้นไม้ซ้ายขวา” โดยลักษณะของมันมีดังนี้

  1. ต้นไม้ซ้ายขวา เป็นต้นไม้ทวิภาค (Binary tree) กล่าวคือ ณ ปมใดๆบนต้นไม้จะมีกิ่งแยกออกไปได้ไม่เกิน 2 กิ่ง (แยกออกไปได้ไม่เกิน 2 ปมย่อย) โดย 2 กิ่งที่แยกออกจากปมนั้น จะแยกออกไปทางซ้าย หรือ ทางขวาเท่านั้น เราเรียกมันว่า กิ่งซ้าย และ กิ่งขวา ตามลำดับ
  2. ต้นไม้ซ้ายขวา จะต้องมีปมรากเพียง 1 ปมเท่านั้น
  3. ต้นไม้ซ้ายขวา จะต้องมี กิ่งซ้ายเท่ากับ N กิ่ง  และ กิ่งขวาเท่ากับ M กิ่งเท่านั้น

แต่การคิดสิ่งใหม่ๆไม่ใช่เรื่องง่าย คุณจึงเริ่มวาดรูปแบบต่างๆที่เป็นไปได้ของ “ต้นไม้ซ้ายขวา” ตามเงื่อนไขเพื่ออยากทราบจำนวนของรูปแบบทั้งหมด จนกระทั้งคุณรู้สึกว่ามันเยอะมากเกินกว่าที่จะวาดได้ ทำให้คุณตัดสินใจใช้ความรู้ด้านคอมพิวเตอร์ของคุณ!

จงเขียนโปรแกรมเพื่อหาเศษจากการหารจำนวนรูปแบบของ “ต้นไม้ซ้ายขวา” ที่เป็นไปได้ทั้งหมดตามเงื่อนไข ด้วย 9999991

Input

บรรทัดแรกรับจำนวนคำถาม T (1 ≤ T ≤ 100)

บรรทัดที่ i + 1 มีจำนวนเต็มสองจำนวน ได้แก่ N แทนจำนวน “กิ่งซ้าย” และ M แทนจำนวน “กิ่งขวา” ของต้นไม้ซ้ายขวาที่ i (0 ≤ N, M ≤ 125, 1 ≤ i ≤ T)

Output

มีท้ังหมด T บรรทัด

บรรทัดที่ i ให้แสดงเศษจากการหารจำนวนรูปแบบของ “ต้นไม้ซ้ายขวา” จากคำถามที่ i ตามเงื่อนไขทั้งหมดที่มีกิ่งซ้ายเท่ากับ N และ กิ่งขวาเท่ากับ M ด้วย 9999991

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B

Select description language

Thai (raw)
English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None