آقا داوود به تازگی با جایگشت‌های پایدار آشنا شده است. از دید او جایگشتی پایدار است که اگر $K$ بار بر روی خودش اعمال شود، تغییری نکند. توجه داشته باشید که بر اثر اعمال جایگشت $B$ بر روی جایگشت $A$ جایگشت جدیدی حاصل می‌شود که عدد $i$ام آن برابر $A_{B_i}$ است ( $A_x$ نمایانگر $x$امین عدد جایگشت $A$ است). حال آقا داوود از شما خواسته است که تعداد جایگشت های پایدار به طول $N$ را به دست آورید

• در تنها خط ورودی به ترتیب دو عدد $N$ و $K$ آمده است ($1 \leq N, K \leq 100000$).
• در حداقل ۶۰ درصد از ورودی‌ها، $1 \leq N, K \leq 5000$ است.

در تنها خط خروجی باقی‌مانده‌ی تعداد جایگشت‌های پایدار به طول $N$ را بر ${10}^9+7$ چاپ کنید.

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

• سوال بعد
• سوال قبل