Submission #1437679

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i,a,b) for(ll i=(a);i<(b);i++)
#define all(a)  (a).begin(),(a).end()
#define pb emplace_back
#define INF (1LL<<59)

const ll MOD = 1777777777LL;

//verified KUPC2014-D,ABC034-C,ARC023-C
//O(r log MOD)
ll power(ll a,ll b){
    ll ret=1;
    if(b>0){
        ret = power(a,b/2);
        if(b%2==0)ret = (ret*ret)%MOD;
        else ret = (((ret*ret)%MOD)*a)%MOD;
    }
    return ret;
}

ll inv(int n){ return power(n,MOD-2); }

ll C(int n,int r){
    r = min(r,n-r);
    ll ret=1;
    for(int i=n;i>n-r;i--) (ret*=i%MOD)%=MOD;
    for(int i=r;i>=1;i--) (ret*=inv(i))%=MOD;
    return ret;
}



signed main(){
    int fact[777778]={1};
    for(int i=1;i<777778;i++){
        fact[i] = (fact[i-1]*i)%MOD;
    }
    int n,k;
    cin>>n>>k;
    
    
    ll ans = 0;
    
    for(int i=0;i<=k;i++){
        if(i%2==0) ans += (fact[k] * inv(fact[i]))%MOD;
        if(i%2==1) ans += MOD - (fact[k] * inv(fact[i]))%MOD;
        ans%=MOD;
    }
    cout<<(C(n,k) * ans)%MOD<<endl;
}

Submission Info

Judge Result