Для последовательности a из n целых чисел от 1 до m, включительно, введём обозначение f(a) — количество различных подпоследовательностей a (включая пустую подпоследовательность).
Вам заданы два положительных целых числа n и m. Пусть S это множество всех последовательностей длины n с элементами от 1 до m. Найдите значение суммы f(a) по всем a из S по модулю 109 + 7.
Выходные данные
Выведите одно целое число c — искомую сумму по модулю 109 + 7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 3
|
6
|
|
2
|
2 2
|
14
|
|
3
|
3 3
|
174
|