Cerința

Se dă n un număr natural nenul. Să se afle câte soluții are ecuația x1+x2+...+xn=0 în mulțimea {-1,0,1}.

Date de intrare

Fișierul de intrare necuatie.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire necuatie.out va conține pe prima linie numărul S, reprezentând numărul soluțiilor ecuației modulo 555557.

Restricții și precizări

• 1 ≤ n ≤ 2000

Exemplu

necuatie.in

3

necuatie.out

7

Explicație

Soluțiile ecuației x1+x2+x3=0 în mulțimea { -1 , 0 , 1 } sunt: (0,0,0) , (0,1,-1) , (0,-1,1) , (1,0,-1) , (-1,0,1) , (1,-1,0) , (-1,1,0).

#include <bits/stdc++.h>
using namespace std;
#define MOD 555557

ifstream cin("necuatie.in");
ofstream cout("necuatie.out");

int n , S = 1;

int Invers(int a)
{
    int r = 1 , n = MOD - 2;
    while(n > 0)
    {
        if(n % 2 == 1) r = 1LL * r * a % MOD;
        a = 1LL * a * a % MOD;
        n /= 2;
    }
    return r;
}

int combinari(int n , int k)
{
    int P = 1 , Q = 1;
    for(int i = 1 ; i <= k ; i++)
    {
        P = 1LL * P * (n - i + 1) % MOD;
        Q = 1LL * Q * i % MOD;
    }
    return 1LL * P * Invers(Q) % MOD;
}


int main()
{
    cin >> n;
    for(int i = 1 ; i <= n / 2; i++)
        S = (S + 1LL * combinari(n , i) * combinari(n - i , i) % MOD) % MOD;
    cout << S;
}