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

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

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

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

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

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


รูปภาพประกอบตัวอย่างข้อมูลนำเข้าที่ 2

• รูปแบบกองขวดน้ำทั้งหมดของชายเลย์ที่มีฐานเป็นขวดน้ำ 4 ขวด
• วงกลมแทนขวดน้ำแต่ละขวด

ที่มา
IOI Thailand League 2010 เดือน เมษายน

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