public int numberOfWays(int[]data, int sum){
    int n = data.length;
    int result = 0;
    for(int z = 0; z < (1 << n); z++){
        int total = 0;
        for(int i = 0; i < n; i++){
            if(((1 << i) & z) != 0){
                total += data[i];
            }else{
                total -= data[i];
            }
        }
        result += total == sum ? 1 : 0;
    }
    return result;
}

int[][][]dp;
public int numberOfWays(int []data, int sum){
    int max = 1000;
    dp = new int[2][data.length][max + 1];
    for(int[][]a : dp){
        for(int[]b : a){
            Arrays.fill(b, -1);
        }
    }
    return cal(0, 0, 0, sum, data);

}

public int cal(int index, int negative, int currentSum, int sum, int[]data){
    int current = negative == 1 ? -currentSum : currentSum;
    if(index == data.length){
        return current== sum ? 1 : 0;
    }
    if(dp[negative][index][currentSum] != -1){
        return dp[negative][index][currentSum];
    }
    int add = current + data[index];
    int sub = current - data[index];
    int result = cal(index + 1, add < 0 ? 1 : 0, abs(add), sum, data);
    result += cal(index + 1, sub < 0 ? 1 : 0, abs(sub), sum, data);
    return dp[negative][index][currentSum] = result;
}

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll expt(ll a, ll b, ll m) {
    ll ans = 1;
    for (; b; b >>= 1) {
        if (b & 1)
            ans = ans * a % m;
        a = a * a % m;
    }
    return ans;
}

int main() {
    string a, b; int n;
    cin >> a >> b >> n;
    ll as = 0;
    for (char c : a) {
        as = (as * 10 + (c - '0')) % n;
    }
    ll ans = expt(as, b[0] - '0', n);
    for (int i = 1; i < b.size(); ++i) {
        ans = expt(ans, 10, n) * expt(as, b[i] - '0', n) % n;
    }
    cout << ans;
    return 0;
}

class Solution {
public:
    #define ll long long
    const ll MOD = 1e9 + 9;
    static const int MAXN = 2003;
    const int p = 31;
    ll power[MAXN], hashT[MAXN], rhashT[MAXN];
   
    string ss = " #";
    string ans;
   
    void precompute() {
        power[0] = 1;
        hashT[0] = rhashT[ss.size()] = 0;
   
        for (int i = 1; i < ss.size(); ++i)
            power[i] = power[i - 1] * p % MOD;
   
        for (int i = 1; i < ss.size(); ++i)
            hashT[i] = (hashT[i - 1] * p + ss[i] - '#' + 1) % MOD;
   
        for (int i = ss.size() - 1; i >= 1; --i)
            rhashT[i] = (rhashT[i + 1] * p + ss[i] - '#' + 1) % MOD;
    }
   
    bool check(int len) {
        for (int i = 1 + len; i <= ss.size() - len - 1; ++i) {
            ll h = (hashT[i] - hashT[i - len - 1] * power[len + 1] + MOD * MOD) % MOD;
            ll rh = (rhashT[i] - rhashT[i + len + 1] * power[len + 1] + MOD * MOD) % MOD;
            if (h == rh) {
                ans = ss.substr(i - len, 2 * len + 1);
                return true;
            }
        }
   
        return false;
    }
   
