D. Almost Identity Permutations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation p of size n is an array such that every integer from 1 to n occurs exactly once in this array.

Let's call a permutation an almost identity permutation iff there exist at least n - k indices i (1 ≤ i ≤ n) such that pi = i.

Your task is to count the number of almost identity permutations for given numbers n and k.

Input

The first line contains two integers n and k (4 ≤ n ≤ 1000, 1 ≤ k ≤ 4).

Output

Print the number of almost identity permutations for given n and k.

Examples
Input
4 1
Output
1
Input
4 2
Output
7
Input
5 3
Output
31
Input
5 4
Output
76