Cod sursa(job #920309)

Utilizator razvan.popaPopa Razvan razvan.popa Data 20 martie 2013 10:31:29
Problema Invers modular Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<cstdio>
#define FOR(i,a,b)\
   for(int i=a; i<=b; ++i)
#define infile "functii.in"
#define outfile "functii.out"
#define MOD 30103
#define nMax 10005
using namespace std;

int fact[nMax];

int N, S, Sol;

void read(){
    freopen(infile, "r", stdin);

    scanf("%d %d", &N, &S);

    fclose(stdin);
}

int lgput(int N, int P){
    if(!P)
       return 1;
    int sqr = lgput(N, P >> 1);
    sqr = (sqr * sqr) % MOD;

    if(P&1)
       sqr = (sqr * N) % MOD;

    return sqr;
}

void euclid_extins(int a, int b, int &x, int &y, int &d){
    if(!b)
        x = 1, y = 0, d = a;
    else{
        int x0, y0;
        euclid_extins(b, a%b, x0, y0, d);
        x = y0;
        y = x0 - (a/b) * y0;
    }
}

int invMod(int A){
    int X, Y, D;
    euclid_extins(A, MOD, X, Y, D);

    if(X <= 0)
       X = MOD + X % MOD;

    return X;
}

void solve(){
    fact[0] = 1;
    FOR(i,1,N)
       fact[i] = (fact[i-1] * i) % MOD;

    Sol = (1LL * (lgput(2, S) - 2) * ((1LL * fact[N] * invMod(fact[N-S]) * invMod(fact[S])) % MOD)) % MOD;
}

void print(){
    freopen(outfile, "w", stdout);

    printf("%d\n", Sol);

    fclose(stdout);
}

int main(){
    read();
    solve();
    print();

    return 0;
}