1172 : ขวดน้ำ (crystal)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

ณ ค่ายแห่งหนึ่ง ซึ่งจัดโดยสมาคมสวมแว่นแห่งประเทศไทย(สสวท.) มีการเก็บขวดน้ำที่ด้านหลังห้องเรียน เพื่อรอการนำไปรีไซเคิลลดโลกร้อน
อยู่มาวันหนึ่ง "ชายเลย์" เพื่อนร่วมค่ายของคุณนำขวดน้ำมาตั้งซ้อนกันอย่างแปลกประหลาด โดยการเรียงขวดน้ำของเขามีกฎการเรียงดังนี้

  1. ที่ฐานของกองขวดน้ำประกอบไปด้วยขวดน้ำ N ขวดเรียงชิดติดกัน
  2. ขวดน้ำแต่ละขวดต้องตั้งอยู่บนขวดน้ำสองขวดที่อยู่ชั้นด้านล่าง
  3. ในชั้นที่ไม่ใช่ชั้นล่างสุด สามารถวางขวดน้ำไม่ติดกันได้
  4. ที่ค่ายมีขวดน้ำอยู่เป็นจำนวนมากมายจนถือว่าพอสำหรับการวางแบบใดๆ และขวดน้ำทุกขวดลักษณะเหมือนกันหมด
(ถ้ายังไม่เข้าใจกรุณาดูรูปภาพประกอบข้อมูลนำเข้าที่ 2)
ชายเลย์ต้องการหาวิธีการเรียงขวดน้ำทุกรูปแบบเท่าที่เป็นไปได้เขาจึงวานให้คุณช่วย

งานของคุณ
จงเขียนโปรแกรมรับจำนวนขวดที่ชายเลย์ใช้เป็นฐานของกองขวดน้ำ จากนั้นคำนวณหาจำนวนวิธีการเรียงขวดน้ำทั้งหมดที่เป็นไปได้

ข้อมูลนำเข้า
บรรทัดแรกมีจำนวนเต็มบวก N(1<=N<=1000) แทนจำนวนขวดที่ชายเลย์ใช้เป็นฐานของกองขวดน้ำ

ข้อมูลส่งออก
บรรทัดเดียว แสดงจำนวนวิธีการเรียงขวดน้ำทั้งหมด โดยตอบเป็นเศษที่เหลือจากการหารจำนวนดังกล่าวด้วย 10001


รูปภาพประกอบตัวอย่างข้อมูลนำเข้าที่ 2
  • รูปแบบกองขวดน้ำทั้งหมดของชายเลย์ที่มีฐานเป็นขวดน้ำ 4 ขวด
  • วงกลมแทนขวดน้ำแต่ละขวด
ที่มา
IOI Thailand League 2010 เดือน เมษายน

โจทย์โดย พศิน มนูรังษี

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3 5
4 14
13 2826

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

กำลังออนไลน์: 24 ผู้เยี่ยมชมและ 0 สมาชิก (4 บอท)