E. Командная работа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас в подчинении находится команда из N людей. Для определённой задачи вы можете выбрать непустое множество людей. Стоимость множества из x людей равна xk.

Найдите сумму стоимостей по всем непустым подмножествам людей.

Входные данные

В единственной строке содержатся два целых числа N (1 ≤ N ≤ 109), обозначающее количество людей в подчинении и число k (1 ≤ k ≤ 5000).

Выходные данные

Выведите сумму стоимостей по всем непустым подмножествам по модулю 109 + 7.

Примеры
Входные данные
1 1
Выходные данные
1
Входные данные
3 2
Выходные данные
24
Примечание

В перовом тестовом примере есть одно непустое подмножество {1} со стоимостью 11 = 1.

Во втором тестовом примере есть семь непустых подмножеств:

- {1} со стоимостью 12 = 1

- {2} со стоимостью 12 = 1

- {1, 2} со стоимостью 22 = 4

- {3} со стоимостью 12 = 1

- {1, 3} со стоимостью 22 = 4

- {2, 3} со стоимостью 22 = 4

- {1, 2, 3} со стоимостью 32 = 9

Их суммарная стоимость равна 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24.