#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i, n) for(int i = 0; i < (n); i++) #define per(i, n) for(int i = (n) - 1; i >= 0; i--) using ll = long long; #define vi vector #define vvi vector #define vl vector #define pii pair #define pll pair #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() constexpr int mod = 1000000007; using namespace std; template bool chmax(T &a, const U &b){ return a < b ? (a = b, 1) : 0; } template bool chmin(T &a, const U &b){ return a > b ? (a = b, 1) : 0; } struct bint { private: static constexpr int BASE = 100000000; static constexpr int LEN = 8; //log10(BASE) bool negative; vector a; int n = 0; bint &normalize(){ int i = n - 1; while(i >= 0 && a[i] == 0) i--; a.resize(i + 1); n = i + 1; if(n == 0) negative = false; return *this; } public: bint(int x = 0) : negative(x < 0){ if(negative) x = -x; for(; x > 0; x /= BASE){ a.push_back(x % BASE); n++; } } bint(const string &s) : negative(false){ int p = 0; if(s[p] == '-'){ p++; negative = true; } else if(s[p] == '+') p++; for(int i = s.size() - 1, v = BASE; i >= p; i--, v *= 10){ int x = s[i] - '0'; if(x < 0 || 9 < x){ cerr << "error: parse error:" << s << "\n"; exit(1); } if(v == BASE){ v = 1; a.push_back(x); n++; }else a.back() += x * v; } normalize(); } bint &operator=(const bint& x){ negative = x.negative; a = x.a; n = x.n; return *this; } bint &operator=(int x){ return *this = bint(x); } bint &operator=(const std::string &s){ return *this = bint(s); } const bool operator<(const bint &x) const{ if(negative != x.negative) return negative < x.negative; if(n != x.n) return (n < x.n) ^ negative; for(int i = n - 1; i >= 0; i--) if(a[i] != x.a[i]) return (a[i] < x.a[i]) ^ negative; return false; } const bool operator>(const bint& x) const{ return x < (*this); } const bool operator<=(const bint& x) const{ return !(x < (*this)); } const bool operator>=(const bint& x) const{ return !((*this) < x); } const bool operator!=(const bint& x) const{ return (*this) < x || x < (*this); } const bool operator==(const bint& x) const{ return !((*this) < x || x < (*this)); } bint operator-() const{ bint ret(*this); if(n) ret.negative = !ret.negative; return ret; } bint &operator+=(const bint& x){ if(negative != x.negative) return *this -= -x; if(n < x.n){ a.resize(x.n); n = x.n; } int tmp = 0; for(int i = 0; i < n; i++){ a[i] += (i < x.n ? x.a[i] : 0) + tmp; tmp = a[i] / BASE; a[i] %= BASE; } if(tmp){ a.push_back(1); n++; } return *this; } bint &operator-=(const bint &x){ if(negative != x.negative) return *this += -x; vector b(x.a); int bn = b.size(); if((*this < x) ^ negative){ a.swap(b); swap(n, bn); negative = !negative; } for(int i = 0, tmp = 0; i < n; i++){ a[i] += BASE - (i < bn ? b[i] : 0) + tmp; tmp = a[i] / BASE - 1; a[i] %= BASE; } return this->normalize(); } bint &operator*=(const bint &x){ negative ^= x.negative; vector c(n * x.n + 1); for(int i = 0; i < n; i++){ ll tmp = 0; for(int j = 0; j < x.n; j++){ ll v = (ll)a[i] * x.a[j] + c[i+j] + tmp; tmp = v / BASE; c[i+j] = (int)(v % BASE); } if(tmp) c[i + x.n] += (int)tmp; } a.swap(c); n = a.size(); return this->normalize(); } bint &operator/=(const bint &x){ return *this = divmod(*this, x).first; } bint &operator%=(const bint &x){ return *this = divmod(*this, x).second; } const bint operator+(const bint &x) const{ bint res(*this); return res += x; } const bint operator-(const bint &x) const{ bint res(*this); return res -= x; } const bint operator*(const bint &x) const{ bint res(*this); return res *= x; } const bint operator/(const bint &x) const{ bint res(*this); return res /= x; } const bint operator%(const bint &x) const{ bint res(*this); return res %= x; } pair divmod(const bint &lhs, const bint &rhs){ if(!rhs.n){ cerr << "error: division by zero\n"; exit(1); } bint x(abs(rhs)), q, r; for(int i = lhs.n - 1; i >= 0; i--){ r = r * BASE + lhs.a[i]; int left = 0, right = BASE; if(r >= x){ while(left + 1 < right){ int mid = (left + right) / 2; if(x * bint(mid) > r) right = mid; else left = mid; } r -= x * left; } q.a.push_back(left); q.n++; } reverse(q.a.begin(), q.a.end()); bool neg = lhs.negative ^ lhs.negative; q.negative = neg; r.negative = neg; return { q.normalize(), r.normalize() }; } string to_string() const{ string s; if(negative) s += '-'; if(!n) s += '0'; else s += std::to_string(a.back()); for(int i = n - 2; i >= 0; i--){ const string t = std::to_string(a[i]); s += string(LEN - t.size(), '0'); s += t; } return s; } friend istream &operator>>(istream &is, bint &x){ string tmp; is >> tmp; x = bint(tmp); return is; } friend ostream &operator<<(ostream &os, const bint &x){ if(x.negative) os << '-'; if(!x.n) os << 0; else os << x.a.back(); for(int i = x.n - 2; i >= 0; i--){ os.width(LEN); os.fill('0'); os << x.a[i]; } return os; } const bint abs(bint x){ x.negative = false; return x; } }; int main(){ int n,m; cin >> n >> m; bint ans = 1; rep(i, n) ans *= m; cout << ans << "\n"; }