Cod sursa(job #1356855)
Utilizator | Rotaru Gheorghe-Iulian iulianrotaru | Data | 23 februarie 2015 17:01:48 |
---|---|---|---|
Problema | Dirichlet | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.44 kb |
#include <fstream>
#define M 9999991
#define ll long long
using namespace std;
ifstream f("dirichlet.in"); ofstream g("dirichlet.out");
ll n;
ll invmod(ll a, ll b)
{ ll p=1;
while(b)
{ if(b&1) p=p*a%M;
a=a*a%M; b>>=1;
}
return p%M;
}
int main()
{ f>>n;
ll n2=2*n,a=1,b=1;
for(int i=n2;i>n+1;--i) a=a*i%M;
for(int i=1;i<=n;++i) b=b*i%M;
g<<a*invmod(b,M-2)%M<<'\n'; g.close(); return 0;
}