În parcul orașului există 4 rânduri de câte n copaci perfect aliniați. Rândurile sunt notate A, B, C și D, iar copacii de pe fiecare rând sunt numerotați de la 1 la n, ca în imaginea de mai jos:

O veveriță jucăușă sare prin copaci astfel:

pornește dintr-un copac numerotat cu 1;
la fiecare pas sare dintr-un copac numerotat cu i într-un copac numerotat cu i+1. Dacă se află într-un copac de pe rândul A, va sări în copacul de pe rândul B, dacă se află într-un copac de pe rândul D, va sări în copacul de pe rândul C, dacă se află în copacul de pe rândul B, va sări în copacul de pe rândul A sau în copacul de pe rândul C, iar dacă se află în copacul de pe rândul C, va sări în copacul de pe rândul B sau în copacul de pe rândul D;
se oprește într-unul dintre copacii numerotați cu n.

Cerința

<syntaxhighlight lang="python3"> MOD = 666013 #definim constanta pentru operatia modulo

fin = open("veverita4.in", "r") #deschidem fisierele input si output fout = open("veverita4.out", "w")

n = int(fin.readline()) #citim valoarea lui "n" din fisierul input

definim functie pentru inmultirea matricei

def mat_multiply(a, b)

   ans = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
   for i in range(4):
       for j in range(4):
           for k in range(4):
               ans[i][j] += a[i][k] * b[k][j]
           if n > 1000:#aplicam operatia modulo daca n>1000
               ans[i][j] %= MOD
   return ans                      # ridicam matricea la puterea n-1

definim matricea initiala "mat"

mat = [[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]]

initializam rezultatul matricel "ansmat" ca matrice de identitate

ansmat = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]

efectuam exponentierea matricei folosind metoda exponentierei binare

exp = n - 1 while exp:

   if exp % 2 == 1:
       ansmat = mat_multiply(ansmat, mat)
   mat = mat_multiply(mat, mat)
   exp = int(exp / 2)
   #calculam rezultatul final apeland elementele din "ansmat"

ans = 0 for i in range(4):

   for j in range(4):
       ans += ansmat[i][j]

aplicam operatia modulo daca n>1000

if n > 1000:

   ans %= MOD

scriem rezultatul final in fisierul output si inchidem fisierul

fout.write(str(ans)) fin.close() fout.close() </syntaxhighlight>Aflați numărul M de modalități în care se poate deplasa veverița, respectând regulile de mai sus. Dacă n este mai mic sau egal cu 1000, atunci veți afișa chiar numărul M, iar dacă n este mai mare decât 1000, veți afișa restul împărțirii lui M la 666013.

Date de intrare

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

Date de ieșire

Fișierul de ieșire veverita4.out va conține pe prima linie valoarea cerută.

Restricții și precizări

1 ≤ n ≤ 109
pentru 60% din teste, n ≤ 1000;
pentru alte 40% din teste, n ≤ 109;

Exemplu

veverita4.in

veverita4.out