{"raw_statement":[{"iden":"statement","content":"Polycarp has set of integers 1, ..., N and parameters M и K. Polycarp is interested in number of permutations {ai} from numbers 1, ..., N, so that every permutation have exactly M inversions and K numbers are in their own place. Inversion is the pair of numbers i, j, so that ai > aj и i < j. Number i is postioned in it's own place if ai = i.\n\nSingle line contains three integers N, M, K. 1 ≤ N ≤ 14, , 0 ≤ K ≤ N.\n\nOne integer — number or permutations.\n\n"},{"iden":"input","content":"Single line contains three integers N, M, K. 1 ≤ N ≤ 14, , 0 ≤ K ≤ N."},{"iden":"output","content":"One integer — number or permutations."},{"iden":"examples","content":"Input4 0 4Output1Input12 7 3Output3000Input12 25 0Output3612516Input12 66 0Output1"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, M, K \\in \\mathbb{Z} $ with $ 1 \\leq N \\leq 14 $, $ 0 \\leq K \\leq N $.  \nLet $ S_N $ be the symmetric group on $ \\{1, 2, \\dots, N\\} $, i.e., the set of all permutations of $ [N] $.  \nFor a permutation $ \\pi \\in S_N $:  \n- An **inversion** is a pair $ (i, j) $ with $ i < j $ and $ \\pi(i) > \\pi(j) $.  \n- A **fixed point** is an index $ i $ such that $ \\pi(i) = i $.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 14 $  \n2. $ 0 \\leq K \\leq N $  \n3. $ M \\geq 0 $  \n\n**Objective**  \nCompute the number of permutations $ \\pi \\in S_N $ such that:  \n- The number of fixed points is exactly $ K $,  \n- The number of inversions is exactly $ M $.  \n\nThat is, compute:  \n$$\n\\left| \\left\\{ \\pi \\in S_N \\,\\middle|\\, \\#\\{i \\in [N] : \\pi(i) = i\\} = K \\text{ and } \\#\\{(i,j) : i < j, \\pi(i) > \\pi(j)\\} = M \\right\\} \\right|\n$$","simple_statement":"Given N, M, K, count the number of permutations of [1, ..., N] with exactly M inversions and exactly K fixed points (where a[i] = i).","has_page_source":false}