Мальчик Ярослав захотел на обед съесть $$$n$$$ вопперов. Сначала он ест первый воппер, затем второй, третий и так далее. Вкусность $$$i$$$-го воппера равна $$$a_i$$$.

Так как у Ярослава СДВГ, ему тяжело есть воппер, когда его вкусность не совпадает со вкусностью предыдущего съеденного воппера, поэтому сделать так он может ровно $$$m$$$ раз. Ему стало интересно, сколько существует различных последовательностей вопперов, которые он может съесть, если вкусность каждого воппера может быть любым целым числом от $$$1$$$ до $$$k$$$.

Более формально, требуется посчитать количество последовательностей $$$a$$$ длины $$$n$$$, состоящих из чисел от $$$1$$$ до $$$k$$$, таких что существует ровно $$$m$$$ индексов $$$i$$$ ($$$2 \le i \le n$$$), для которых $$$a_i \ne a_{i-1}$$$.

Так как таких последовательностей может быть очень много, выведите ответ по модулю $$$10^9 + 7$$$.

Тесты к этой задаче состоят из четырех групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Итоговый балл за каждую группу равняется максимальному баллу, полученному за эту группу тестов по всем отправленным посылкам.