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 \(p_i = 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

题意

给出\(n\)的全排列，求有多少种排列，满足至少\(n-k\)个位置上的数和下标相同（下标从\(1\)开始）

思路

因为\(1\leq k\leq 4\)，所以可以将题意转换一下：在\(n\)的全排列中，找到\(k\)个数，数和下标的值全都不相等

我们可以从\(n\)个数中，随机选出\(k\)个数，让这\(k\)个数全都没有放在正确的位置上，选\(k\)个数，我们可以用组合数来求，然后用错排公式来求有多少个数没放在正确的位置上。

因为\(k\)只有四个值，直接计算错排公式的值即可

最后将\(1\)～\(k\)中的这些值加起来即可

代码

#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define ms(a,b) memset(a,b,sizeof(a))

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=1e6+10;

const int mod=1e9+7;

const int maxm=1e3+10;

using namespace std;

ll C(int n,int m)

{

    ll fenmu=1LL;

    ll fenzi=1LL;

    for(int i=1;i<=m;i++)

    {

        fenmu=1LL*fenmu*(n-i+1);

        fenzi=1LL*fenzi*i;

    }

    return fenmu/fenzi;

}

int main(int argc, char const *argv[])

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt", "r", stdin);

        freopen("out.txt", "w", stdout);

        srand((unsigned int)time(NULL));

    #endif

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n,k;

    cin>>n>>k;

    ll ans=0;

    if(k>=1)

        ans+=1;

    if(k>=2)

        ans+=(n*(n-1)/2);

    if(k>=3)

        ans+=2*C(n,3);

    if(k>=4)

        ans+=9*C(n,4);

    cout<<ans<<endl;

    #ifndef ONLINE_JUDGE

        cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;

    #endif

    return 0;

}

巴特西

Codeforces 888D： Almost Identity Permutations（错排公式，组合数）

Input

Output

Examples

题意

思路

代码

最新文章

热门文章