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

---

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

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