در شهر آبابوا به دنباله، امیرمحمد می‌گویند، هم‌چنین به دنباله‌هایی که به ازای هر $i$ که $1 < i$ ، حداقل یکی از دو عدد $a_i$ و $a_i - 1$ سمت چپ مکان $i$ ظاهر نشده باشند، ایمانی می‌گویند. (منظور از سمت چپ، تمام خانه‌های قبل از خانه $i$ است، نه تنها خانه‌ی قبلی)

مثلاً $<2, 2, 1>$ یک امیرمحمد ایمانی معتبر است و $<1, 2, 2>$ یک امیرمحمد ایمانی معتبر نیست.

اهالی شهر آبابوا به سوالی مهم برخورده‌اند و از شما درخواست کمک دارند: چند امیرمحمد ایمانی به طول $n$ با اعداد $1$ تا $m$ داریم؟

سطر اول ورودی شامل دو عدد $n$ و $m$ است که $n$ طول مورد‌نظر برای امیرمحمد ایمانی است و امیرمحمد ایمانی فقط می‌تواند شامل اعداد $1$ تا $m$ باشد.

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

• $1 \le n, m \le 500$

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

در مثال اول، هر ۴ دنباله ممکن معتبر هستند.

در مثال دوم، تنها ۲ دنباله $<1, 2, 2>$ و $<2, 1, 2>$ از ۸ حالت ممکن نامعتبر هستند، در نتیجه جواب برابر با ۶ است.