    string longestPalindrome(string s) {
        ans = s[0];
        for (auto& x : s) ss = ss + x + "#";
        int l = 1, r = s.size();
        precompute();
   
        while (l < r) {
            int m = (l + r + 1) / 2;
   
            if (check(m)) l = m;
            else r = m - 1;
        }
   
        ans.erase(remove(ans.begin(), ans.end(), '#'), ans.end());
        return ans;
    }
};

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        vector<vector<int>> waterMap(heightMap.size(), vector<int>(heightMap[0].size(), 0));
        for (int i = 1; i < heightMap.size() - 1; i++) {
            for (int j = 1; j < heightMap[0].size() - 1; j++) {
                array<int, 3> neighbours = {heightMap[i][j-1] + waterMap[i][j-1],
                                            heightMap[i][j],
                                            heightMap[i-1][j] + waterMap[i-1][j]};
                waterMap[i][j] = *max_element(neighbours.begin(), neighbours.end()) - heightMap[i][j];
            }   
        }
        bool run = true;
        while(run) {
            run = false;
            for (int i = 1; i < heightMap.size() - 1; i++) {
                for (int j = 1; j < heightMap[0].size() - 1; j++) {
                    array<int, 4> neighbourHeight = {heightMap[i][j+1] + waterMap[i][j+1],
                                                   heightMap[i][j-1] + waterMap[i][j-1],
                                                   heightMap[i+1][j] + waterMap[i+1][j],
                                                   heightMap[i-1][j] + waterMap[i-1][j]};
                    int minHeight = *min_element(neighbourHeight.begin(),
                                                 neighbourHeight.end());
                    int newWater = minHeight > heightMap[i][j] ?
                        minHeight - heightMap[i][j] : 0;
                    run = newWater != waterMap[i][j] ? true : run;
                    waterMap[i][j] = newWater;
                }   
            }
        }
        int result = 0;
        for (auto row : waterMap) {
            for (auto cell : row) {
                result += cell;
            }
        }
        return result;
    }
};

struct cell{
    cell (int _x, int _y, int _val){
        x = _x;
        y = _y;
        val = _val;
    }
    int x;
    int y;
    int val;
};


bool operator < (const cell &o1, const cell &o2) {
        return o1.val > o2.val;
}

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.size() <= 2 || heightMap[0].size() <= 2) return 0;
        
        vector<vector<bool>> visited(heightMap.size(), vector<bool>(heightMap[0].size(), false));
        priority_queue<cell> minHeap;
        
        // add all cell in boundary into heap
        for (int j = 0; j < heightMap[0].size(); j++){
            minHeap.emplace(0,j,heightMap[0][j]);
            minHeap.emplace(heightMap.size() - 1,j,heightMap.back()[j]);
            visited[0][j] = true;
            visited[heightMap.size() - 1][j] = true;
        }
        for (int i = 1; i < heightMap.size() - 1; i++){
            minHeap.emplace(i,0,heightMap[i][0]);
            minHeap.emplace(i,heightMap[0].size() - 1,heightMap[i].back());
            visited[i][0] = true;
            visited[i][heightMap[0].size() - 1] = true;
        }
        
        
        array<pair<int, int>, 4> offsets = {make_pair(0,-1), make_pair(0,1),
                                            make_pair(-1,0), make_pair(1,0)};
        int curMax = -1;
        int result = 0;
        //bfs
        while (!minHeap.empty()) {
            auto top = minHeap.top();
            curMax = curMax > top.val ? curMax : top.val;
            minHeap.pop();
            for (auto off : offsets){
                int next_x = top.x + off.first;
                int next_y = top.y + off.second;
                if (next_x>=0 && next_x<heightMap.size()
                    && next_y>=0 && next_y<heightMap[0].size()
                    && !visited[next_x][next_y]) {
                    visited[next_x][next_y] = true;
                    if (heightMap[next_x][next_y] < curMax) {
                        result += curMax - heightMap[next_x][next_y];
                        minHeap.emplace(next_x, next_y, curMax);
                    } else{
                        minHeap.emplace(next_x, next_y, heightMap[next_x][next_y]);
                    }
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL && l2 == NULL)
            return l1;
       
        if(l1 == NULL)
            return l2;
       
        if(l2 == NULL)
            return l1;
                 
        ListNode *hd= NULL;
        ListNode *cr= NULL;
       
        int x;
        int y;
        while(l1 != NULL && l2 != NULL ){
            x = l1 ? l1->val:0; 
            y = l2 ? l2->val:0;           

            if (hd == NULL) {
                if (x <= y){               
                    cr = new ListNode(x);
                   
                    l1 = l1 ? l1->next:NULL;
                }
                else{
                    cr = new ListNode(y);
                    l2 = l2 ? l2->next:NULL;
                }
                hd = cr;
            }
            else{
                if (x <= y){               
                    cr->next = new ListNode(x);
                   
                    l1 = l1 ? l1->next:NULL;
                }
                else{
                    cr->next = new ListNode(y);
                    l2 = l2 ? l2->next:NULL;
                }
                cr = cr->next;
            }
        }
       
        if(l1 != NULL ){
            cr->next = l1;
        }
       
        if(l2 != NULL ){
            cr->next = l2;
        }

        return hd;       
    }
};