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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.StringTokenizer;

// Educational Codeforces Round 7
// The Sum of the k-th Powers
public class Problem_622_F {
    public static final int MOD = 1000000007;

    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        PrintWriter out = new PrintWriter(outputStream);
        Problem_622_F solver = new Problem_622_F();
        solver.solve(1, new InputStreamReader(inputStream), out);
        out.close();
    }
    
    int xx;
    int yy;
    
    int gcd(int a, int b)
    {
      if (a == 0) {
        xx = 0;
        yy = 1;
        return b;
      }
      int x, y, g = gcd(b % a, a);

      x = yy - b / a * xx;
      y = xx;
      
      xx = x;
      yy = y;

      return g;
    }
    
    int inv(int a)
    {
      gcd(a, MOD);
      return normal(xx);
    }
    
    int add(int a, int b)
    {
      return (a + b) % MOD;
    }
    
    int mul(int a, int b)
    {
      return (int)((a * 1L * b) % MOD);
    }
    
    int _div(int a, int b)
    {
      return mul(a, inv(b));
    }
    
    int normal(int a)
    {
      a = a % MOD;
      if(a < 0) a += MOD;
      return a;
    }
    
    int binPow(int a, int b)
    {
      int res = 1;
      
      while(b > 0) {
        if((b & 1) != 0) res = mul(res, a);
        a = mul(a, a);
        b >>= 1;
      }
      return res;
    }

    int calc(ArrayList<Integer> y, int x)
    {
      int res = 0;
      int k = 1;
      for(int j = 1; j < y.size(); j++) {
        k = mul(k, normal(x - j));
        k = _div(k, normal(0 - j));
      }
      for(int i = 0; i < y.size(); i++) {
        res = add(res, mul(y.get(i), k));
        if(i + 1 >= y.size()) break;
        k = mul(k, _div(normal(x - i), normal(x - (i + 1))));
        k = mul(k, _div(normal(i - (y.size() - 1)), normal(i + 1)));
      }
      return res;
    }
    
    public void solve(int test, Reader input, PrintWriter out)
    {
        MyScanner in = new MyScanner(input);
        
        int n = in.nextInt();
        int k = in.nextInt();
        
        ArrayList<Integer> y = new ArrayList<>();
        
        int sum = 0;
        y.add(sum);
        for(int i = 0; i < k + 1; i++) {
          sum = add(sum, binPow(i + 1, k));
          y.add(sum);
        }
        int res = 0;
        if(n < y.size()) res = y.get(n);
        else res = calc(y, n);
        out.println(res);
    }

    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner(Reader reader) {
            br = new BufferedReader(reader);
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        
        int[] nextIntArray(int n)
        {
            int[] r = new int[n];
            for(int i = 0; i < n; i++)
                r[i] = nextInt();
            return r;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
    //--------------------------------------------------------

}