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

---

در شهر آبابوا به دنباله، امیرمحمد می‌گویند، هم‌چنین به دنباله‌هایی که به ازای هر \(i\) که 1 < \(a_i\) حداقل یکی از دو عدد \(a_i\) و \(a_i-1\) سمت چپ مکان \(i\) ظاهر نشده باشند، ایمانی می‌گویند. (منظور از سمت چپ، تمام خانه‌های قبل از خانه \(i\) است، نه تنها خانه‌ی قبلی)
مثلا \(<2, 2, 1>\) یک امیرمحمد ایمانی معتبر است و \(<1, 2, 2>\) یک امیرمحمد ایمانی معتبر نیست.
اهالی شهر آبابوا به سوالی مهم برخورده‌اند و از شما درخواست کمک دارند: چند امیرمحمد ایمانی به طول \(n\) با اعداد \(1\) تا \(m\) داریم؟

ورودی

سطر اول وروی شامل دو عدد \(n\) و \(m\) است که \(n\) طول مورد‌نظر برای امیرمحمد ایمانی است و امیرمحمد ایمانی فقط می‌تواند شامل اعداد \(1\) تا \(m\) باشد. \[1 \le n, m \le 500\]

خروجی

در خروجی باید تنها یک عدد چاپ کنید که جواب سوال مردم آبابوا است. از آنجا که این عدد می‌تواند خیلی بزرگ باشد باقی‌مانده آن بر \(10^9 + 7\) را چاپ کنید.

زیر مسئله ها

زیرمسئله	نمره	محدودیت ها
۱	۴	\(n, m \le 8\)
۲	۳۲	\(n, m \le 200\)
۳	۶۴	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

2 2

خروجی نمونه ۱

4

ورودی نمونه ۲

3 2

خروجی نمونه ۲

6