I. Последовательности

Саша изучает последовательности. Сегодня он занимается последовательностями из n чисел, каждое из которых может быть от 1 до c. Саше нравятся последовательности, в которых много одинаковых чисел идёт подряд. Поэтому для каждой последовательности a: a₁, a₂, …a_n, 1 ≤ a_i ≤ c Саша вычисляет f(a) – максимально количество подряд идущих одинаковых чисел.

Например если n = 3, c = 2, то для последовательности 1 2 2 f(a) = 2, а для последовательности 1 2 1 f(a) = 1.

Сашу интересует сумма f(a) по всем возможным последовательностям. Так как сумма может быть очень большой, он просит посчитать её по модулю 10⁹ + 7.

Формат входного файла

В первой строке входного файла находятся два числа n и c – длина последовательности и максимальное значение её элемента соответственно. (1 ≤ n ≤ 1000, 1 ≤ c ≤ 10⁹)

Формат выходного файла

Выведите сумму f(a) по всем последовательностям, по модулю 10⁹ + 7.

Пример:

Отправить решение



Версия для печати