#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cctype>
#include <cstdio>
#include <iomanip>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <complex>
#include <numeric>
#include <valarray>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
#define inf 1061109567
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define mem(x,a) memset(x,a,sizeof(x))
#define rep(i,n) for(int i(0),_n(n);i<_n;++i)
#define repi(i,a,b) for(int i(a),_b(b);i<_b;++i)
#define repr(i,a,b) for(int i(a),_b(b);i>=_b;--i)
#define repe(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define len(x) ((int)(x.size()))
class BigInt {
int size;
unsigned *data;
int alloc;
unsigned _data[5];
public:
// Memory management
void reserve(int n) {
if (data == NULL) {
data = _data;
alloc = sizeof(_data)/sizeof(_data[0]);
}
if (alloc < n) {
while (alloc < n) alloc <<= 1;
if (data == _data) {
data = (unsigned *)malloc(alloc * sizeof(unsigned));
assert(data != NULL);
memcpy(data, _data, sizeof(_data));
} else {
data = (unsigned *)realloc(data, alloc * sizeof(unsigned));
assert(data != NULL);
}
}
}
~BigInt() {
if (data != _data) free(data);
}
void swap(BigInt &y) {
if (data != _data && y.data != y._data) {
std::swap(size, y.size); std::swap(alloc, y.alloc);
std::swap(data, y.data);
} else {
BigInt t(*this); assign(y); y.assign(t);
}
}
private:
typedef unsigned long long uint64;
static inline int sgn(int n) { return n == 0 ? 0 : (n < 0 ? -1 : 1); }
// Removes leading zeroes
void normalize() {
int n = abs(size);
while (n > 0 && data[n-1] == 0) n--;
size = (size < 0 ? -n : n);
}
static int absCmp(const BigInt &x, const BigInt &y) {
int xn = abs(x.size), yn = abs(y.size);
if (xn != yn) return sgn(xn - yn);
for (int i = xn-1; i >= 0; i--)
if (x.data[i] != y.data[i]) return x.data[i] > y.data[i] ? +1 : -1;
return 0;
}
// z = abs(x) + abs(y);
static void absAdd(BigInt &z, const BigInt &x, const BigInt &y) {
int xn = abs(x.size), yn = abs(y.size);
if (xn < yn) { absAdd(z, y, x); return; }
int zn = max(xn, yn);
z.reserve(zn + 1);
uint64 c = 0;
for (int i = 0; i < yn; i++, c >>= 32)
z.data[i] = (unsigned)((c += x.data[i] + (uint64)y.data[i]) & 0xFFFFFFFFU);
if (&z == &x) {
for (int i = yn; c != 0 && i < xn; i++, c >>= 32)
z.data[i] = (unsigned)((c += x.data[i]) & 0xFFFFFFFFU);
} else {
for (int i = yn; i < xn; i++, c >>= 32)
z.data[i] = (unsigned)((c += x.data[i]) & 0xFFFFFFFFU);
}
if (c != 0) z.data[zn++] = (unsigned)c;
z.size = zn;
}
// z = abs(x) + abs(y)
static void absAdd1(BigInt &z, const BigInt &x, unsigned y) {
int n = abs(x.size);
z.reserve(n+1);
uint64 c = y;
if (&z == &x) {
for (int i = 0; c != 0 && i < n; i++, c >>= 32)
z.data[i] = (unsigned)((c += x.data[i]) & 0xFFFFFFFFU);
} else {
for (int i = 0; i < n; i++, c >>= 32)
z.data[i] = (unsigned)((c += x.data[i]) & 0xFFFFFFFFU);
}
if (c != 0) z.data[n++] = (unsigned)c;
z.size = n;
}
// z = abs(x) - abs(y)
static void absSub(BigInt &z, const BigInt &x, const BigInt &y) {
int t = absCmp(x, y);
if (t <= 0) {
if (t == 0) z.size = 0; else absSub(z, y, x);
z.size = -z.size;
return;
}
int xn = abs(x.size), yn = abs(y.size);
z.reserve(max(xn, yn));
uint64 c = 1;
for (int i = 0; i < yn; i++, c >>= 32) {
c += (uint64)x.data[i] + ((uint64)y.data[i] ^ 0xFFFFFFFFULL);
z.data[i] = (unsigned)(c & 0xFFFFFFFFU);
}
if (&z == &x) {
for (int i = yn; c != 1 && i < xn; i++, c >>= 32)
z.data[i] = (unsigned)((c += (uint64)x.data[i] + 0xFFFFFFFFULL) & 0xFFFFFFFFU);
} else {
for (int i = yn; i < xn; i++, c >>= 32)
z.data[i] = (unsigned)((c += (uint64)x.data[i] + 0xFFFFFFFFULL) & 0xFFFFFFFFU);
}
assert(c == 1);
z.size = xn;
while (z.size > 0 && z.data[z.size-1] == 0) z.size--;
assert(z.size > 0);
}
// z = abs(x) - abs(y)
static void absSub1(BigInt &z, const BigInt &x, unsigned y) {
if (y == 0) { z.assign(x); z.size = abs(z.size); return; }
if (x.size == 0) { z.size = -1; z.data[0] = y; return; }
int xn = abs(x.size);
if (xn == 1) {
if (x.data[0] > y) { z.size = 1; z.data[0] = x.data[0] - y; }
else if (x.data[0] == y) { z.size = 0; }
else { z.size = -1; z.data[0] = y - x.data[0]; }
return;
}
z.reserve(xn);
uint64 c = 1 + (uint64)x.data[0] + (y ^ 0xFFFFFFFFULL);
z.data[0] = (unsigned)c;
c >>= 32;
if (&z == &x) {
for (int i = 1; c != 1 && i < xn; i++, c >>= 32)
z.data[i] = (unsigned)(c += (uint64)x.data[i] + 0xFFFFFFFFULL);
} else {
for (int i = 1; i < xn; i++, c >>= 32)
z.data[i] = (unsigned)(c += (uint64)x.data[i] + 0xFFFFFFFFULL);
}
z.size = xn;
while (z.size > 0 && z.data[z.size-1] == 0) z.size--;
}
// z = abs(x) * m + a
static void absMulAdd1(BigInt &z, const BigInt &x, unsigned m, unsigned a) {
int n = abs(x.size);
z.reserve(n+2);
uint64 c = a;
for (int i = 0; i < n; i++, c >>= 32) {
c = (c + (uint64)x.data[i] * (unsigned)m);
z.data[i] = (unsigned)(c & 0xFFFFFFFFU);
}
while (c != 0) { z.data[n++] = (unsigned)c; c >>= 32; }
z.size = n;
}
// z = x + sign*y. Asserts: abs(sign) = 1
static void add(BigInt &z, const BigInt &x, int sign, const BigInt &y) {
int xs = sgn(x.size), ys = sign * sgn(y.size);
if (xs == 0) { z.assign(y); z.size *= sign; }
else if (ys == 0) z.assign(x);
else if (xs == ys) { absAdd(z, x, y); z.size *= xs; }
else if (ys < 0) absSub(z, x, y);
else { absSub(z, x, y); z.size = -z.size; }
}
static void add1s(BigInt &z, const BigInt &x, int y) {
int xs = (x.size >= 0 ? +1 : -1), ys = (y >= 0 ? +1 : -1);
if (xs == ys) { absAdd1(z, x, abs(y)); z.size *= xs; }
else if (ys < 0) { absSub1(z, x, -y); }
else { absSub1(z, x, y); z.size = -z.size; }
}
static void mul1s(BigInt &z, const BigInt &x, int y) {
if (y < 0) { mul1s(z, x, -y); z.size = -z.size; return; }
if (y == 0) { z.size = 0; return; }
if (y == 1) { z.assign(x); return; }
int n = abs(x.size);
z.reserve(n+1);
uint64 c = 0;
for (int i = 0; i < n; i++, c >>= 32) {
c = (c + (uint64)x.data[i] * (unsigned)y);
z.data[i] = (unsigned)(c & 0xFFFFFFFFU);
}
if (c != 0) z.data[n++] = (unsigned)c;
z.size = (x.size < 0 ? -n : n);
}
static void mulQuadratic(BigInt &z, const BigInt &x, const BigInt &y) {
if (&z == &x || &z == &y) {
BigInt t;
mulQuadratic(t, x, y);
z = t;
return;
}
int xn = abs(x.size), yn = abs(y.size), zn = xn + yn + 1;
z.reserve(zn);
for (int i = 0; i < zn; i++) z.data[i] = 0;
for (int i = 0; i < xn; i++) {
uint64 c = 0;
int k = i;
for (int j = 0; j < yn; j++, k++, c >>= 32) {
c += z.data[k] + x.data[i] * (uint64)y.data[j];
z.data[k] = (unsigned)(c & 0xFFFFFFFFU);
}
for (; c != 0; k++, c >>= 32)
z.data[k] = (unsigned)((c += z.data[k]) & 0xFFFFFFFFU);
}
z.size = zn * sgn(x.size) * sgn(y.size);
z.normalize();
}
static void mulKaratsuba(BigInt &z, const BigInt &x, const BigInt &y) {
int xn = abs(x.size), yn = abs(y.size), zs = sgn(x.size) * sgn(y.size);
int w = max(xn, yn) >> 1;
BigInt A(x.data+w, max(0, xn-w)), B(x.data, min(xn, w));
BigInt C(y.data+w, max(0, yn-w)), D(y.data, min(yn, w));
BigInt R, T;
absAdd(z, A, B);
absAdd(T, C, D);
mul(R, z, T);
mul(z, A, C);
mul(T, B, D);
R -= z; R -= T; R <<= w*32;
z <<= w*64; z += R; z += T; z.size *= zs;
}
BigInt(unsigned a[], int n) {
if (n < 0) n = 0;
while (n > 0 && a[n-1] == 0) n--;
data = NULL;
reserve(n);
size = n;
memcpy(data, a, n * sizeof(unsigned));
}
// q = abs(x) div abs(y); Returns abs(x) mod abs(y)
static unsigned absDiv1(BigInt &q, const BigInt &x, unsigned y) {
assert(y != 0);
int n = abs(x.size);
q.reserve(n);
uint64 c = 0;
for (int i = n-1; i >= 0; i--) {
c = (c << 32) | (uint64)x.data[i];
q.data[i] = (unsigned)(c / y);
c %= y;
}
q.size = n;
q.normalize();
return (unsigned)c;
}
// u = abs(u) mod abs(v), q = abs(u) div abs(v)
static void absDiv(BigInt *q, BigInt &u, BigInt v) {
if (q != NULL && q == &u) {
BigInt t;
absDiv(&t, u, v);
*q = t;
return;
}
u.size = abs(u.size);
v.size = abs(v.size);
assert(v.size > 0);
if (u.size < v.size) { if (q) *q = 0; return; }
if (v.size == 1) {
unsigned t = absDiv1(q==NULL ? u : *q, u, v.data[0]);
u.data[0] = t;
u.size = (t == 0 ? 0 : 1);
return;
}
int n = v.size, d = 0;
while (((v.data[n-1] << d) & 0x80000000U) == 0) d++;
u <<= d;
v <<= d;
unsigned vh = v.data[n-1], vh2 = v.data[n-2];
uint64 c, g;
u.reserve(u.size+1); u.data[u.size] = 0;
v.reserve(v.size+1); v.data[v.size] = 0;
int qp = u.size - v.size + 1;
if (q) { q->reserve(qp+1); q->size = qp; }
for (int up = u.size-1; --qp >= 0; up--) {
c = (((uint64)u.data[up+1]) << 32) | (uint64)u.data[up];
g = c / (uint64)vh;
if (g > 0xFFFFFFFFULL) g = 0xFFFFFFFFULL;
while ((c - g*vh) < 0x100000000ULL &&
(((c - g*vh) << 32) + u.data[up-1]) < (g*(uint64)vh2))
g--;
c = 0;
for (int i = qp, j = 0; j <= n; i++, j++) {
c += g * (uint64)v.data[j];
if (u.data[i] >= (unsigned)(c & 0xFFFFFFFFULL)) {
u.data[i] -= (unsigned)(c & 0xFFFFFFFFULL);
c >>= 32;
} else {
u.data[i] += (unsigned)(0x100000000ULL - (c & 0xFFFFFFFFULL));
c = (c >> 32) + 1;
}
}
if (c != 0) {
g--;
assert(c == 1);
c = 0;
for (int i = qp, j = 0; j <= n; i++, j++, c >>= 32) {
c += (uint64)u.data[i] + (uint64)v.data[j];
u.data[i] = (unsigned)c;
}
assert(c == 1);
}
if (q) q->data[qp] = (unsigned)g;
}
u >>= d;
v >>= d;
if (q) q->normalize();
}
public:
static int cmp(const BigInt &x, const BigInt &y) {
if (x.size != y.size) return sgn(x.size - y.size);
return absCmp(x, y) * (x.size < 0 ? -1 : 1);
}
static int cmp1s(const BigInt &x, int y) {
if (y == 0) return sgn(x.size);
if (y > 0) {
if (x.size <= 0) return -1;
if (x.size > 1) return +1;
if (x.data[0] == (unsigned)y) return 0;
return x.data[0] > (unsigned)y ? +1 : -1;
} else {
if (x.size >= 0) return +1;
if (x.size < -1) return -1;
if (x.data[0] == (unsigned)(-y)) return 0;
return x.data[0] > (unsigned)(-y) ? -1 : +1;
}
}
static void add(BigInt &z, const BigInt &x, const BigInt &y) {
add(z, x, +1, y);
}
static void sub(BigInt &z, const BigInt &x, const BigInt &y) {
add(z, x, -1, y);
}
static void mul(BigInt &z, const BigInt &x, const BigInt &y) {
if (max(abs(x.size), abs(y.size)) < 64)
mulQuadratic(z, x, y);
else
mulKaratsuba(z, x, y);
}
static void mod(BigInt &r, const BigInt &u, const BigInt &v) {
r = u;
absDiv(NULL, r, v);
}
static void div(BigInt &q, BigInt &r, const BigInt &u, const BigInt &v) {
int us = sgn(u.size), vs = sgn(v.size);
r = u;
absDiv(&q, r, v);
//TODO
if (us*vs < 0) q.size = -q.size;
}
void assign(int n) { reserve(1); size = sgn(n); data[0] = abs(n); }
void assign(long long n) {
reserve(2);
if (n < 0) { size = -2; n = -n; } else { size = 2; }
data[0] = (unsigned)(n & 0xFFFFFFFFU);
data[1] = (unsigned)(n >> 32);
normalize();
}
void assign(const BigInt &b) {
if (this == &b) return;
int n = abs(b.size);
reserve(n);
size = b.size;
memcpy(data, b.data, n * sizeof(unsigned));
}
void assign(const char *s, int radix = 10) {
assert(2 <= radix && radix <= 36);
while (isspace(*s)) s++;
int sign = 1;
if (*s == '+') { s++; } else if (*s == '-') { s++; sign = -1; }
while (*s == '0') s++;
int n = 0;
for (n = 0; s[n] && isalnum(s[n]); n++);
size = 0;
if (n > 20)
reserve((int)(log((double)radix)/log(2.0)/32.0*n) + 2);
else
reserve(n/9+2);
unsigned a = 0, m = 1;
for (int i = 0; i < n; i++) {
int dig = (isdigit(s[i]) ? (s[i]-'0') : (toupper(s[i])-'A'+10));
assert(dig < radix);
a = a * radix + dig;
m *= radix;
if (m > 0x3000000) { absMulAdd1(*this, *this, m, a); a = 0; m = 1; }
}
if (m > 1) absMulAdd1(*this, *this, m, a);
size *= sign;
}
BigInt(int n = 0) { data = NULL; assign(n); }
BigInt(int n, int cap) { data = NULL; reserve(cap); assign(n); }
BigInt(long long n) { data = NULL; assign(n); }
BigInt(const BigInt &b) { data = NULL; assign(b); }
BigInt(const char *s, int radix = 10) { data = NULL; assign(s, radix); }
BigInt(const string &s, int radix = 10) { data = NULL; assign(s.c_str(), radix); }
BigInt &operator =(int n) { assign(n); return *this; }
BigInt &operator =(long long n) { assign(n); return *this; }
BigInt &operator =(const BigInt &b) { assign(b); return *this; }
BigInt &operator =(const char *s) { assign(s); return *this; }
BigInt &operator =(const string &s) { assign(s.c_str()); return *this; }
BigInt &operator +=(const BigInt &y) { add(*this, *this, +1, y); return *this; }
BigInt &operator -=(const BigInt &y) { add(*this, *this, -1, y); return *this; }
BigInt &operator *=(const BigInt &y) { mul(*this, *this, y); return *this; }
BigInt &operator /=(const BigInt &y) { BigInt q, r; div(q, r, *this, y); assign(q); return *this; }
BigInt &operator %=(const BigInt &y) { mod(*this, *this, y); return *this; }
BigInt &operator +=(int y) { add1s(*this, *this, y); return *this; }
BigInt &operator -=(int y) { add1s(*this, *this, -y); return *this; }
BigInt &operator *=(int y) { mul1s(*this, *this, y); return *this; }
BigInt &operator <<=(int n) { shl(n); return *this; }
BigInt &operator >>=(int n) { shr(n); return *this; }
void operator ++() { add1s(*this, *this, 1); }
void operator --() { add1s(*this, *this, -1); }
BigInt operator -() const { BigInt z = *this; z.negate(); return z; }
BigInt operator >>(int n) const { BigInt r = *this; r.shr(n); return r; }
BigInt operator <<(int n) const { BigInt r = *this; r.shl(n); return r; }
string str(int radix = 10) const {
assert(2 <= radix && radix <= 36);
if (size == 0) return "0";
int y = 1, m = 0;
while (y < 0x300000) { y *= radix; m++; }
BigInt x(*this);
x.size = abs(x.size);
char *tmp = (char *)malloc(x.size*(radix>=10?10:32)+10);
int n = 0;
while (x.size != 0) {
unsigned r = absDiv1(x, x, y);
for (int i = 0; i < m; i++, r /= radix)
tmp[n++] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[r % radix];
}
while (n > 0 && tmp[n-1] == '0') n--;
if (size < 0) tmp[n++] = '-';
reverse(tmp, tmp+n);
tmp[n] = 0;
string res = string(tmp);
free(tmp);
return res;
}
string toString(int r = 10) const { return str(r); }
int toInt() const { return sgn(size) * (int)data[0]; }
long long toLL() const {
long long r = 0;
for (int i = 0; i < 2 && i < abs(size); i++) r = (r << 32) | data[i];
return size < 0 ? -r : r;
}
void setBit(int n) {
int s = abs(size), m = (n>>5)+1;
reserve(m);
while (s < m) data[s++] = 0;
size = (size < 0 ? -s : s);
data[n>>5] |= 1U << (n & 31);
}
void clrBit(int n) { if (abs(size) > (n>>5)) { data[n>>5] &= ~(1U << (n & 31)); normalize(); } }
int getBit(int n) const { return (abs(size) > (n>>5)) ? ((data[n>>5]>>(n&31))&1) : 0; }
// Returns 1+(index of highest non-zero bit)
int bitSize() const {
if (size == 0) return 0;
int n = (abs(size) - 1) * 32;
unsigned t = data[abs(size)-1];
if (t >= 65536) { n += 16; t >>= 16; }
if (t >= 256) { n += 8; t >>= 8; }
if (t >= 16) { n += 4; t >>= 4; }
if (t >= 4) { n += 2; t >>= 2; }
if (t >= 2) { n++; t >>= 1; }
if (t >= 1) n++;
return n;
}
void shl(int s) {
if (size == 0) return;
if (s < 0) shr(-s);
int n = abs(size), w = s >> 5;
reserve(n + w + 1);
if (w > 0) {
for (int i = n-1; i >= 0; i--) data[i+w] = data[i];
for (int i = w-1; i >= 0; i--) data[i] = 0;
n += w;
}
s &= 31;
if (s > 0) {
unsigned a = 0, b;
data[n++] = 0;
for (int i = 0; i < n; i++) {
b = data[i] >> (32 - s);
data[i] = (data[i] << s) | a;
a = b;
}
}
size = (size < 0 ? -n : n);
normalize();
}
void shr(int s) {
if (s < 0) shl(-s);
int n = abs(size), w = s >> 5;
if (w > 0) {
for (int i = 0; i+w < n; i++) data[i] = data[i+w];
n -= w;
if (n < 0) n = 0;
}
s &= 31;
if (s > 0) {
unsigned a = 0, b;
for (int i = n-1; i >= 0; i--) {
b = data[i] << (32 - s);
data[i] = (data[i] >> s) | a;
a = b;
}
}
size = (size < 0 ? -n : n);
normalize();
}
void negate() { size = -size; }
int sign() const { return sgn(size); }
int compareTo(const BigInt &y) const { return cmp(*this, y); }
int compareTo(int y) const { return cmp1s(*this, y); }
};
BigInt operator +(const BigInt &x, const BigInt &y) { BigInt z; BigInt::add(z, x, y); return z; }
BigInt operator -(const BigInt &x, const BigInt &y) { BigInt z; BigInt::sub(z, x, y); return z; }
BigInt operator *(const BigInt &x, const BigInt &y) { BigInt z; BigInt::mul(z, x, y); return z; }
BigInt operator /(const BigInt &x, const BigInt &y) { BigInt q, r; BigInt::div(q, r, x, y); return q; }
BigInt operator %(const BigInt &x, const BigInt &y) { BigInt r; BigInt::mod(r, x, y); return r; }
bool operator ==(const BigInt &x, const BigInt &y) { return BigInt::cmp(x, y) == 0; }
bool operator ==(const BigInt &x, int y) { return BigInt::cmp1s(x, y) == 0; }
bool operator !=(const BigInt &x, const BigInt &y) { return BigInt::cmp(x, y) != 0; }
bool operator <(const BigInt &x, const BigInt &y) { return BigInt::cmp(x, y) < 0; }
bool operator <=(const BigInt &x, const BigInt &y) { return BigInt::cmp(x, y) <= 0; }
bool operator >(const BigInt &x, const BigInt &y) { return BigInt::cmp(x, y) > 0; }
bool operator >=(const BigInt &x, const BigInt &y) { return BigInt::cmp(x, y) >= 0; }
ostream &operator <<(ostream &o, const BigInt &x) { return o << x.str(); }
istream &operator >>(istream &i, BigInt &x) { string s; i >> s; x = s; return i; }
namespace std { template<> inline void swap(BigInt &a, BigInt &b) { a.swap(b); } }
// Returns floor(sqrt(a)).
BigInt isqrt(const BigInt &a) {
assert(a >= 0);
if (a == 0) return 0;
BigInt x, y;
x.setBit(a.bitSize()/2 + 2);
for (;;) {
y = a; y /= x; y += x; y >>= 1;
if (y < x) x = y; else return x;
}
}
BigInt pow(BigInt b, int p) {
assert(p >= 0);
BigInt r = 1;
for (int i = 0; (p >> i) != 0; i++) {
if (i != 0) b *= b;
if (p & (1 << i)) r *= b;
}
return r;
}
BigInt modpow(BigInt b, const BigInt &e, const BigInt &m) {
assert(e >= 0 && m > 0);
if (m == 1) return 0;
BigInt r = 1;
for (int i = 0, n = e.bitSize(); i < n; i++) {
if (i != 0) { b *= b; b %= m; }
if (e.getBit(i)) { r *= b; r %= m; }
}
return r;
}
// Asserts that n is odd, n >= 3, and 1<=base<n.
bool millerRabin(const BigInt &n, const BigInt &base) {
BigInt n1 = n; --n1;
int s = 0;
while (n1.getBit(s) == 0) s++;
BigInt t = modpow(base, n1>>s, n);
if (t == 1) return true;
for (int i = 0; i < s && t > 1; i++) {
if (i > 0) { t *= t; t %= n; }
if (t == n1) return true;
}
return false;
}
bool probablePrime(const BigInt &n) {
if (n <= 1) return false;
if (n.getBit(0) == 0) return (n == 2);
if (n < 100000) {
int t = n.toInt();
for (int d = 3; d*d <= t; d += 2)
if ((t % d) == 0) return false;
return true;
}
static int p[]={3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,0};
for (int i = 0; p[i] != 0; i++)
if ((n % p[i]) == 0) return false;
static int a[] = {2,7,61,3,24251,5,11,13,17,19,23,29,0};
for (int i = 0; a[i] != 0; i++) {
if (i == 5 && n.bitSize() < 52) break;
if (!millerRabin(n, a[i])) return false;
}
return true;
}
BigInt a,b,c,lo,hi,mid,ans;
ll n,r,t;
int main()
{
/*long long cs,tst;
scanf("%lld",&cs);
for(tst=1;tst<=cs;tst++)
{
BigInt a,b;
cin>>a>>b;
//printf("Case %ld: ",tst);
cout<<(a+b)/2<<endl;
}*/
long i,n,d;
while(cin>>n>>d)
{
if(n==0&&d==0)
break;
BigInt ans=1,ans1=1;
for(i=1;i<=d;i++)
{
ans*=n;
}
cout<<ans<<endl;
}
}
