• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

علی برای بهبود کار شرکت می‌خواهد چند نفر از اعضای شرکت که می‌توانند سوال زیر را حل کنند انتخاب کند و آن‌ها را برای آموزش پیشرفته آماده کند... تربچه که خیلی دوست دارد آموزش‌های پیشرفته را ببیند می‌خواهد این سوال را حل کند... به او کمک کنید تا این کار را انجام دهد...

برای هر عدد طبیعی فرض کنید $P_n$ مجموعه همه دنباله‌هایی از اعداد طبیعی باشد که جمع اعضای این دنباله برابر $n$ است. به عبارت دیگر: $P_n = \{ (a_1a_2a_3\dots a_m) | a_1+a_2+a_3+\dots+a_m=n\}$ اکنون ترب می‌خواهد عبارت زیر را محاسبه کند. $\sum_{(a_1a_2a_3\dots a_m) \in P_n} {a_1}^k{a_2}^k{a_3}^k\dots{a_m}^k$ به ترب کمک کنید تا این عبارت را محاسبه کند چون ممکن است پاسخ شما بسیار عدد بزرگی باشد باقی‌مانده آن را به پیمانه $10^9+7$ حساب کنید.

ورودی🔗

ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده است. $1 \le k\le 100,1 \le n\le 10^9$

خروجی🔗

در تنها سطر خروجی پاسخ مسئله را به پیمانه $10^9+7$ چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

1 1

خروجی نمونه ۱🔗

1

ورودی نمونه ۲🔗

4 2

خروجی نمونه ۲🔗

63

تمام اعضای مجموعه $P_4$ عبارت است از: $P_4=\{ (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2), (3,1), (1,3), (4) \}$ بنابراین حاصل مجموع فوق برابر است با: $1 + 4 + 4 + 4 + 16 + 9 + 9 + 16 = 63$