#include <bits/stdc++.h>
using namespace std;

/*****
a, b, c = number
n = length of a
m = length of b
k = max(n, m)
+ : O(n + m)
- : Not Defined
* : O(k log k) with FFT
/ : Not Defined
pow(a, b) : O((m + n log n) log b)
*****/

typedef complex<double> cpx;
typedef vector<cpx> vec;
const double pi = acos(-1);

struct BigInt{
	vector<int> v;
	BigInt(){
		v.clear(); v.push_back(0);
	}
	BigInt(long long x){
		v.clear();
		while(x){
			v.push_back(x % 10); x /= 10;
		}
		if(v.size() == 0) v.push_back(0);
	}
	BigInt(const vector<int> &t){
		v.clear(); v.reserve(t.size());
		for(auto i : t) v.push_back(i);
		while(v.size() > 1 && v.back() == 0) v.pop_back();
	}
	void print(){
		while(v.size() > 1 && v.back() == 0) v.pop_back();
		for(int i=v.size()-1; i>=0; i--) cout << v[i];
	}
};

vector<int> Plus(const vector<int> &a, const vector<int> &b){
	int n = max(a.size(), b.size()) + 1;
	vector<int> ret(n);
	for(int i=0; i<a.size(); i++) ret[i] += a[i];
	for(int i=0; i<b.size(); i++) ret[i] += b[i];
	for(int i=0; i<n-1; i++){
		if(ret[i] < 0){
			int b = (abs(ret[i]) + 9) / 10;
			ret[i] += b * 10;
			ret[i+1] -= b;
		}else{
			ret[i+1] += ret[i] / 10;
			ret[i] %= 10;
		}
	}
	while(ret.size() > 1 && ret.back() == 0) ret.pop_back();
	return ret;
}

void FFT(vec &f, cpx w){
	int n = f.size();
	if(n == 1) return;
	vec even(n >> 1), odd(n >> 1);
	for(int i=0; i<n; i++){
		if(i & 1) odd[i >> 1] = f[i];
		else even[i >> 1] = f[i];
	}
	FFT(even, w*w); FFT(odd, w*w);
	cpx wp(1, 0);
	for(int i=0; i<n/2; i++){
		f[i] = even[i] + wp * odd[i];
		f[i+n/2] = even[i] - wp * odd[i];
		wp *= w;
	}
}

vec Mul(vec a, vec b){
	int n = 1;
	while(n <= a.size() || n <= b.size()) n <<= 1;
	n <<= 1;
	a.resize(n); b.resize(n);
	vec c(n);
	cpx w(cos(2*pi/n), sin(2*pi/n));
	FFT(a, w); FFT(b, w);
	for(int i=0; i<n; i++) c[i] = a[i] * b[i];
	FFT(c, cpx(w.real(), -w.imag()));
	for(int i=0; i<n; i++){
		c[i] /= cpx(n, 0);
		c[i] = cpx(round(c[i].real()), round(c[i].imag()));
	}
	return c;
}

vector<int> Mul(vector<int> a, vector<int> b){
	vec A, B, C;
	for(auto i : a) A.push_back(cpx(i, 0));
	for(auto i : b) B.push_back(cpx(i, 0));
	C = Mul(A, B);
	vector<int> v(C.size());
	for(int i=0; i<C.size(); i++) v[i] = (int)round(C[i].real());
	v.push_back(0);
	for(int i=0; i<v.size()-1; i++){
		if(v[i] < 0){
			int b = (abs(v[i]) + 9) / 10;
			v[i+1] -= b;
			v[i] += b * 10;
		}else{
			v[i+1] += v[i] / 10;
			v[i] %= 10;
		}
	}
	while(v.size() > 1 && v.back() == 0) v.pop_back();
	return v;
}

BigInt div2(BigInt a){
	int c = 0;
	for(int i=a.v.size()-1; i>=0; i--){
		int now = c*10 + a.v[i];
		c = now % 2;
		a.v[i] = now / 2;
	}
	while(a.v.size() > 1 && a.v.back() == 0) a.v.pop_back();
	return a;
}

BigInt operator + (const BigInt &a, const BigInt &b){
	vector<int> ret = Plus(a.v, b.v);
	return BigInt(ret);
}

BigInt operator * (const BigInt &a, const BigInt &b){
	vector<int> ret = Mul(a.v, b.v);
	return BigInt(ret);
}

BigInt pow(BigInt a, BigInt b){
	BigInt ret(1);
	while(1){
		if(b.v.size() == 0) break;
		if(b.v.size() == 1 && b.v[0] == 0) break;
		if(b.v[0] & 1) ret = ret * a;
		a = a * a;
		b = div2(b);
	}
	return ret;
}