Mai intai trebuie sa te autentifici.
Cod sursa(job #635697)
Utilizator | Data | 19 noiembrie 2011 14:16:58 | |
---|---|---|---|
Problema | Dirichlet | Scor | 100 |
Compilator | cpp | Status | done |
Runda | .com 2011 | Marime | 0.99 kb |
#include <stdio.h>
#define MOD 9999991
long long firstfact;
long long fact (int N)
{
long long sol = 1, i;
for (i = 2; i <= N; i ++)
{
sol = sol * i % MOD;
if (i == N / 2)
firstfact = sol;
}
return sol;
}
long long FastPow (long long A, long long B)
{
if (B == 0)
return 1;
long long now = FastPow (A, B >> 1);
if (B & 1)
return ((long long)now * now % MOD * A) % MOD;
else
return (long long)now * now % MOD;
}
long long invers (long long val)
{
return FastPow (val, MOD - 2);
}
int main ()
{
int N;
long long sol, fact1, inv1, inv2;
freopen ("dirichlet.in", "r", stdin);
freopen ("dirichlet.out", "w", stdout);
scanf ("%d", &N);
fact1 = fact (2 * N) % MOD;
inv1 = invers (firstfact) % MOD;
inv2 = invers (firstfact * (N + 1) % MOD) % MOD;
sol = (((fact1 * inv1) % MOD) * inv2) % MOD;
printf ("%lld", sol);
return 0;
}