#include <bits/stdc++.h>
using namespace std;
bool is_Smaller_str(string str1, string str2) {
  long long n1 = str1.length(), n2 = str2.length();
  if (n1 < n2) return true;
  if (n2 < n1) return false;
  for (int i = 0; i < n1; i++)
    if (str1[i] < str2[i])
      return true;
    else if (str1[i] > str2[i])
      return false;
  return false;
}
long long mod(long long a, long long b) {
  long long ans = a / b;
  ans *= b;
  ans = a - ans;
  return ans;
}
string find_Diff_str(string str1, string str2) {
  if (is_Smaller_str(str1, str2)) swap(str1, str2);
  string str = "";
  long long n1 = str1.length(), n2 = str2.length();
  reverse(str1.begin(), str1.end());
  reverse(str2.begin(), str2.end());
  long long carry = 0;
  for (long long i = 0; i < n2; i++) {
    long long sub = ((str1[i] - '0') - (str2[i] - '0') - carry);
    if (sub < 0) {
      sub = sub + 10;
      carry = 1;
    } else
      carry = 0;
    str.push_back(sub + '0');
  }
  for (long long i = n2; i < n1; i++) {
    long long sub = ((str1[i] - '0') - carry);
    if (sub < 0) {
      sub = sub + 10;
      carry = 1;
    } else
      carry = 0;
    str.push_back(sub + '0');
  }
  reverse(str.begin(), str.end());
  return str;
}
string find_sum_str(string str1, string str2) {
  if (str1.length() > str2.length()) swap(str1, str2);
  string str = "";
  int n1 = str1.length(), n2 = str2.length();
  reverse(str1.begin(), str1.end());
  reverse(str2.begin(), str2.end());
  int carry = 0;
  for (int i = 0; i < n1; i++) {
    int sum = ((str1[i] - '0') + (str2[i] - '0') + carry);
    str.push_back(sum % 10 + '0');
    carry = sum / 10;
  }
  for (int i = n1; i < n2; i++) {
    int sum = ((str2[i] - '0') + carry);
    str.push_back(sum % 10 + '0');
    carry = sum / 10;
  }
  if (carry) str.push_back(carry + '0');
  reverse(str.begin(), str.end());
  return str;
}
void FAST() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
long long Rselect(vector<long long> v, long long i, long long l, long long r);
long long partition(vector<long long> v, long long l, long long r);
void scanc(vector<char>& v, long long n) {
  for (long long i = 0; i < n; i++) {
    char num;
    cin >> num;
    v.push_back(num);
  }
}
void scanP(vector<pair<long long, long long> >& v, long long n) {
  for (long long i = 0; i < n; i++) {
    long long num1, num2;
    cin >> num1 >> num2;
    pair<long long, long long> p = {num1, num2};
    v.push_back(p);
  }
}
template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& vec) {
  for (auto& i : vec) {
    stream << i << ' ';
  }
  stream << '\n';
  return stream;
}
template <class T>
istream& operator>>(istream& stream, vector<T>& vec) {
  for (auto& i : vec) {
    stream >> i;
  }
  return stream;
}
void solve();
void scanN(vector<long long>& v, long long n) {
  for (long long i = 0; i < n; i++) {
    long long num;
    cin >> num;
    v.push_back(num);
  }
}
void scans(vector<string>& v, long long n) {
  for (long long i = 0; i < n; i++) {
    string s;
    cin >> s;
    v.push_back(s);
  }
}
long long modfactorial(long long n, long long p) {
  if (n >= p) return 0;
  long long result = 1;
  for (long long i = 1; i < n + 1; i++) {
    result = result * i;
    result = result % p;
  }
  return result;
}
long long MI(long long a, long long b, long long s0 = 1, long long s1 = 0) {
  long long k = b;
  if (b == 0)
    return s0;
  else {
    return MI(b, a % b, s1, s0 - s1 * (a / b));
  }
}
long long choose(long long a, long long b, long long c = (long long)1e9 + 7) {
  if (a < b) return 0;
  long long x = modfactorial(a, c);
  long long y = modfactorial(b, c);
  long long z = modfactorial(a - b, c);
  long long y_ = MI(y, c, 1, 0);
  if (y_ < 0) y_ = y_ + c;
  long long z_ = MI(z, c, 1, 0);
  if (z_ < 0) z_ = z_ + c;
  long long mul = (x * y_) % c;
  mul = (mul * z_) % c;
  return mul;
}
void SOLT() {
  int test;
  cin >> test;
  while (test--) {
    solve();
  }
}
long long modpow(long long n, long long p, long long k) {
  n = n % k;
  long long res = 1;
  while (p > 0) {
    if (p % 2 == 1) res = res * n % k;
    n = n * n % k;
    p = p / 2;
  }
  return res;
}
long long __pow(long long n, long long p) {
  long long res = 1;
  while (p > 0) {
    if (p % 2 == 1) res = res * n;
    n = n * n;
    p = p / 2;
  }
  return res;
}
long long str_mod_num(string b, long long c) {
  long long k = b.size();
  vector<long long> mod(k + 1);
  mod[0] = 1;
  for (long long i = 1; i < k + 1; i++) {
    mod[i] = 10 * mod[i - 1];
    mod[i] %= c;
  }
  long long rem = 0;
  for (long long i = k - 1; i > -1; i--) {
    long long num = b[i] - '0';
    num *= mod[k - 1 - i];
    num %= c;
    rem += num;
    rem %= c;
  }
  return rem;
}
long long str_pow_str_mod_num(string b, string n, long long c) {
  long long tr = n.size();
  long long rem = str_mod_num(b, c);
  long long time_pass = n[0] - '0';
  long long ans = modpow(rem, time_pass, c);
  for (long long i = 1; i < tr; i++) {
    time_pass = n[i] - '0';
    ans = modpow(ans, 10, c);
    ans *= modpow(rem, time_pass, c);
    ans %= c;
  }
  return ans;
}
bool isPrime(long long a) {
  for (long long i = 2; i * i <= a; ++i)
    if (a % i == 0) return false;
  return true;
}
bool useflushdivisible(long long a) {
  cout << a << endl;
  fflush(stdout);
  char sl[10];
  scanf("%s", sl);
  return sl[0] == 'y' || sl[0] == 'Y';
}
long long phi(long long n) {
  long long result = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) n = n / i;
      result = result - result / i;
    }
  }
  if (n > 1) result = result - result / n;
  return result;
}
bool cmp(pair<long long, long long> x, pair<long long, long long> y) {
  return x.first < y.first;
}
vector<long long> getfactors(long long n) {
  vector<long long> factors;
  for (long long i = 1; i < sqrt(n) + 1; i++) {
    if (n % i == 0) {
      factors.push_back(i);
      if (i != (n / i)) factors.push_back(n / i);
    }
  }
  return factors;
}
long long Binary_Search(vector<long long>& a, long long low, long long high,
                        long long key) {
  if (high < low) return a[low - 1];
  int mid = (high + low) / 2;
  if (key == a[mid])
    return a[mid];
  else if (key < a[mid])
    return Binary_Search(a, low, mid - 1, key);
  return Binary_Search(a, mid + 1, high, key);
}
double area(long long x1, long long y1, long long x2, long long y2,
            long long x3, long long y3) {
  return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0);
}
bool isInside(long long x1, long long y1, long long x2, long long y2,
              long long x3, long long y3, int x, int y) {
  double A = area(x1, y1, x2, y2, x3, y3);
  double A1 = area(x, y, x2, y2, x3, y3);
  double A2 = area(x1, y1, x, y, x3, y3);
  double A3 = area(x1, y1, x2, y2, x, y);
  return (A == A1 + A2 + A3);
}
long long log3(long long n) {
  long long j = 0;
  while (n > 0) {
    n /= 3;
    j++;
  }
  return j - 1;
}
bool isleap(long long n) {
  if (n % 4)
    return 0;
  else if (n % 100)
    return 1;
  else if (n % 400)
    return 0;
  else
    return 1;
}
int main() {
  FAST();
  srand(time(0));
  int test = 1;
  for (int tt = 1; tt <= test; tt++) {
    solve();
  }
  return 0;
}
void solve() {
  long long n, k;
  cin >> n >> k;
  long long ans = modpow(n - k, n - k, (long long)1e9 + 7);
  ans *= modpow(k, k - 1, (long long)1e9 + 7);
  ans %= (long long)1e9 + 7;
  cout << ans << endl;
}
long long Rselect(vector<long long> v, long long i, long long l, long long r) {
  if (l == r) return v[l];
  long long pivot = partition(v, l, r);
  if (pivot == i)
    return v[pivot - 1];
  else if (pivot < i) {
    return Rselect(v, i, pivot, r);
  } else {
    return Rselect(v, i, l, pivot - 2);
  }
}
long long partition(vector<long long> v, long long l, long long r) {
  long long pivot_index = rand() % (r - l + 1) + l;
  swap(v[pivot_index], v[l]);
  long long i = l + 1, j = l + 1;
  while (j <= r) {
    if (v[j] < v[l]) {
      swap(v[j], v[i]);
      i++;
    }
    j++;
  }
  swap(v[l], v[i - 1]);
  return i;
}

