D. Almost Identity Permutationstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputA 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.InputThe first line contains two integers n and k (4 ≤ n ≤ 1000, 1 ≤ k ≤ 4).OutputPrint the number of almost identity permutations for given n and k.ExamplesInput4 1Output1Input4 2Output7Input5 3Output31Input5 4Output76
Input4 1
Output1
['combinatorics', 'dp', 'math', '*1600']