{"raw_statement":[{"iden":"statement","content":"A permutation _p_ of size _n_ is an array such that every integer from 1 to _n_ occurs exactly once in this array.\n\nLet's call a permutation an _almost identity permutation_ iff there exist at least _n_ - _k_ indices _i_ (1 ≤ _i_ ≤ _n_) such that _p__i_ = _i_.\n\nYour task is to count the number of _almost identity_ permutations for given numbers _n_ and _k_."},{"iden":"input","content":"The first line contains two integers _n_ and _k_ (4 ≤ _n_ ≤ 1000, 1 ≤ _k_ ≤ 4)."},{"iden":"output","content":"Print the number of _almost identity_ permutations for given _n_ and _k_."},{"iden":"examples","content":"Input\n\n4 1\n\nOutput\n\n1\n\nInput\n\n4 2\n\nOutput\n\n7\n\nInput\n\n5 3\n\nOutput\n\n31\n\nInput\n\n5 4\n\nOutput\n\n76"}],"translated_statement":[{"iden":"statement","content":"一个大小为 $n$ 的排列 $p$ 是一个数组，其中从 $1$ 到 $n$ 的每个整数恰好出现一次。\n\n我们称一个排列为 _几乎恒等排列_，当且仅当至少有 $n - k$ 个下标 $i$（$1 ≤ i ≤ n$）满足 $p_i = i$。\n\n你的任务是计算给定数字 $n$ 和 $k$ 的 _几乎恒等排列_ 的数量。\n\n第一行包含两个整数 $n$ 和 $k$（$4 ≤ n ≤ 1000$，$1 ≤ k ≤ 4$）。\n\n请输出给定 $n$ 和 $k$ 的 _几乎恒等排列_ 的数量。\n\n"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $k$（$4 ≤ n ≤ 1000$，$1 ≤ k ≤ 4$）。"},{"iden":"output","content":"请输出给定 $n$ 和 $k$ 的 _几乎恒等排列_ 的数量。"},{"iden":"examples","content":"输入\n4 1\n输出\n1\n输入\n4 2\n输出\n7\n输入\n5 3\n输出\n31\n输入\n5 4\n输出\n76"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n, k \\in \\mathbb{N} $ with $ 4 \\leq n \\leq 1000 $, $ 1 \\leq k \\leq 4 $.\n\nLet $ S_n $ denote the symmetric group on $ n $ elements, i.e., the set of all permutations of $ \\{1, 2, \\dots, n\\} $.\n\nA permutation $ \\pi \\in S_n $ is an *almost identity permutation* if the number of fixed points satisfies:\n$$\n|\\{ i \\in \\{1, 2, \\dots, n\\} \\mid \\pi(i) = i \\}| \\geq n - k.\n$$\n\nWe are to compute:\n$$\n\\sum_{j = n - k}^{n} \\binom{n}{j} \\cdot D_{n - j}\n$$\nwhere $ D_m $ denotes the number of derangements of $ m $ elements (i.e., permutations of $ m $ elements with no fixed points), and $ D_0 = 1 $.\n\n(Note: $ \\binom{n}{j} $ counts the ways to choose $ j $ fixed points, and $ D_{n-j} $ counts the derangements of the remaining $ n-j $ elements.)","simple_statement":null,"has_page_source":false}