### Prompt

Please formulate a Cpp solution to the following problem:

Little penguin Polo loves his home village. The village has n houses, indexed by integers from 1 to n. Each house has a plaque containing an integer, the i-th house has a plaque containing integer pi (1 ≤ pi ≤ n).

Little penguin Polo loves walking around this village. The walk looks like that. First he stands by a house number x. Then he goes to the house whose number is written on the plaque of house x (that is, to house px), then he goes to the house whose number is written on the plaque of house px (that is, to house ppx), and so on.

We know that:

  1. When the penguin starts walking from any house indexed from 1 to k, inclusive, he can walk to house number 1. 
  2. When the penguin starts walking from any house indexed from k + 1 to n, inclusive, he definitely cannot walk to house number 1. 
  3. When the penguin starts walking from house number 1, he can get back to house number 1 after some non-zero number of walks from a house to a house. 



You need to find the number of ways you may write the numbers on the houses' plaques so as to fulfill the three above described conditions. Print the remainder after dividing this number by 1000000007 (109 + 7).

Input

The single line contains two space-separated integers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ min(8, n)) — the number of the houses and the number k from the statement.

Output

In a single line print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

Examples

Input

5 2


Output

54


Input

7 4


Output

1728

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool is_Smaller_str(string str1, string str2) {
  long long n1 = str1.length(), n2 = str2.length();
  if (n1 < n2) return true;
  if (n2 < n1) return false;
  for (int i = 0; i < n1; i++)
    if (str1[i] < str2[i])
      return true;
    else if (str1[i] > str2[i])
      return false;
  return false;
}
long long mod(long long a, long long b) {
  long long ans = a / b;
  ans *= b;
  ans = a - ans;
  return ans;
}
string find_Diff_str(string str1, string str2) {
  if (is_Smaller_str(str1, str2)) swap(str1, str2);
  string str = "";
  long long n1 = str1.length(), n2 = str2.length();
  reverse(str1.begin(), str1.end());
  reverse(str2.begin(), str2.end());
  long long carry = 0;
  for (long long i = 0; i < n2; i++) {
    long long sub = ((str1[i] - '0') - (str2[i] - '0') - carry);
    if (sub < 0) {
      sub = sub + 10;
      carry = 1;
    } else
      carry = 0;
    str.push_back(sub + '0');
  }
  for (long long i = n2; i < n1; i++) {
    long long sub = ((str1[i] - '0') - carry);
    if (sub < 0) {
      sub = sub + 10;
      carry = 1;
    } else
      carry = 0;
    str.push_back(sub + '0');
  }
  reverse(str.begin(), str.end());
  return str;
}
string find_sum_str(string str1, string str2) {
  if (str1.length() > str2.length()) swap(str1, str2);
  string str = "";
  int n1 = str1.length(), n2 = str2.length();
  reverse(str1.begin(), str1.end());
  reverse(str2.begin(), str2.end());
  int carry = 0;
  for (int i = 0; i < n1; i++) {
    int sum = ((str1[i] - '0') + (str2[i] - '0') + carry);
    str.push_back(sum % 10 + '0');
    carry = sum / 10;
  }
  for (int i = n1; i < n2; i++) {
    int sum = ((str2[i] - '0') + carry);
    str.push_back(sum % 10 + '0');
    carry = sum / 10;
  }
  if (carry) str.push_back(carry + '0');
  reverse(str.begin(), str.end());
  return str;
}
void FAST() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
long long Rselect(vector<long long> v, long long i, long long l, long long r);
long long partition(vector<long long> v, long long l, long long r);
void scanc(vector<char>& v, long long n) {
  for (long long i = 0; i < n; i++) {
    char num;
    cin >> num;
    v.push_back(num);
  }
}
void scanP(vector<pair<long long, long long> >& v, long long n) {
  for (long long i = 0; i < n; i++) {
    long long num1, num2;
    cin >> num1 >> num2;
    pair<long long, long long> p = {num1, num2};
    v.push_back(p);
  }
}
template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& vec) {
  for (auto& i : vec) {
    stream << i << ' ';
  }
  stream << '\n';
  return stream;
}
template <class T>
istream& operator>>(istream& stream, vector<T>& vec) {
  for (auto& i : vec) {
    stream >> i;
  }
  return stream;
}
void solve();
void scanN(vector<long long>& v, long long n) {
  for (long long i = 0; i < n; i++) {
    long long num;
    cin >> num;
    v.push_back(num);
  }
}
void scans(vector<string>& v, long long n) {
  for (long long i = 0; i < n; i++) {
    string s;
    cin >> s;
    v.push_back(s);
  }
}
long long modfactorial(long long n, long long p) {
  if (n >= p) return 0;
  long long result = 1;
  for (long long i = 1; i < n + 1; i++) {
    result = result * i;
    result = result % p;
  }
  return result;
}
long long MI(long long a, long long b, long long s0 = 1, long long s1 = 0) {
  long long k = b;
  if (b == 0)
    return s0;
  else {
    return MI(b, a % b, s1, s0 - s1 * (a / b));
  }
}
long long choose(long long a, long long b, long long c = (long long)1e9 + 7) {
  if (a < b) return 0;
  long long x = modfactorial(a, c);
  long long y = modfactorial(b, c);
  long long z = modfactorial(a - b, c);
  long long y_ = MI(y, c, 1, 0);
  if (y_ < 0) y_ = y_ + c;
  long long z_ = MI(z, c, 1, 0);
  if (z_ < 0) z_ = z_ + c;
  long long mul = (x * y_) % c;
  mul = (mul * z_) % c;
  return mul;
}
void SOLT() {
  int test;
  cin >> test;
  while (test--) {
    solve();
  }
}
long long modpow(long long n, long long p, long long k) {
  n = n % k;
  long long res = 1;
  while (p > 0) {
    if (p % 2 == 1) res = res * n % k;
    n = n * n % k;
    p = p / 2;
  }
  return res;
}
long long __pow(long long n, long long p) {
  long long res = 1;
  while (p > 0) {
    if (p % 2 == 1) res = res * n;
    n = n * n;
    p = p / 2;
  }
  return res;
}
long long str_mod_num(string b, long long c) {
  long long k = b.size();
  vector<long long> mod(k + 1);
  mod[0] = 1;
  for (long long i = 1; i < k + 1; i++) {
    mod[i] = 10 * mod[i - 1];
    mod[i] %= c;
  }
  long long rem = 0;
  for (long long i = k - 1; i > -1; i--) {
    long long num = b[i] - '0';
    num *= mod[k - 1 - i];
    num %= c;
    rem += num;
    rem %= c;
  }
  return rem;
}
long long str_pow_str_mod_num(string b, string n, long long c) {
  long long tr = n.size();
  long long rem = str_mod_num(b, c);
  long long time_pass = n[0] - '0';
  long long ans = modpow(rem, time_pass, c);
  for (long long i = 1; i < tr; i++) {
    time_pass = n[i] - '0';
    ans = modpow(ans, 10, c);
    ans *= modpow(rem, time_pass, c);
    ans %= c;
  }
  return ans;
}
bool isPrime(long long a) {
  for (long long i = 2; i * i <= a; ++i)
    if (a % i == 0) return false;
  return true;
}
bool useflushdivisible(long long a) {
  cout << a << endl;
  fflush(stdout);
  char sl[10];
  scanf("%s", sl);
  return sl[0] == 'y' || sl[0] == 'Y';
}
long long phi(long long n) {
  long long result = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) n = n / i;
      result = result - result / i;
    }
  }
  if (n > 1) result = result - result / n;
  return result;
}
bool cmp(pair<long long, long long> x, pair<long long, long long> y) {
  return x.first < y.first;
}
vector<long long> getfactors(long long n) {
  vector<long long> factors;
  for (long long i = 1; i < sqrt(n) + 1; i++) {
    if (n % i == 0) {
      factors.push_back(i);
      if (i != (n / i)) factors.push_back(n / i);
    }
  }
  return factors;
}
long long Binary_Search(vector<long long>& a, long long low, long long high,
                        long long key) {
  if (high < low) return a[low - 1];
  int mid = (high + low) / 2;
  if (key == a[mid])
    return a[mid];
  else if (key < a[mid])
    return Binary_Search(a, low, mid - 1, key);
  return Binary_Search(a, mid + 1, high, key);
}
double area(long long x1, long long y1, long long x2, long long y2,
            long long x3, long long y3) {
  return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0);
}
bool isInside(long long x1, long long y1, long long x2, long long y2,
              long long x3, long long y3, int x, int y) {
  double A = area(x1, y1, x2, y2, x3, y3);
  double A1 = area(x, y, x2, y2, x3, y3);
  double A2 = area(x1, y1, x, y, x3, y3);
  double A3 = area(x1, y1, x2, y2, x, y);
  return (A == A1 + A2 + A3);
}
long long log3(long long n) {
  long long j = 0;
  while (n > 0) {
    n /= 3;
    j++;
  }
  return j - 1;
}
bool isleap(long long n) {
  if (n % 4)
    return 0;
  else if (n % 100)
    return 1;
  else if (n % 400)
    return 0;
  else
    return 1;
}
int main() {
  FAST();
  srand(time(0));
  int test = 1;
  for (int tt = 1; tt <= test; tt++) {
    solve();
  }
  return 0;
}
void solve() {
  long long n, k;
  cin >> n >> k;
  long long ans = modpow(n - k, n - k, (long long)1e9 + 7);
  ans *= modpow(k, k - 1, (long long)1e9 + 7);
  ans %= (long long)1e9 + 7;
  cout << ans << endl;
}
long long Rselect(vector<long long> v, long long i, long long l, long long r) {
  if (l == r) return v[l];
  long long pivot = partition(v, l, r);
  if (pivot == i)
    return v[pivot - 1];
  else if (pivot < i) {
    return Rselect(v, i, pivot, r);
  } else {
    return Rselect(v, i, l, pivot - 2);
  }
}
long long partition(vector<long long> v, long long l, long long r) {
  long long pivot_index = rand() % (r - l + 1) + l;
  swap(v[pivot_index], v[l]);
  long long i = l + 1, j = l + 1;
  while (j <= r) {
    if (v[j] < v[l]) {
      swap(v[j], v[i]);
      i++;
    }
    j++;
  }
  swap(v[l], v[i - 1]);
  return i;
}

```