Problem: There are well-known formulas: <image>, <image>, <image>. Also mathematicians found similar formulas for higher degrees.

Find the value of the sum <image> modulo 109 + 7 (so you should find the remainder after dividing the answer by the value 109 + 7).

Input

The only line contains two integers n, k (1 ≤ n ≤ 109, 0 ≤ k ≤ 106).

Output

Print the only integer a — the remainder after dividing the value of the sum by the value 109 + 7.

Examples

Input

4 1


Output

10


Input

4 2


Output

30


Input

4 3


Output

100


Input

4 0


Output

4

Solution (in JAVA):

Solution:
import java.util.*;
import java.math.*;
import java.io.*;

public class CF662F {
	long inv(long x) { return exp(x, MOD - 2, MOD); }
	long exp(long b, long e, long m) {
		if(e == 0) return 1;
		long r = exp(b, e / 2, m);
		if((e & 1) == 0) return r * r % MOD;
		return r * r % m * b % m;
	}
	long interpolate(long[] ys, long x) {
		int n = ys.length;
		long[] ifa = new long[n], b = new long[n];
		long f = 1, y = 0, a = 1;
		for(int i = 1 ; i < n ; i++)
			f = f * i % MOD;
		ifa[n - 1] = inv(f);
		for(int i = n - 1 ; i >= 1 ; i--)
			ifa[i - 1] = ifa[i] * i % MOD;
		b[n - 1] = 1;
		for(int i = n - 1 ; i >= 1 ; i--)
			b[i - 1] = b[i] * (x - i) % MOD;
		for(int i = 0 ; i < n ; i++) {
			long t = (a * b[i] % MOD) * ys[i] % MOD;
			t = (t * ifa[i] % MOD) * ifa[n - 1 - i] % MOD;
			y += ((n - i) & 1) == 0 ? -t : t;
			a = a * (x - i) % MOD;
		}
		return ((y % MOD) + MOD) % MOD;
	}
	final int MOD = (int) 1e9 + 7;
	public CF662F() {
		FS scan = new FS();
		int n = scan.nextInt(), k = scan.nextInt();
		long[] ys = new long[1111111];
		long sum = 0;
		for(int i = 1 ; i < 1111111 ; i++) {
			sum += exp(i, k, MOD);
			sum %= MOD;
			ys[i] = sum;
		}
		System.out.println(interpolate(ys, n));
	}
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while (!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch (Exception e) { e.printStackTrace(); }
			}
			return st.nextToken();
		}
		public int nextInt() { return Integer.parseInt(next()); }
	}
	public static void main(String[] args) { new CF662F(); }
}