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

Маленький пингвин Поло любит свою родную деревню. В этой деревне n домов, пронумерованных целыми числами от 1 до n. На каждом доме висит табличка с целым числом, на i-том доме висит табличка с целым числом pi (1 ≤ pi ≤ n).

Маленький пингвин Поло очень любит гулять по этой деревне. Прогулка выглядит следующим образом. Сначала он стоит около дома с номером x. Потом пингвин идет к дому, номер которого написан на табличке дома x (то есть к дому px), затем к дому, номер которого написан на табличке дома px (то есть к дому ppx), и так далее.

Известно, что:

  1. Начав прогулку от любого дома с номером от 1 до k, включительно, он может дойти до дома с номером 1.
  2. Начав прогулку от любого дома с номером от k + 1 до n, включительно, он точно не может дойти до дома с номером 1.
  3. Начав прогулку от дома с номером 1, пингвин Поло может попасть обратно к дому с номером 1 через некоторое ненулевое количество переходов от дома к дому.

Вам нужно найти, сколькими способами можно написать числа на табличках домов, чтобы описанные выше три условия выполнялись. Выведите остаток от деления этого количества на 1000000007 (109 + 7).

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

В единственной строке через пробел заданы два целых числа n и k (1 ≤ n ≤ 1000, 1 ≤ k ≤ min(8, n)) — количество домов и число k из условия.

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

В единственной строке выведите целое число — ответ на задачу по модулю 1000000007 (109 + 7).

Примеры
Входные данные
5 2
Выходные данные
54
Входные данные
7 4
Выходные данные
1728