#include <iostream>
using namespace std;

int convert(int deci)
{
  int bin = 0;
  int rem, i = 1;

  while (deci!=0)
  {
    rem = deci % 2;
    deci /= 2;
    bin += rem * i;
    i *= 10;
  }

  return bin;
}

int main()
{
    int n, b, m, bin_b, a;
    int power, i, x = 1;

    cout<< "Enter value of b: ";
    cin>> b;

    cout<< "Enter value of n: ";
    cin>> n;

    cout<< "Enter value of m: ";
    cin>> m;

    bin_b = convert(n);
    power = b % m;

    for(i=0; bin_b!=0; i++)
    {
        a = bin_b % 10;
        if(a == 1)
            x = (x * power) % m;
        power = (power * power) % m;
        bin_b /= 10;
    }

    cout << "\n("<< b << "^" << n <<") mod " << m <<" = " << x <<endl;

    return 0;
}