Cod sursa(job #2506905)

Utilizator victoreVictor Popa victore Data 8 decembrie 2019 23:20:23
Problema Dirichlet Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
//check check check
#include<iostream>
#include<vector>
#include<algorithm>
#include<fstream>
#include<queue>
#include<cstring>
#include<map>
#include<iomanip>
#include<set>

#define ll long long
#define pb(x) push_back(x)

using namespace std;

typedef pair<int,int> ii;

const int NMAX = 0;
const int MOD = 9999991;

ifstream fin("dirichlet.in");
ofstream fout("dirichlet.out");

ll pow2(ll num , ll e)
{
    if(e == 0)
        return 1;
    if(e&1)
    {
        ll k = pow2(num,e>>1);
        k = (k*k)%MOD;
        return (k*num)%MOD;
    }
    else
    {
        ll k = pow2(num,e>>1);
        return (k*k)%MOD;
    }
}


int main()
{
    ll a = 1,b = 1,N,i;
    fin>>N;

    for(i = 1 ; i <= N ; ++i)
    {
        a = (a * (N+i))%MOD;
        b = (b * i)%MOD;
    }
    fout<<(((a*pow2(b,MOD-2))%MOD)*pow2(N+1,MOD-2))%MOD;
}