#include <iostream>
#define SumOfDigits(x, y, z) x + y + z - 3 * '0'
#define ProductOfDigits(x, y) (x[0] - '0') * (y[0] - '0')
using namespace std;
void addFrontZeros(string &x, int numberOfZeros){
for(int i = 0; i < numberOfZeros; i++){
x = '0' + x;
}
}
void addBackSideZeros(string &x, int numberOfZeros){
for(int i = 0; i < numberOfZeros; i++){
x = x + '0';
}
}
void deleteFrontZeros(string &x){
while(x[0] == '0'){
x.erase(0, 1);
}
}
int equalizeLength(string &x, string &y){
int difference = x.size() - y.size();
if(difference > 0){
addFrontZeros(y, difference);
}
else{
addFrontZeros(x, -difference);
}
return x.size();
}
string add2Numbers(string x, string y){
string result = "0";
int length = equalizeLength(x, y);
int sum;
addFrontZeros(result, length);
for(int i = length - 1; i >= 0; i--){
sum = SumOfDigits(x[i], y[i], result[i + 1]);
result[i + 1] = '0' + sum % 10;
result[i] = '0' + sum / 10;
}
deleteFrontZeros(result);
return result;
}
string add3Numbers(string x, string y, string z){
return add2Numbers(add2Numbers(x, y), z);
}
// we know that x is bigger than y
string subtract2Numbers(string x, string y){
string result = "0";
int length = equalizeLength(x, y);
int sum;
addFrontZeros(result, length);
for(int i = length - 1; i >= 0; i--){
sum = x[i] - y[i];
if(sum < 0){
x[i - 1] -= 1;
sum += 10;
}
result[i + 1] += sum;
}
deleteFrontZeros(result);
return result;
}
string product2Numbers(string x, string y){
int length, sum, fh, sh;
string result , x1, x2, y1, y2, a, d, e;
if(x == "0" || y == "0") return "0";
length = equalizeLength(x, y);
if(length == 0) return "0";
if(length == 1){
sum = ProductOfDigits(x, y);
if(sum >= 10){
result += ('0' + sum / 10);
}
result += ('0' + sum % 10);
return result;
}
sh = length / 2;
fh = length - sh;
x1 = x.substr(0, fh);
x2 = x.substr(fh, sh);
y1 = y.substr(0, fh);
y2 = y.substr(fh, sh);
a = product2Numbers(x1, y1);
d = product2Numbers(x2, y2);
e = product2Numbers(add2Numbers(x1, x2), add2Numbers(y1, y2));
e = subtract2Numbers(e, add2Numbers(a, d));
addBackSideZeros(a, length - length % 2);
addBackSideZeros(e, length / 2);
return add3Numbers(d, a, e);
}
string decToBin(int n){
string x = "";
while(n > 0){
if(n % 2 == 1){
x = '1' + x;
}
else{
x = '0' + x;
}
n /= 2;
}
return x;
}
string exponentiation(string number, int exponent){
string exponentBINARY, solution="1";
exponentBINARY = decToBin(exponent);
if(number == "0"){
return "0";
}
for(int i = exponentBINARY.size() - 1; i >= 0; i--){
if(exponentBINARY[i] == '1'){
solution = product2Numbers(solution, number);
}
if(i != 0){
number = product2Numbers(number, number);
}
}
deleteFrontZeros(solution);
return solution;
}
int main(){
string x;
int y;
cin >> x >> y;
cout << exponentiation(x, y) << endl;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojZGVmaW5lIFN1bU9mRGlnaXRzKHgsIHksIHopIHggKyB5ICsgeiAtIDMgKiAnMCcKI2RlZmluZSBQcm9kdWN0T2ZEaWdpdHMoeCwgeSkgKHhbMF0gLSAnMCcpICogKHlbMF0gLSAnMCcpCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIGFkZEZyb250WmVyb3Moc3RyaW5nICZ4LCBpbnQgbnVtYmVyT2ZaZXJvcyl7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbnVtYmVyT2ZaZXJvczsgaSsrKXsKICAgICAgICB4ID0gJzAnICsgeDsKICAgIH0KfQoKdm9pZCBhZGRCYWNrU2lkZVplcm9zKHN0cmluZyAmeCwgaW50IG51bWJlck9mWmVyb3MpewogICAgZm9yKGludCBpID0gMDsgaSA8IG51bWJlck9mWmVyb3M7IGkrKyl7CiAgICAgICAgeCA9IHggKyAnMCc7CiAgICB9Cn0KCnZvaWQgZGVsZXRlRnJvbnRaZXJvcyhzdHJpbmcgJngpewogICAgd2hpbGUoeFswXSA9PSAnMCcpewogICAgICAgIHguZXJhc2UoMCwgMSk7CiAgICB9Cn0KCmludCBlcXVhbGl6ZUxlbmd0aChzdHJpbmcgJngsIHN0cmluZyAmeSl7CiAgICBpbnQgZGlmZmVyZW5jZSA9IHguc2l6ZSgpIC0geS5zaXplKCk7CgogICAgaWYoZGlmZmVyZW5jZSA+IDApewogICAgICAgIGFkZEZyb250WmVyb3MoeSwgZGlmZmVyZW5jZSk7CiAgICB9CiAgICBlbHNlewogICAgICAgIGFkZEZyb250WmVyb3MoeCwgLWRpZmZlcmVuY2UpOwogICAgfQoKICAgIHJldHVybiB4LnNpemUoKTsKfQoKc3RyaW5nIGFkZDJOdW1iZXJzKHN0cmluZyB4LCBzdHJpbmcgeSl7CiAgICBzdHJpbmcgcmVzdWx0ID0gIjAiOwogICAgaW50IGxlbmd0aCA9IGVxdWFsaXplTGVuZ3RoKHgsIHkpOwogICAgaW50IHN1bTsKCiAgICBhZGRGcm9udFplcm9zKHJlc3VsdCwgbGVuZ3RoKTsKCiAgICBmb3IoaW50IGkgPSBsZW5ndGggLSAxOyBpID49IDA7IGktLSl7CiAgICAgICAgc3VtID0gU3VtT2ZEaWdpdHMoeFtpXSwgeVtpXSwgcmVzdWx0W2kgKyAxXSk7CiAgICAgICAgcmVzdWx0W2kgKyAxXSA9ICcwJyArIHN1bSAlIDEwOwogICAgICAgIHJlc3VsdFtpXSA9ICcwJyArIHN1bSAvIDEwOwogICAgfQoKICAgIGRlbGV0ZUZyb250WmVyb3MocmVzdWx0KTsKCiAgICByZXR1cm4gcmVzdWx0Owp9CgpzdHJpbmcgYWRkM051bWJlcnMoc3RyaW5nIHgsIHN0cmluZyB5LCBzdHJpbmcgeil7CiAgICByZXR1cm4gYWRkMk51bWJlcnMoYWRkMk51bWJlcnMoeCwgeSksIHopOwp9CgovLyB3ZSBrbm93IHRoYXQgeCBpcyBiaWdnZXIgdGhhbiB5CnN0cmluZyBzdWJ0cmFjdDJOdW1iZXJzKHN0cmluZyB4LCBzdHJpbmcgeSl7CiAgICBzdHJpbmcgcmVzdWx0ID0gIjAiOwogICAgaW50IGxlbmd0aCA9IGVxdWFsaXplTGVuZ3RoKHgsIHkpOwogICAgaW50IHN1bTsKCiAgICBhZGRGcm9udFplcm9zKHJlc3VsdCwgbGVuZ3RoKTsKCiAgICBmb3IoaW50IGkgPSBsZW5ndGggLSAxOyBpID49IDA7IGktLSl7CiAgICAgICAgc3VtID0geFtpXSAtIHlbaV07CgogICAgICAgIGlmKHN1bSA8IDApewogICAgICAgICAgICB4W2kgLSAxXSAtPSAxOwogICAgICAgICAgICBzdW0gKz0gMTA7CiAgICAgICAgfQoKICAgICAgICByZXN1bHRbaSArIDFdICs9IHN1bTsKICAgIH0KCiAgICBkZWxldGVGcm9udFplcm9zKHJlc3VsdCk7CgogICAgcmV0dXJuIHJlc3VsdDsKfQoKc3RyaW5nIHByb2R1Y3QyTnVtYmVycyhzdHJpbmcgeCwgc3RyaW5nIHkpewogICAgaW50IGxlbmd0aCwgc3VtLCBmaCwgc2g7CiAgICBzdHJpbmcgcmVzdWx0ICwgeDEsIHgyLCB5MSwgeTIsIGEsIGQsIGU7CgogICAgaWYoeCA9PSAiMCIgfHwgeSA9PSAiMCIpIHJldHVybiAiMCI7CgogICAgbGVuZ3RoID0gZXF1YWxpemVMZW5ndGgoeCwgeSk7CgogICAgaWYobGVuZ3RoID09IDApIHJldHVybiAiMCI7CiAgICBpZihsZW5ndGggPT0gMSl7CiAgICAgICAgc3VtID0gUHJvZHVjdE9mRGlnaXRzKHgsIHkpOwogICAgICAgIGlmKHN1bSA+PSAxMCl7CiAgICAgICAgICAgIHJlc3VsdCArPSAoJzAnICsgc3VtIC8gMTApOwogICAgICAgIH0KICAgICAgICByZXN1bHQgKz0gKCcwJyArIHN1bSAlIDEwKTsKCiAgICAgICAgcmV0dXJuIHJlc3VsdDsKICAgIH0KCgogICAgc2ggPSBsZW5ndGggLyAyOwogICAgZmggPSBsZW5ndGggLSBzaDsKCiAgICB4MSA9IHguc3Vic3RyKDAsIGZoKTsKICAgIHgyID0geC5zdWJzdHIoZmgsIHNoKTsKCiAgICB5MSA9IHkuc3Vic3RyKDAsIGZoKTsKICAgIHkyID0geS5zdWJzdHIoZmgsIHNoKTsKCiAgICBhID0gcHJvZHVjdDJOdW1iZXJzKHgxLCB5MSk7CiAgICBkID0gcHJvZHVjdDJOdW1iZXJzKHgyLCB5Mik7CiAgICBlID0gcHJvZHVjdDJOdW1iZXJzKGFkZDJOdW1iZXJzKHgxLCB4MiksIGFkZDJOdW1iZXJzKHkxLCB5MikpOwoKICAgIGUgPSBzdWJ0cmFjdDJOdW1iZXJzKGUsIGFkZDJOdW1iZXJzKGEsIGQpKTsKICAgIGFkZEJhY2tTaWRlWmVyb3MoYSwgbGVuZ3RoIC0gbGVuZ3RoICUgMik7CiAgICBhZGRCYWNrU2lkZVplcm9zKGUsIGxlbmd0aCAvIDIpOwoKICAgIHJldHVybiBhZGQzTnVtYmVycyhkLCBhLCBlKTsKfQoKc3RyaW5nIGRlY1RvQmluKGludCBuKXsKICAgIHN0cmluZyB4ID0gIiI7CgogICAgd2hpbGUobiA+IDApewogICAgICAgIGlmKG4gJSAyID09IDEpewogICAgICAgICAgICB4ID0gJzEnICsgeDsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgeCA9ICcwJyArIHg7CiAgICAgICAgfQogICAgICAgIG4gLz0gMjsKICAgIH0KCiAgICByZXR1cm4geDsKfQoKCnN0cmluZyBleHBvbmVudGlhdGlvbihzdHJpbmcgbnVtYmVyLCBpbnQgZXhwb25lbnQpewogICAgc3RyaW5nIGV4cG9uZW50QklOQVJZLCBzb2x1dGlvbj0iMSI7CgogICAgZXhwb25lbnRCSU5BUlkgPSBkZWNUb0JpbihleHBvbmVudCk7CgogICAgaWYobnVtYmVyID09ICIwIil7CiAgICAgICAgcmV0dXJuICIwIjsKICAgIH0KCiAgICBmb3IoaW50IGkgPSBleHBvbmVudEJJTkFSWS5zaXplKCkgLSAxOyBpID49IDA7IGktLSl7CiAgICAgICAgaWYoZXhwb25lbnRCSU5BUllbaV0gPT0gJzEnKXsKICAgICAgICAgICAgc29sdXRpb24gPSBwcm9kdWN0Mk51bWJlcnMoc29sdXRpb24sIG51bWJlcik7CiAgICAgICAgfQogICAgICAgIGlmKGkgIT0gMCl7CiAgICAgICAgICAgIG51bWJlciA9IHByb2R1Y3QyTnVtYmVycyhudW1iZXIsIG51bWJlcik7CiAgICAgICAgfQoKCiAgICB9CiAgICBkZWxldGVGcm9udFplcm9zKHNvbHV0aW9uKTsKCiAgICByZXR1cm4gc29sdXRpb247Cn0KCmludCBtYWluKCl7CiAgICBzdHJpbmcgeDsKICAgIGludCB5OwoKICAgIGNpbiA+PiB4ID4+IHk7CiAgICBjb3V0IDw8IGV4cG9uZW50aWF0aW9uKHgsIHkpIDw8IGVuZGw7Cgp9Cg==