- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
همان طور که می‌دانید حنا به ریاضیات علاقه خاصی دارد. او برای این که این علاقه را به دوستانش ثابت کند، آن‌ها را به چالش زیر دعوت می‌کند.
هر کدام آن‌ها باید دو عدد $n$ و $k$ را انتخاب کنند و سپس حنا تمام دنباله‌های شامل اعداد طبیعی $a_1, a_2, ..., a_m\ $ را که ویژگی‌های زیر را دارند یادداشت می‌کند.
- $1 \le m \le n$
- $1 \le a_i \le k$
- $\sum_{i=1}^{m} a_i = n$
برای مثال اگر $n = 3$ و $k = 2$ باشد، حنا دنباله‌های زیر را یادداشت می‌کند.
- $(2, 1)$
- $(1, 2)$
- $(1, 1, 1)$
دوستان حنا که از مهارت حنا شگفت زده می‌شوند از او می‌خواهند تا به ازای هر دنباله حاصل‌ضرب اعضایش را محاسبه کند و در نهایت بگوید که چند مقدار متفاوت در این بین وجود دارد (در نمونه بالا این مقدار برابر با ۲ است)؛ اما چون حنا در ضرب کردن کمی مشکل دارد از شما می‌خواهد تا به او کمک کنید و جواب دوستانش را بدهید.
ورودی
در سطر اول $n$ و $k$ به ترتیب آمده‌است.
$$1 \leq k \leq n \leq 30 , 000 $$
خروجی
در تنها سطر خروجی باقیمانده جواب مسئله را بر $10^9 + 7$ چاپ کنید.
مثال
ورودی نمونه ۱
4 2
خروجی نمونه ۱
3
مقادیر مختلف حاصل‌ضرب در این مثال ۱ و ۲ و ۴ هستند.
ورودی نمونه ۲
5 3
خروجی نمونه ۲
5
ارسال پاسخ برای این سؤال