Жители страны R живут в городе с $k$ улицами, на каждой из которых расположено по $n$ домов, упорядоченных в виде прямоугольной сетки. Изначально каждые два соседних дома соединены дорогой. Проще говоря, эти дома соединены дорожной сетью в виде прямоугольной решетки. Однако в последнее время у городских властей возникли финансовые трудности, и они не могут поддерживать такое количество дорог. Поэтому им необходимо максимально сократить количество дорог, сохранив при этом возможность добраться от любого дома до любого другого. Заметьте, что дороги на самих улицах также могут быть частично демонтированы. Нетрудно заметить, что в итоге останется ровно $kn - 1$ дорога. Пожалуйста, вычислите, сколько существует способов удовлетворить этому требованию.
Ответ выведите по модулю $P = 10^9 + 7$.
Входные данные
Одна строка, содержащая два целых числа $k$ и $n$.
Выходные данные
Выведите одно число — количество способов.
Подзадачи
| Номер теста | $k \le $ | $n \le $ |
|---|---|---|
| $1$ | $2$ | $5$ |
| $2$ | $3$ | |
| $3$ | $2$ | $10^5$ |
| $4$ | $10^9$ | |
| $5$ | $3$ | $10^4$ |
| $6$ | $4$ | |
| $7$ | $5$ | |
| $8$ | $10^9$ | |
| $9$ | $6$ | $10^3$ |
| $10$ | $10^9$ |
Для $100\%$ данных гарантируется, что $2 \le k \le 6$, $1 \le n \le 10^9$.
Примеры
Пример 1
Входные данные
2 2
Выходные данные
4