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.io.*;
import java.math.*;
import java.util.*;


public class Main {
	static final int MOD = 1000000007;
	
	public static int mul(int x, int y) {
		long ret = x;
		ret *= y;
		ret %= MOD;
		return (int) ret;
	}
	
	public static int power(int basic, int times) {
		int ret = 1;
		while(times > 0) {
			if((times & 1) == 1) ret = mul(ret, basic);
			basic = mul(basic, basic);
			times >>= 1;
		}
		return ret;
	}
	
	public static Integer[] extGcd(Integer a, Integer b) {
		Integer [] ret = new Integer[3];
		if(b == 0) {
			ret[0] = Integer.valueOf(a.intValue());
			ret[1] = Integer.valueOf(1);
			ret[2] = Integer.valueOf(0);
		} else {
			Integer [] tmp = extGcd(b, a % b);
			Integer g = tmp[0], ta = tmp[2], tb = tmp[1] - a / b * tmp[2];
			if(ta < 0) {
				Integer t = ta / (b / g);
				ta -= t * (b / g);
				tb += t * (a / g);
			}
			if(ta < 0) {
				ta += b / g;
				tb -= a / g;
			}
			ret[0] = g;
			ret[1] = ta;
			ret[2] = tb;
		}
		return ret;
	}
	
	public static int inv(int x) {
//		0-> gcd   1->ta    2->tb
//		Integer [] results = extGcd(x, MOD);
//		return results[1];
		return power(x, MOD - 2);
	}
	
	public static int solve(int n, int m) {
//		System.out.println(n + " " + m);
		
		int [] f = new int[m + 3];
		f[0] = 0;
		for(int i = 1; i <= m + 2; i++) {
			f[i] = f[i - 1] + power(i, m);
			if(f[i] >= MOD) f[i] -= MOD;
		}
//		System.out.println(power(Integer.valueOf(2), Integer.valueOf(100)));

//		for(Integer i = Integer.valueOf(1); i <= m + 2; i++)
//			System.out.print(f[i] + " ");
//		System.out.println("");
		
		if(n <= m + 2) return f[n];
		
		int [] lagrange = new int[m + 3];
		int [] fact = new int[m + 3];
		fact[0] = 1;
		for(int i = 1; i <= m + 2; i++)
			fact[i] = mul(fact[i - 1], i);
		for(int i = 1; i <= m + 2; i++) {
			lagrange[i] = f[i];
			lagrange[i] = mul(lagrange[i], inv(mul(fact[i - 1], fact[m + 2 - i])));
			if(((m + 2 - i) & 1) == 1)
				lagrange[i] = MOD - lagrange[i];
//			System.out.print(lagrange[i] + " ");
		}
//		System.out.println("");
		
		int fullDenominator = 1;
		for(int i = 1; i <= m + 2; i++)
			fullDenominator = mul(fullDenominator, n - i);
//		System.out.println(fullDenominator);
		
		Integer ret = Integer.valueOf(0);
		for(int i = 1; i <= m + 2; i++) {
			int denominator = mul(fullDenominator, inv(n - i));
//			System.out.print(denominator + " ");
			ret = ret + mul(denominator, lagrange[i]);
			if(ret >= MOD) ret -= MOD;
		}
		return ret;
	}
	
	public static void main(String[] args) throws IOException {
		
		Scanner reader = new Scanner(System.in);
		Integer n = new Integer(reader.nextInt());
		Integer k = new Integer(reader.nextInt());
		
		Integer ans = solve(n, k);
		
		System.out.println(ans);
		
		reader.close();
	}
}