1079 : หม้อวิเศษ (pot)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

      งานเลี้ยงฉลองการแข่งขัน...ได้ถูกจัดขึ้นในคฤหาสน์หรูหรากลางป่าใหญ่ คุณได้รับมอบหมายหน้าที่ให้เป็นหัวหน้างานจัดเตรียมความเรียบร้อยในงานนี้ ตั้งแต่ทำความสะอาด ถูพื้น จัดโต๊ะ เตรียมอาหาร ยกของว่าง ต้อนรับแขก และอีกมากมาย

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

      ในวันวันหนึ่งแม่ครัวสามารถหุงข้าวได้หลายครั้ง และในแต่ละครั้งก็จะได้ข้าวชนิดแตกต่างกันออกไป  แต่หม้อหุงข้าวเจ้าปัญหาจะมีลำดับการหุงที่แน่นอนอีกด้วย (เช่น หุงครั้งแรกของวันจะได้ข้าวสวย ครั้งที่สองได้ข้าวต้ม ครั้งที่สามได้ข้าวผัด เสมอ) ซึ่งในการหุงข้าวแต่ละครั้งอาจหุงข้าวได้หนึ่งจานหรือมากกว่าหนึ่งจานก็ได้

      แม่ครัวของคุณต้องหุงข้าว N จานให้แขก N คนที่จะมาเยี่ยมในวันนี้ หม้อหุงข้าววิเศษสามารถหุงข้าวได้จำนวนไม่เกิน K จานต่อครั้ง เนื่องจากคุณเป็นคนที่ต้องวางแผนอะไรอย่างรอบคอบเสมอ คุณจึงอยากรู้ว่า คุณจะสามารถหุงข้าวให้แขกทั้งหมดออกมาได้กี่วิธี (ถ้าจำนวนวิธีมีมากกว่า 2008 วิธี ให้ตอบเศษที่ได้จากการหารจำนวนวิธีด้วย 2009)

      สมมติว่าคุณต้องหุงข้าวให้แขก 3 คน โดยหม้อหุงข้าวของคุณหุงข้าวได้ไม่เกินครั้งละ 2 จาน คุณจะหุงข้าวได้ 3 วิธีดังนี้

         ข้าวชนิดแรก 2 จาน ข้าวชนิดที่สอง 1 จาน
         ข้าวชนิดแรก 1 จาน ข้าวชนิดที่สอง 2 จาน
         ข้าวชนิดแรก 1 จาน ข้าวชนิดที่สอง 1 จาน ข้าวชนิดที่สาม 1 จาน

งานของคุณ

      เขียนโปรแกรมหาจำนวนวิธีการหุงข้าวทั้งหมดที่สามารถทำได้ โดยใช้หม้อหุงข้าววิเศษนี้

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

      บรรทัดเดียว ประกอบไปด้วยจำนวนเต็ม N (1≤N≤100,000) และ K (1≤K≤100,000) แทนจำนวนแขกที่มา และจำนวนจานที่สามารถหุงได้มากที่สุดต่อการหุงข้าวหนึ่งครั้ง ตามลำดับ

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

      จำนวนวิธีที่เป็นไปได้ทั้งหมดในการหุงข้าวให้กับแขก (ถ้าเป็นไปได้มากกว่า 2008 วิธี ให้ตอบเศษที่ได้จากการหารจำนวนวิธีด้วย 2009)

โจทย์โดย: ทักษพร กิตติอัครเสถียร
ที่มา: TOI.CPP:02-2009

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

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