+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت + روز ۳ دوره ۳۱ ---------- مهرداد به تازگی فهمیده که با جایگشت فروشی می‌تواند پول خوبی بدست بیاورد. مهرداد مغازه‌ای خرید و حال می‌خواهد از هر جایگشت یکی بخرد و به مغازه‌اش بیاورد. آرین دلال جایگشت‌ها است و قیمت گذاری جایگشت‌ها را او تعیین می‌کند. او که از المپیاد کامپیوتری‌های سابق می‌باشد، به روش عجیبی قیمت‌گذاری را انجام می‌دهد که در ادامه با آن آشنا می‌شوید. جایگشت $\langle p_1, p_2, ..., p_n \rangle$ را در نظر بگیرید. قدرت عضو $i$ام را با $a_i$ نشان می‌دهیم. بزرگترین عدد $j$ را در نظر بگیرید که $j < i$ و $p_j > p_i$ باشد. اگر هیچ $j$ با خواص گفته شده وجود نداشته باشد، آنگاه $a_i = 1$ و در غیر این صورت $a_i = a_j + 1$ می‌باشد. همت عضو $i$ام را با $b_i$ نشان می‌دهیم. کوچکترین عدد $j$ را در نظر بگیرید که $j > i$ و $p_j > p_i$ باشد. اگر هیچ $j$ با خواص گفته شده وجود نداشته باشد، آنگاه $b_i = 1$ و در غیر این صورت $b_i = b_j + 1$ می‌باشد. آرین یک عدد طبیعی $k$ انتخاب می‌کند و قیمت جایگشت $\langle p_1, p_2, ..., p_n \rangle$ را برابر $\sum_{i=1}^{n} (a_i + b_i)^k$ قرار می‌دهد. مهرداد که می‌خواهد از هر جایگشت دقیقا یکی بخرد، از شما می‌خواهد به او بگویید به چه مقدار پول احتیاج دارد. # ورودی در خط اول دو عدد طبیعی $n$ و $k$ به ترتیب می‌آیند. $$2 \leq n \leq 5000$$ $$0 \leq k \leq 5000$$ # خروجی باقیمانده تقسیم مقدار پولی که مهرداد باید برای خرید تمامی جایگشت‌ها به آرین پرداخت کند بر $10^9 + 7$ را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۳ | $k = 0$ | | ۲ | ۵ | $n \leq 7$ | | ۳ | ۱۵ | $k \leq 1$ | | ۴ | ۲۳ | $k \leq 2$ | | ۵ | ۲۶ | $n \leq 500$ | | ۶ | ۲۸ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 2 1 ``` ## خروجی نمونه ۱ ``` 10 ``` ## ورودی نمونه ۲ ``` 5 2 ``` ## خروجی نمونه ۲ ``` 7928 ``` ## ورودی نمونه ۳ ``` 5 3 ``` ## خروجی نمونه ۳ ``` 32376 ``` ## ورودی نمونه ۴ ``` 124 274 ``` ## خروجی نمونه ۴ ``` 796626652 ```