Задача 2S. Новые ценики ≡

Условие

В DNS Ритейл существует n видов товаров, и продавцы-консультанты очень жалуются на их ценообразование, т.к. им часто нужно перепечатывать ценники.

Цена меняется каждый час следующим образом:

1. Сначала все виды условно расставляются в ряд слева направо по возрастанию их цен. После этого для каждого вида вычисляется его новая цена, равная сумме цен видов справа от неё.
2. А после того, как новая цена стала известна для всех видов, выполняется стандартный алгоритм (legacy-код, который никто не решается поменять), и к каждому виду применяет операцию взятия остатка от деления цены на 10⁹ + 7. Считается, что это делается для того, чтобы не было слишком больших цен.

Сегодня цены на товары равны 1, 2, 3, 4, … , n денежных единиц.

Продавцы-консультанты уже перестали каждый день удивляться новой странной цене на товары. Но им очень интересно, к чему такая система может привести в будущем, поэтому просят вас о не менее странной просьбе: выяснить сумму цен всех видов товаров в тот же день в тот же час ровно через k веков.

Считается, что в дне 24 часа. В каждом году 365 дней (В DNS ритейл не знают что такое високосные года). Век равен 100 годам.

Формат входных данных

В единственной строке входных данных находится два числа: n - количество видов товаров и k - количество веков. (1 ≤ n ≤ 50, 1 ≤ k ≤ 5).

Формат выходных данных

Выведите одно число - сумму цен через k веков.

Пояснение к примерам:

В первом примере понятно, что уже через один час цена единственного вида станет равна нулю, потому что нет товара справа от него. Так что по аналогии и через век цена будет также равна нулю. Во втором примере цены на товар выглядят следующим образом: В начале их цена [1, 2], а через час цены станут равны [2, 0], а еще через час [0, 2] и так далее. И также по аналогии через век сумма цен будет равна 2.

Примеры тестов

1 1

0

2 1

2

3 1

1704755427