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

---

مهرداد به تازگی فهمیده که با جایگشت فروشی می‌تواند پول خوبی بدست بیاورد. مهرداد مغازه‌ای خرید و حال می‌خواهد از هر جایگشت یکی بخرد و به مغازه‌اش بیاورد. آرین دلال جایگشت‌ها است و قیمت گذاری جایگشت‌ها را او تعیین می‌کند. او که از المپیاد کامپیوتری‌های سابق می‌باشد، به روش عجیبی قیمت‌گذاری را انجام می‌دهد که در ادامه با آن آشنا می‌شوید.

جایگشت \(\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