#include <iostream>
using namespace std;

long long cal(long long a, long long b, long long c) {
	if (b == 1) return a%c;
	long long ans = cal(a, b / 2, c);
	if (b % 2) return ((ans * ans) % c * a)%c;
	return (ans*ans) % c;
}

int main() {
	long long a, b, c; cin >> a >> b >> c;

	cout << cal(a,b,c) << endl;
}

#include <iostream>
using namespace std;
#include <algorithm>
long long arr[100001];


long long cal(int i, int j) {
	if (i == j) return arr[i] * arr[i];
	if (i + 1 == j) return (arr[i] + arr[j]) * min(arr[i], arr[j]);
	int mid = (i + j) / 2;
	long long result = max(cal(i, mid), cal(mid, j));

	int l = mid, r = mid + 1;
	long long sum = arr[l] + arr[r];
	long long mul = min(arr[l], arr[r]);
	result = max(result, sum * mul);
	while (i < l || r < j) {
		if (r<j && (l==i || arr[l - 1] < arr[r + 1])) {
			sum += arr[++r];
			mul = min(mul, arr[r]);
		}
		else if(i<l &&( r==j || arr[l-1]> arr[r+1])) {
			sum += arr[--l];
			mul = min(mul, arr[l]);
		}
		result = max(result, sum * mul);
	}

	return result;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	cout << cal(0, n-1);
}

#include <iostream>
using namespace std;
#include <algorithm>
int arr[100001];


int cal(int i, int j) {
	if (i == j) return 0;
	if (i + 1 == j) return arr[i];

	int mid = (i + j) / 2;
	int result = max(cal(i, mid), cal(mid, j));

	int l = mid, r = mid;
	int w = 1, h = arr[mid];

	while (r-l+1 < j-i) {
		int p = l > i ? min(h, arr[l - 1]) : -1;
		int q = r < j - 1 ? min(h, arr[r + 1]) : -1;
		if (p >= q) { h = p; l--; }
		else { h = q; r++; }
		result = max(result, ++w * h);
	}

	return result;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	cout << cal(0, n) << endl;
}

#include <iostream>
using namespace std;
#include <algorithm>

int arr[2187][2187];
int result[3];

void cal(int x, int y, int div) {
	int num = arr[y][x];

	if (div == 1) {
		result[num + 1]++;
		return;
	}

	bool same = true;
	for (int i = y; i < y + div; i++) {
		for (int j = x; j < x + div; j++) {
			if (num != arr[i][j]) same = false;
		}
	}

	if(same) result[num + 1] ++; //-1 은 0, 0은 1, 1은 2
	else {
		div /= 3;
		cal(x, y, div);
		cal(x + div, y, div);
		cal(x + div*2, y, div);

		cal(x, y + div, div);
		cal(x + div, y + div, div);
		cal(x + div * 2, y + div, div);

		cal(x, y + div * 2, div);
		cal(x + div, y + div * 2, div);
		cal(x + div * 2, y + div * 2, div);
	}

	return;
}

int main() {
	int n; cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];

	cal(0, 0, n);
	for (int i = 0; i < 3; i++)
		cout << result[i] << endl;
}

#include <iostream>
using namespace std;
#include <algorithm>

int arr[64][64];

void cal(int x, int y, int div) {
	int num = arr[y][x];

	if (div == 1) {
		cout << num;
		return;
	}

	bool same = true;
	for (int i = y; i < y + div; i++) {
		for (int j = x; j < x + div; j++) {
			if (num != arr[i][j]) {
				same = false; break;
			}
		}
	}

	if(same) cout << num;
	else {
		cout << "(";

		div /= 2;
		cal(x, y, div);
		cal(x + div, y, div);

		cal(x, y + div, div);
		cal(x+div, y + div, div);
		cout << ")";

	}

	return;
}

int main() {
	int n; cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%1d", &arr[i][j]);

	cal(0, 0, n);
}

#include <iostream>
using namespace std;
#include <algorithm>

int r, c; int ans;

bool cal(int x, int y, int div) {
	if (x == c && y == r) return true;

	bool find = false;
	if (x <= c && c < x + div && y <= r && r < y + div) {
		div /= 2;
		if (!find) { find = cal(x, y, div);}
		if (!find) { find = cal(x+div, y, div); ans += div * div; }
		if (!find) { find = cal(x, y+div, div); ans += div * div; }
		if (!find) { find = cal(x+div, y+div, div); ans += div * div; }

		return true;
	}

	return false;
}

int main() {
	int n; cin >> n >> r>> c;

	cal(0, 0, 1<<n);

	cout << ans;
}

#include <iostream>
using namespace std;
#include <algorithm>

char arr[2187][2187];
int n;

void cal(int x, int y, int div, char c){
	if (div == 1) {
		arr[y][x] = c;
		return;
	}
	div /= 3;
	cal(x, y, div,c);
	cal(x + div, y, div, c);
	cal(x + div * 2, y, div, c);

	cal(x, y+div, div, c);
	cal(x + div, y + div, div,' ');
	cal(x + div * 2, y + div, div, c);

	cal(x, y+div*2, div, c);
	cal(x + div, y + div * 2, div, c);
	cal(x + div * 2, y + div * 2, div, c);
	return;
}

int main() {
	cin >> n;

	cal(0, 0, n, '*');

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cout << arr[i][j];
		cout << endl;
	}
}

#include <iostream>
using namespace std;
#include <algorithm>
#include <queue>

#define EMPTY 0
#define STONE 1
#define CRYSTAL 2

int n;
int arr[20][20];

int cut(int xs, int xe, int ys, int ye) {
	int ans = 0;
	//현재 조각 판단
	int havec = 0;
	int haves = 0;
	queue<pair<int, int>> st;
	for (int i = ys; i < ye; i++)
		for (int j = xs; j < xe; j++) {
			if (arr[i][j] == CRYSTAL) havec++;
			if (arr[i][j] == STONE) {
				haves++;
				st.push(make_pair(i,j));
			}
		}
	if (!havec) return 0;
	if (havec - haves != 1) return 0; 


	//기저사례
	if (!haves && havec == 1) {
		return 1; 
	}

	//다음 조각 나누기
	while (st.size()) {
		int h = st.front().first;
		int v = st.front().second;
		st.pop();

		bool can = true;
		for (int j = xs; j < xe; j++)
			if (arr[h][j] == CRYSTAL) {
				can = false; break;
			}
		if (can) {
			int a= cut(xs, xe, ys, h);
			int b= cut(xs, xe, h + 1, ye);
			ans += a * b;
		}

		can = true;
		for (int i = ys; i < ye; i++)
			if (arr[i][v] == CRYSTAL) {
				can = false; break;
			}
		if (can) {
			int a = cut(xs, v, ys, ye);
			int b = cut(v+1, xe, ys, ye);
			ans += a * b;
		}
	}

	return ans;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];
		
	
	int ans = cut(0, n, 0, n);

	if (ans) cout << ans << endl;
	else cout << -1 << endl;
}