Se citesc trei numere naturale x, n și m. Afișați valoarea lui x^n modulo m, calculată folosind o funcție recursivă ce exploatează relația de ridicare la putere prin înjumătățire (numărul de apeluri trebuie să fie de ordinul log2(n)).

Definiți o funcție recursivă putere(x, n, m) care întoarce (x^n) mod m, folosind relația:

putere(x, 0, m) = 1 mod m
putere(x, n, m) = (putere(x, n/2, m))^2 mod m,                 dacă n este par
putere(x, n, m) = ((putere(x, n/2, m))^2 * x) mod m,           dacă n este impar

Atenție: NU calculați x^n direct și apoi modulo (numerele intermediare pot fi enorme). Reduceți modulo m după fiecare înmulțire.