Modular exponentiation

Go to the Jutge statement of the problem

Write a program that, given n, k and m, computes n^k \pmod m.

Input: several cases, each one with three natural numbers n, k and m.
Assume 2 \leq n \leq 30000 and 2 \leq m \leq 30000.

Output: For every case, print n^k \pmod m.

Hint

What code from Problem 1.23 is a good starting point for this exercise? Be careful with the \pmod{m} and how big the numbers could get…

A possible C++ code to start the problem

//Modular exponentiation
#include<iostream>

using namespace std;

int power(int n, int k, int m){
    // do something here
    // be careful on how big the numbers could get
    // what approach, say from Problem 1.23 is a good one?
}

int main(){
    /*
    const int M_MAX = 30000;
    const int N_MAX = 30000;
    */
    int n, k, m;
    while(cin >> n >> k >> m){
        cout << power(n, k, m) << endl;
    }
}

A possible solution

//Modular exponentiation
#include<iostream>

using namespace std;

int power(int n, int k, int m){
    if (k == 0) return 1;
    int y = power(n, k/2, m);
    int res = (y*y) % m;
    if (k % 2 == 1) return (n*res) % m;// return (n*y*y) % m; is NOT OK!
    else return res;
}

int main(){
    /*
    const int M_MAX = 30000;
    const int N_MAX = 30000;
    */
    int n, k, m;
    while(cin >> n >> k >> m){
        cout << power(n, k, m) << endl;
    }
}