You have a team of N people. For a particular task, you can pick any non-empty subset of people. The cost of having x people for the task is xk. 

Output the sum of costs over all non-empty subsets of people.

Input

Only line of input contains two integers N (1 ≤ N ≤ 109) representing total number of people and k (1 ≤ k ≤ 5000).

Output

Output the sum of costs for all non empty subsets modulo 109 + 7.

Examples

Input

1 1


Output

1


Input

3 2


Output

24

Note

In the first example, there is only one non-empty subset {1} with cost 11 = 1.

In the second example, there are seven non-empty subsets.

- {1} with cost 12 = 1

- {2} with cost 12 = 1

- {1, 2} with cost 22 = 4

- {3} with cost 12 = 1

- {1, 3} with cost 22 = 4

- {2, 3} with cost 22 = 4

- {1, 2, 3} with cost 32 = 9

The total cost is 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24.
#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> p) {
  out << '(' << p.first << ',' << p.second << ')';
  return out;
}
template <class T1, class T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  in >> p.first >> p.second;
  return in;
}
template <class T>
istream& operator>>(istream& in, vector<T>& v) {
  for (auto& x : v) in >> x;
  return in;
}
template <class T>
ostream& operator<<(ostream& out, vector<vector<T>>& v) {
  for (auto& x : v) out << x << '\n';
  return out;
}
template <class T>
ostream& operator<<(ostream& out, vector<T>& v) {
  for (auto x : v) out << x << ' ';
  return out;
}
long long gcd(long long a, long long b) {
  if (b > a) swap(a, b);
  return (b ? gcd(b, a % b) : a);
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using tiii = pair<pair<int, int>, int>;
using vi = vector<int>;
using vl = vector<long long>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
const int h = 1000000007;
ll p(ll x, ll y) {
  static const int mod = 1000000007;
  if (y == 0) return 1;
  ll z = p(x, y / 2);
  z *= z;
  z %= mod;
  return (y & 1 ? (z * x) % mod : z);
}
ll inv(ll x) {
  static const int mod = 1000000007;
  return p(x, h - 2);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cerr.setstate(ios::failbit);
  ll n, k;
  cin >> n >> k;
  vvl dp(k + 1, vl(k + 1));
  dp[0][0] = 1;
  for (int i = 0; i < k; i++)
    for (int j = 0; j < i + 1; j++) {
      dp[i + 1][j] += dp[i][j] * j;
      dp[i + 1][j] %= h;
      dp[i + 1][j + 1] += dp[i][j] * (n - j);
      dp[i + 1][j + 1] %= h;
    }
  ll ans = 0;
  for (int i = 0; i < k + 1; i++) ans += dp[k][i] * p(2, n - i), ans %= h;
  cout << ans;
}
