วันหนึ่ง JOI-kun ได้เครื่องย้อนเวลามา เขาตัดสินใจเดินทางไปยังประเทศญี่ปุ่นในคริสต์ศตวรรษที่ 9 เขาได้พบกับ Kukai ซึ่งเป็นหนึ่งในพระสงฆ์ที่มีชื่อเสียงที่สุดในญี่ปุ่นในขณะนั้น พระสงฆ์รูปนี้ต้องการพัฒนาวิธีฝึกตนแบบใหม่
การฝึกตนของเขาดำเนินไปดังนี้:
- Kukai อ่านพระสูตรที่มี $N$ ประโยค ประโยคเหล่านี้มีลำดับกำหนดไว้ และเขาต้องอ่านตามลำดับ
- แต่ละประโยคมีจำนวนเต็มหนึ่งจำนวนตั้งแต่ $1$ ถึง $N$ รวมปลายทั้งสอง ไม่มีประโยคสองประโยคที่ต่างกันซึ่งมีจำนวนเดียวกัน
- เขาต้องอ่านประโยคที่มีจำนวนเต็ม $i$ ($1 \le i \le N$) ในช่วงเวลาที่ $i$ จากทั้งหมด $N$ ช่วงเวลาที่แบ่งวันหนึ่งออกเป็นส่วนเท่า ๆ กัน แต่ละประโยคสั้นมากจนเขาสามารถอ่านจบภายในหนึ่งช่วงเวลาได้เสมอ
Kukai ต้องการอ่านพระสูตรทั้งหมดให้จบโดยเร็วที่สุด อย่างไรก็ตาม จำนวนวันที่เขาต้องใช้ในการอ่านจนจบขึ้นอยู่กับจำนวนเต็มที่กำกับประโยคต่าง ๆ ในพระสูตร Kukai ขอให้ JOI-kun นับจำนวนวิธีกำหนดจำนวนเต็มให้กับประโยคที่ทำให้ Kukai ใช้เวลาอ่านจบพอดี $K$ วัน หากเขาอ่านด้วยวิธีที่ดีที่สุด
งานที่ต้องทำ
กำหนดจำนวนประโยค $N$ และจำนวนเต็ม $K$ ให้คำนวณจำนวนวิธีกำหนดจำนวนเต็มให้กับประโยคที่ทำให้ Kukai ใช้เวลาอ่านจบพอดี $K$ วัน หากเขาอ่านด้วยวิธีที่ดีที่สุด โดยหาคำตอบโมดูโล $1\,000\,000\,007$
ข้อมูลนำเข้า
อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน
- บรรทัดแรกของข้อมูลนำเข้ามี $N$ และ $K$ คั่นด้วยช่องว่างหนึ่งช่อง
ข้อมูลส่งออก
พิมพ์จำนวนวิธีกำหนดจำนวนเต็มให้กับประโยคที่ทำให้ Kukai ใช้เวลาอ่านจบพอดี $K$ วัน หากเขาอ่านด้วยวิธีที่ดีที่สุด โดยหาคำตอบโมดูโล $1\,000\,000\,007$
ข้อจำกัด
ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้
- $1 \le N \le 100\,000$
- $1 \le K \le N$
งานย่อย
มีงานย่อยทั้งหมด 4 งาน คะแนนและข้อจำกัดเพิ่มเติมของแต่ละงานย่อยมีดังนี้:
งานย่อย 1 [4 คะแนน]
- $N \le 10$
งานย่อย 2 [20 คะแนน]
- $N \le 300$
งานย่อย 3 [25 คะแนน]
- $N \le 3\,000$
งานย่อย 4 [51 คะแนน]
ไม่มีข้อจำกัดเพิ่มเติม
ตัวอย่าง
ข้อมูลนำเข้า 1
3 2
ข้อมูลส่งออก 1
4
หมายเหตุ
มีวิธีกำหนดจำนวนเต็มให้กับประโยคทั้งหมด 4 วิธีที่ทำให้เขาใช้เวลาอ่านจบ 2 วัน
- ประโยคแรกมีจำนวน $1$ ประโยคถัดไปมีจำนวน $3$ และประโยคสุดท้ายมีจำนวน $2$ เขาอ่านสองประโยคแรก (ซึ่งมีหมายเลข $1$ และ $3$ ตามลำดับ) ในวันแรก และอ่านประโยคสุดท้าย (ซึ่งมีหมายเลข $2$) ในวันที่สอง
- ประโยคแรกมีจำนวน $2$ ประโยคถัดไปมีจำนวน $1$ และประโยคสุดท้ายมีจำนวน $3$
- ประโยคแรกมีจำนวน $2$ ประโยคถัดไปมีจำนวน $3$ และประโยคสุดท้ายมีจำนวน $1$
- ประโยคแรกมีจำนวน $3$ ประโยคถัดไปมีจำนวน $1$ และประโยคสุดท้ายมีจำนวน $2$
ข้อมูลนำเข้า 2
10 5
ข้อมูลส่งออก 2
1310354