#include <cstdio>
#include <cassert>
#include <cstring>

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

typedef long long ll;

const int NUM_LEN = 23;
const int BASE_LEN = 9;
const int BASE = (int)1e9;
const ll INF = (ll)8e18;

struct num
{
  ll a[NUM_LEN];
  int len; // always > 0

  inline const ll& operator [] ( int i ) const { return a[i]; }
  inline ll& operator [] ( int i ) { return a[i]; }

  num() { len = 1, a[0] = 0; } // 0
  
  num& operator = ( const num &x ) // copy
  {
    len = x.len;
    forn(i, len)
      a[i] = x[i];
    return *this;
  }

  num( const num &x ) { *this = x; } // copy

  num( ll x ) // x
  {
    len = 0;
    while (!len || x)
    {
      assert(len + 1 <= NUM_LEN); // to catch overflow
      a[len++] = x % BASE, x /= BASE;
    }
  }

  num& cor()
  {
    while (a[len - 1] >= BASE)
    {
      assert(len + 1 <= NUM_LEN); // to catch overflow
      if (a[len - 1] >= 2 * BASE)
      {
        a[len] = a[len - 1] / BASE;
        a[len - 1] %= BASE;
      }
      else
      {
        a[len] = 1;
        a[len - 1] -= BASE;
      }
      len++;
    }
    while (len > 1 && !a[len - 1])
      len--;
    return *this;
  }

  void out() const
  {
    int i = len - 1;
    printf("%d", (int)a[i--]);
    while (i >= 0)
      printf("%0*d", BASE_LEN, (int)a[i--]);
    puts("");
  }

  void read()
  {
    static char s[NUM_LEN * BASE_LEN + 1];
    scanf("%s", s);
    int slen = strlen(s);
    int x = 1, j = 0;
    len = 0;
    for (int i = slen - 1; i >= 0; i--)
    {
      if (x == 1)
        len++, a[j] = 0;
      a[j] += x * (s[i] - '0');
      if ((x *= 10) == BASE)
        j++, x = 1;
    }
    if (len == 0)
      a[len++] = 0;
  }
};

num& operator += ( num &a, const num &b )
{
  while (a.len < b.len)
    a[a.len++] = 0;
  forn(i, b.len)
    a[i] += b[i];
  forn(i, a.len - 1)
    if (a[i] >= BASE)
      a[i] -= BASE, a[i + 1]++;
  return a.cor();
}

num& operator -= ( num &a, const num &b )
{
  while (a.len < b.len)
    a[a.len++] = 0;
  forn(i, b.len)
    a[i] -= b[i];
  forn(i, a.len - 1)
    if (a[i] < 0)
      a[i] += BASE, a[i + 1]--;
  assert(a[a.len - 1] >= 0); // a >= b
  return a.cor();
}

num& operator *= ( num &a, int k )
{
  if (k == 1)
    return a;
  if (k == 0)
  {
    a.len = 0;
    return a;
  }
  forn(i, a.len)
    a[i] *= k;
  forn(i, a.len - 1)
    if (a[i] >= BASE)
      a[i + 1] += a[i] / BASE, a[i] %= BASE;
  return a.cor();
}

num& operator /= ( num &a, int k )
{
  for (int i = a.len - 1; i > 0; i--)
    a[i - 1] += (ll)(a[i] % k) * BASE, a[i] /= k;
  a[0] /= k;
  return a.cor();
}

num& operator *= ( num &a, const num &b )
{
  ll x[NUM_LEN];
  assert(a.len + b.len - 1 <= NUM_LEN);
  forn(i, a.len + b.len - 1)
    x[i] = 0;
  forn(i, a.len)
    forn(j, b.len)
      if ((x[i + j] += a[i] * b[j]) >= INF)
        x[i + j + 1] += x[i + j] / BASE, x[i + j] %= BASE;
  a.len += b.len - 1;
  forn(i, a.len)
    a[i] = x[i];
  forn(i, a.len - 1)
    if (a[i] >= BASE)
      a[i + 1] += a[i] / BASE, a[i] %= BASE;
  return a.cor();
}

int cmp( const num &a, const num &b )
{
  if (a.len != b.len)
    return a.len - b.len;
  for (int i = a.len - 1; i >= 0; i--)
    if (a[i] != b[i])
      return a[i] - b[i];
  return 0;
}

bool operator == ( const num &a, const num &b ) { return cmp(a, b) == 0; }
bool operator != ( const num &a, const num &b ) { return cmp(a, b) != 0; }
bool operator < ( const num &a, const num &b ) { return cmp(a, b) < 0; }
bool operator > ( const num &a, const num &b ) { return cmp(a, b) > 0; }
bool operator <= ( const num &a, const num &b ) { return cmp(a, b) <= 0; }
bool operator >= ( const num &a, const num &b ) { return cmp(a, b) >= 0; }

num operator + ( const num &a, const num &b ) { num c = a; c += b; return c; }
num operator - ( const num &a, const num &b ) { num c = a; c -= b; return c; }
num operator * ( const num &a, const num &b ) { num c = a; c *= b; return c; }
num operator * ( const num &a, int k )        { num c = a; c *= k; return c; }
num operator / ( const num &a, int k )        { num c = a; c /= k; return c; }

num operator ^ ( const num &a, int k )
{
  num res(1);
  forn(i, k)
    res *= a;
  return res;
}