2010 : Fish
Problem type : Batch
Time limit : 3.0 second(s)
Memory limit : 64 megabyte(s)

Scheherazade ได้บอกเล่าว่าในกลางทะเลทรายที่อยู่ไกลแสนไกล มีทะเลสาบแห่งหนึ่ง   เดิมทีในทะเลสาบแห่งนี้มีปลาทั้งสิ้น F ตัว   อัญมณี K ประเภทที่มีค่ามากที่สุดในโลก ถูกเลือกขึ้นมาให้ปลากิน โดยที่ปลาแต่ละตัวจะได้กินอัญมณีหนึ่งชิ้นเท่านั้น   สังเกตว่าเนื่องจาก K อาจมีค่าน้อยกว่า F ได้  ดังนั้น อาจมีปลาหลายตัวกินอัญมณีประเภทเดียวกันได้

 

กาลเวลาผ่านไป ปลาบางตัวอาจกินปลาตัวอื่น ๆ  ปลาตัวหนึ่งสามารถกินตัวอื่นได้ก็ต่อเมื่อปลาตัวนั้นมีความยาวมากกว่าสองเท่าของปลาอีกตัวหนึ่ง (ปลา A สามารถกินปลา B ได้ก็ต่อเมื่อ L_A >= 2 * L_B)  ในการกินกันนั้นไม่มีกติกาใดๆ  ปลาตัวหนึ่งอาจตัดสินใจกินปลาที่เล็กกว่าหลายตัวต่อกันไป ในขณะที่ปลาบางตัวอาจตัดสินใจไม่กินปลาอื่นเลย ถึงแม้ว่ามันสามารถกินได้ก็ตาม   เมื่อปลาตัวหนึ่งกินปลาตัวที่เล็กกว่า ความยาวของมันจะไม่เปลี่ยนแปลง แต่อัญมณีในท้องปลาตัวเล็กก็จะมาอยู่ในท้องปลาตัวใหญ่กว่า

 

Scheherazade  บอกว่าถ้าคุณสามารถหาทะเลสาบแห่งนี้พบ คุณจะสามารถจับปลาได้เพียงหนึ่งตัวและเก็บอัญมณีทั้งหมดในท้องปลาเป็นของคุณ   คุณพอใจที่จะทดสอบโชคชะตา แต่ก่อนจะออกเดินทางอันแสนยาวไกล คุณอยากทราบจำนวน combination ที่แตกต่างกันของอัญมณีที่คุณสามารถจะได้รับจากการจับปลาหนึ่งตัว

 

โจทย์

เขียนโปรแกรมที่รับความยาวของปลาแต่ละตัวและประเภทของอัญมณีที่ปลากินเมื่อตอนเริ่มต้น แล้วคำนวณหาจำนวน combination ที่แตกต่างกันของอัญมณีที่สามารถไปอยู่ในท้องของปลาตัวหนึ่ง  โดยตอบเป็นเศษเหลือจากการหารด้วยจำนวนเต็ม M (modulo M)  เราจะนิยาม combination ด้วยจำนวนของอัญมณีแต่ละประเภทจาก K ประเภท  โดยไม่คำนึงถึงลำดับของอัญมณี และอัญมณีประเภทเดียวกันสองชิ้นจะไม่นับว่าแตกต่างกัน

 

เงื่อนไข

1 <= F <= 500,000                  จำนวนปลาเริ่มต้นในทะเลสาบ

1 <= K <= F                             จำนวนของประเภทอัญมณี

2 <= M <= 30,000

1 <= L_x <= 1,000,000,000       ความยาวของปลาตัวที่ x

 

 

ข้อมูลนำเข้า

โปรแกรมของคุณจะต้องอ่านข้อมูลเหล่านี้จาก standard input:

·       บรรทัดที่ 1 ระบุจำนวนเต็ม F แทนจำนวนปลาเริ่มต้นในทะเลสาบ

·       บรรทัดที่ 2 ระบุจำนวนเต็ม K แทนจำนวนประเภทของอัญมณี

ประเภทของอัญมณีจะแทนด้วยจำนวนเต็มตั้งแต่ 1 ถึง K

·       บรรทัดที่ 3 ระบุจำนวนเต็ม M

·       แต่ละ F บรรทัดถัดมา ระบุข้อมูลของปลาแต่ละตัว ด้วยจำนวนเต็ม 2 จำนวน คั่นด้วยช่องว่างหนึ่งช่อง โดยจำนวนแรกแทนความยาวของปลา ตามด้วยประเภทของอัญมณีที่ปลาตัวนั้นกิน ณ ตอนเริ่มต้น

