1160 - Necuatie

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).

Încărcare soluție

Lipește codul aici

MOD = 555557
n = int(input())
S = 1

def Invers(a):
    r = 1
    n = MOD - 2
    while n > 0:
        if n % 2 == 1:
            r = (r * a) % MOD
        a = (a * a) % MOD
        n //= 2
    return r

def combinari(n, k):
    P = 1
    Q = 1
    for i in range(1, k+1):
        P = (P * (n - i + 1)) % MOD
        Q = (Q * i) % MOD
    return (P * Invers(Q)) % MOD

for i in range(1, n // 2 + 1):
    S = (S + (combinari(n, i) * combinari(n - i, i)) % MOD) % MOD

print(S)