หมายเหตุ  สำหรับทุก ๆ ข้อมูลชุดทดสอบในการประเมิน รับประกันว่าจะต้องมีอัญมณีครบทั้ง K ประเภท

 

ข้อมูลส่งออก

โปรแกรมของคุณจะต้องเขียนผลลัพธ์หนึ่งบรรทัดไปยัง standard output ซึ่งระบุจำนวนเต็มหนึ่งจำนวนที่มีค่าตั้งแต่ 0 ถึง M - 1 แทนจำนวน combination ที่เป็นไปได้ที่แตกต่างกันของอัญมณี modulo ด้วย M

สังเกตว่าในการแก้ปัญหานี้ ค่าของ M ไม่มีความสำคัญใด ๆ นอกจากทำให้การคำนวณง่ายขึ้น

 

การให้คะแนน

ในข้อมูลชุดทดสอบที่มีคะแนนรวม 70 คะแนน จำนวนเต็ม K จะมีค่าไม่เกิน 7,000

นอกจากนี้ ในบางข้อมูลชุดทดสอบข้างต้นที่มีคะแนนรวม 25 คะแนน จำนวนเต็ม K จะมีค่าไม่เกิน 20

 

อธิบายตัวอย่างที่หนึ่ง(ด้านล่าง)

มี combination ที่เป็นไปได้ทั้งสิ้น 11 แบบ ดังนั้นคุณจะต้องรายงานผลลัพธ์เป็น 11 modulo 7 ซึ่งก็คือ 4  โดย combination ที่เป็นไปได้คือ: [1] [1,2] [1,2,3] [1,2,3,3] [1,3] [1,3,3] [2] [2,3] [2,3,3] [3] และ [3,3]

(ในแต่ละ combination เราแสดงอัญมณีที่อยู่ใน combination นั้น  ตัวอย่างเช่น [2,3,3] คือ combination ที่มีอัญมณีประเภทที่สองหนึ่งชิ้น และอัญมณีประเภทที่สามอีกสองชิ้น)

 

combination ข้างต้นสามารถทำได้ดังนี้:

·       [1]: เป็นไปได้ว่าคุณจับได้ปลาตัวที่สอง (หรือตัวที่สี่) ก่อนที่มันจะกินปลาตัวอื่น

·       [1,2]:  ถ้าปลาตัวที่สองกินปลาตัวที่หนึ่ง มันจะมีทั้งอัญมณีประเภทที่ 1 (ที่มันกินมาเมื่อเริ่มต้น)  และอัญมณีประเภทที่ 2 (จากท้องของปลาตัวที่หนึ่ง)

·       [1,2,3]:  ทางหนึ่งที่จะได้ combination นี้ก็คือ ปลาตัวที่สี่กินปลาตัวที่หนึ่ง จากนั้นปลาตัวที่สามกินปลาตัวที่สี่ ถ้าคุณจับปลาตัวที่สามได้ มันมีอัญมณีแต่ละประเภทในท้องของมัน

·       [1,2,3,3]: ปลาตัวที่สี่กินปลาตัวที่หนึ่ง ปลาตัวที่สามกินปลาตัวที่สี่และปลาตัวที่ห้า  จากนั้นคุณจับปลาตัวที่สามได้

·       [1,3]: ปลาตัวที่สามกินปลาตัวที่สี่ และคุณจับปลาตัวที่สามได้

·       [1,3,3]: ปลาตัวที่สามกินปลาตัวที่ห้า ปลาตัวที่สามกินปลาตัวที่สี่ จากนั้นคุณจับปลาตัวที่สามได้

·       [2]: คุณจับปลาตัวที่หนึ่งได้

·       [2,3]: ปลาตัวที่สามกินปลาตัวที่หนึ่ง และคุณจับปลาตัวที่สามได้

·       [2,3,3]: ปลาตัวที่สามกินปลาตัวที่หนึ่ง ปลาตัวที่สามกินปลาตัวที่ห้า และคุณจับปลาตัวที่สามได้

·       [3]: คุณจับปลาตัวที่สามได้

·       [3,3]: ปลาตัวที่สามกินปลาตัวที่ห้า คุณจับปลาตัวที่สามได้

 

ที่มา: 20^th International Olympiad in Informatics; Cairo, Egypt (Day 1)

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
5 3 7 2 2 5 1 8 3 4 1 2 3	4

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้