/**
   多倍長演算 名前空間
**/
namespace BigNum
{
  typedef unsigned short int Digit;        // 一つの桁に対する型
  typedef unsigned long int UnsignedBuff;  // 一桁 x 一桁を計算するためのバッファの型(符号なし)
  typedef long int SignedBuff;             // 一桁 x 一桁を計算するためのバッファの型(符号あり)

  /**
     符号なし多倍長整数
  **/
  class Unsigned
  {
    std::vector< Digit > number_; // 数列
    bool nan_;                    // Not A Number判定フラグ

    static const size_t DIGIT_BIT; // 一桁のビット数
    static const Digit DIGIT_MAX;  // 一桁の最大値

    void resize( size_t sz ) { number_.resize( sz, Digit() ); } // 桁数(数列のサイズ)を変更する

    void push_upper( Digit i = 0 ) { number_.push_back( i ); }   // 上位桁の追加
    void push_lower( Digit i = 0 ) { ushift(); number_[0] = i; } // 下位桁の追加

    void ushift( size_t cnt = 1 ); // 上位シフト
    void lshift( size_t cnt = 1 ); // 下位シフト
    void negZero();   // 上位の0部分を削除する
  :

public:

    /* コンストラクタ */

    /// long int からの構築
    ///
    /// 負数の場合は無効値 ( NaN ) 扱いされるので注意
    Unsigned( long int i = 0 );

    /* 初期化ルーチン */

    /// ゼロで初期化する
    ///
    /// 無効値だった場合は有効な値に変更する
    void clear() { number_.clear(); push_upper(); nan_ = false; }

    /* 判定ルーチン */

    /// 無効値(NaN)判定
    bool isNaN() const { return( nan_ ); }
    bool operator!() const { return( nan_ ); }

    /* ビットシフト */

    /// 代入演算子(右ビットシフト)
    Unsigned& operator>>=( UnsignedBuff num );
    /// 代入演算子(左ビットシフト)
    Unsigned& operator<<=( UnsignedBuff num );

    /* 比較演算子 */

    /// 等号演算子
    ///
    /// どちらかが無効値なら必ず false を返す。
    bool operator==( const Unsigned& num ) const;
    /// 相手より小さいかを判定する
    ///
    /// どちらかが無効値なら必ず false を返す。
    bool operator<( const Unsigned& num ) const;
    /// 相手より大きいかを判定する
    ///
    /// どちらかが無効値なら必ず false を返す。
    bool operator>( const Unsigned& num ) const;
    /// 不等号演算子
    ///
    /// どちらかが無効値なら必ず false を返す。
    bool operator!=( const Unsigned& num ) const;
    /// 相手以下かを判定する
    ///
    /// どちらかが無効値なら必ず false を返す。
    bool operator<=( const Unsigned& num ) const;
    /// 相手以上かを判定する
    ///
    /// どちらかが無効値なら必ず false を返す。
    bool operator>=( const Unsigned& num ) const;

    /* 配列としての演算子 */

    /// 桁数(数列のサイズ)を返す
    ///
    /// BigNum::Digit を一桁分とした時の桁数を返す
    size_t size() const { return( number_.size() ); }

    :
  };

  /*
    Unsigned::init 整数型からの変換

    t : 演算対象の数
  */
  template< class T >
  void Unsigned::init( T t )
  {
    assert( sizeof( Digit ) * 2 <= sizeof( UnsignedBuff ) );

    nan_ = false;
    if ( t < 0 ) { // 負数は全て無効値扱いとする
      nan_ = true;
      return;
    } else if ( t > DIGIT_MAX ) {
      UnsignedBuff buff = t;
      do {
        push_upper( buff & DIGIT_MAX );
        buff >>= DIGIT_BIT;
      } while ( buff > DIGIT_MAX );
      if ( buff > 0 ) push_upper( buff );
    } else {
      // 0 の場合も登録したいため、t > DIGIT_MAX とあえて場合分けする
      push_upper( t );
    }
  }

  // 符号付き整数から変換
  Unsigned::Unsigned( long int i )
  { init< long int >( i ); }
}

namespace BigNum
{
  /*
    Unsigned::isNaN 演算させる数を加味したNaNチェック
                    numがNaNの場合、自分自身もNaNになる

    num : 演算対象の数

    戻り値 : どちらかがNaNならばTrue
  */
  bool Unsigned::isNaN( const Unsigned& num )
  {
    if ( isNaN() ) return( true );
    if ( ! num ) {
      nan_ = true;
      return( true );
    }

    return( false );
  }

  /*
    partialAdd : 部分加算

    num : 加算する数
    start : 加算を始める位置
  */
  void Unsigned::partialAdd( const Unsigned& num, size_t start )
  {
    if ( isNaN( num ) ) return;
    if ( num == 0 ) return;

    if ( start + num.size() > size() ) resize( start + num.size() );
    size_t cnt = size();
    UnsignedBuff carry = 0; // 繰り上がり分
    for ( size_t i = start ; i < cnt ; i++ ) {
      if ( carry == 0 && i >= start + num.size() ) break; // 加算対象がなくなったら完了
      carry += number_[i];
      if ( i < start + num.size() ) carry += num.number_[i - start];
      number_[i] = carry & DIGIT_MAX;
      carry >>= DIGIT_BIT;
    }
    // 繰り上がりが残っていたらそれも加算する
    if ( carry > 0 )
      push_upper( carry );
  }

  /*
    Unsigned::operator+= +=演算子の多重定義

    num : 加算する数

    戻り値 : 自分自身
  */
  Unsigned& Unsigned::operator+=( const Unsigned& num )
  {
    partialAdd( num, 0 );

    return( *this );
  }

  /*
    Unsigned::operator-= -=演算子の多重定義

    num : 減算する数

    戻り値 : 自分自身
  */
  Unsigned& Unsigned::operator-=( const Unsigned& num )
  {
    if ( isNaN( num ) ) return( *this );

    // 減数が自分自身なら0にする
    if ( this == &num ) {
      clear();
      return( *this );
    }

    // 自分より大きな数を減算した場合、結果は不定とする
    if ( *this < num ) {
      nan_ = true;
      return( *this );
    }

    size_t cnt = size();
    SignedBuff carry = 0;
    for ( size_t i = 0 ; i < cnt ; i++ ) {
      if ( i >= num.size() && carry == 0 ) break; // 減算する対象がなくなったら終了
      SignedBuff n = number_[i] - carry;           // 桁借り分を引いておく
      if ( i < num.size() ) n -= num.number_[i];
      if ( n < 0 ) { // 結果が負なら上位から桁借り
        n += DIGIT_MAX + 1;
        carry = 1;
      } else {
        carry = 0;
      }
      number_[i] = n;
    }
    negZero();

    return( *this );
  }
}

namespace BigNum
{
  /*
    Unsigned::mulOneDigit 一桁の数で乗算する

    mulnum : 乗数
  */
  void Unsigned::mulOneDigit( Digit mulnum )
  {
    if ( mulnum == 0 ) {
      clear();
      return;
    }

    UnsignedBuff carry = 0; // 繰り上がり分
    for ( size_t i = 0 ; i < size() ; i++ ) {
      carry += static_cast< UnsignedBuff >( number_[i] ) * mulnum;
      number_[i] = carry & DIGIT_MAX;
      carry >>= DIGIT_BIT;
    }
    // 繰り上がりが残っていたらそれも加算する
    if ( carry > 0 ) push_upper( carry );
  }
}

namespace BigNum
{
  /*
    Unsigned::operator*= *=演算子の多重定義

    num : 乗数

    戻り値 : 自分自身
  */
  Unsigned& Unsigned::operator*=( const Unsigned& num )
  {
    if ( isNaN( num ) ) return( *this );

    // 被乗数(*this) = u, 乗数(num) = *v
    Unsigned u( *this );
    const Unsigned* v = ( this == &num ) ? new Unsigned( num ) : #

    try {
      clear();
      // *vの下位の桁から一桁ずつ乗算して結果に加算
      for ( UnsignedBuff i = v->size() ; i > 0 ; i-- ) {
        Unsigned ans( u );
        ans.mulOneDigit( v->number_[i - 1] );
        partialAdd( ans, i - 1 );
      }
    }
    catch(...) {
      if ( this == &num ) delete v;
      throw;
    }

    if ( this == &num ) delete v;

    return( *this );
  }
}

namespace BigNum
{
  /*
    Unsigned::divNDigit N+1桁(またはN桁)とN桁での除算を行う
                        被除数(*this)は処理後に商とvの積との差分=余りになる

    v : 除数(非0であること 0除算チェックはしていない)

    戻り値 : 商
  */
  Digit Unsigned::divNDigit( const Unsigned& v )
  {
    if ( this == &v ) {
      clear();
      return( 1 );
    }

    UnsignedBuff digit = v.size(); // 桁数(N)

    // 仮の商 qを求める
    UnsignedBuff q = number_[digit-1];
    if ( size() > digit ) q += static_cast< UnsignedBuff >( number_[digit] ) << DIGIT_BIT;
    q /= v.number_[digit-1];
    if ( q > DIGIT_MAX ) q = DIGIT_MAX; // qが DIGIT_MAXを越えたら補正(実際の商は DIGIT_MAXを越えない)

    // qとvの積を計算する
    Unsigned qv( v );
    qv.mulOneDigit( q );

    // 余り r = *this - qv < 0 の場合、仮の商が大きすぎるため、補正を行う。
    while ( operator<( qv ) ) {
      --q;
      operator+=( v );
    }
    operator-=( qv ); // 余りを代入

    return( q );
  }
}

namespace BigNum
{
  /*
    Unsigned::copy 部分コピー

    num : 対象の Unsigned
    s, e : コピーする要素の位置(開始・終了)

    this == &num の場合は処理しないことに注意
  */
  void Unsigned::copy( const Unsigned& num, size_t s, size_t e )
  {
    if ( this == &num ) return;

    number_.clear();
    if ( e - s + 1 > number_.capacity() )
      number_.reserve( e - s + 1 );
    while ( s <= e ) {
      if ( s >= num.size() ) break;
      push_upper( num.number_[s++] );
    }
    if ( size() == 0 ) push_upper();
    negZero();
  }

  /*
    Unsigned::div vとの除算を行い、商と余りを返す

    v : 除数
    r : 余りを返す変数へのポインタ

    戻り値 : 計算に成功した ... True
  */
  bool Unsigned::div( Unsigned v, Unsigned* r )
  {
    const Digit half = 1 << ( DIGIT_BIT - 1 ); // 一桁の最大値の半分

    if ( this == r ) return( false );
    if ( isNaN( v ) ) return( false );
    if ( v == 0 ) {     // 0除算
      nan_ = true;
      return( false );
    }

    if ( operator<( v ) ) { // 被除数 < 除数
      *r = *this;
      clear();
      return( true );
    }

    vector< Digit > ans; // 処理結果を格納するバッファ

    // vの最上位ビットが'1'になるように全体をシフト
    Digit msMem = v.number_[v.size() - 1];
    UnsignedBuff shiftNum = 0;
    while ( msMem < half ) {
      msMem <<= 1;
      shiftNum++;
    }
    v <<= shiftNum;
    operator<<=( shiftNum );

    // rに除数のサイズ分だけ被除数の上位桁を取り込む
    size_t s = size() - v.size();
    r->copy( *this, s, s + v.size() - 1 );
    if ( *r < v )
      r->push_lower( number_[--s] );

    while ( *r >= v ) {
      ans.push_back( r->divNDigit( v ) ); // (N+1)桁/N桁除算の結果を格納
      // 被除数>=除数になるまで新たな桁を取り込む
      while ( s > 0 ) {
        r->push_lower( number_[--s] );
        if ( *r >= v ) break;
        ans.push_back( 0 ); // 一回で条件を満たさなかったら結果に0を追加
      }
    }

    // 結果(ans)を取り込む
    number_.clear();
    for ( size_t i = ans.size() ; i > 0 ; --i )
      push_upper( ans[i-1] );

    // 余りは、シフトした分を元に戻す
    *r >>= shiftNum;

    return( true );
  }

  /*
    Unsigned::operator/= /=演算子の多重定義

    num : 除数

    戻り値 : 自分自身
  */
  Unsigned& Unsigned::operator/=( const Unsigned& num )
  {
    Unsigned r;
    div( num, &r );

    return( *this );
  }

  /*
    Unsigned::operator%= %=演算子の多重定義

    num : 除数

    戻り値 : 自分自身
  */
  Unsigned& Unsigned::operator%=( const Unsigned& num )
  {
    Unsigned u( *this );
    u.div( num, this );

    return( *this );
  }
}

namespace BigNum
{
  /*
    Unsigned::lBitShift 1ビット下位側へシフトしてそのビットを渡す

    戻り値 : 最下位のビット(1=True,0=False)
  */
  bool Unsigned::lBitShift()
  {
    bool ans = ( number_[0] & 1 ) > 0;
    operator>>=( 1 );

    return( ans );
  }

  /*
    Unsigned::pow べき乗計算

    べき乗計算には「繰り返し自乗法」を利用する

    exp : 指数

    戻り値 : 自分自身
  */
  Unsigned& Unsigned::pow( Unsigned exp )
  {
    if ( isNaN( exp ) ) return( *this );
    if ( *this == 0 ) {
      if ( exp == 0 ) nan_ = true;
      return( *this );
    }

    Unsigned curVal( *this ); // 現在の値を保持
    if ( ! exp.lBitShift() ) {
      clear();
      number_[0] = 1;
    }

    while ( exp != 0 ) {
      curVal *= curVal;
      if ( exp.lBitShift() )
        operator*=( curVal );
    }

    return( *this );
  }
}

/*
  Fact : 階乗計算(通常版)

  n : 階乗する数
  ans : 結果を保持する変数へのポインタ
*/
void Fact( BigNum::UnsignedBuff n, BigNum::Unsigned* ans )
{
  *ans = 1;
  for ( BigNum::UnsignedBuff u = 2 ; u <= n ; ++u )
    *ans *= u;
}

/*
  Fact2 階乗計算(乗算処理を半分に)

  n : 階乗する数
  ans : 結果を保持する変数へのポインタ
*/
void Fact2( BigNum::UnsignedBuff n, BigNum::Unsigned* ans )
{
  // 小さな値は先に計算してテーブル化
  BigNum::UnsignedBuff factNum[] = {
    //0, 1, 2, 3,  4,   5,   6,    7,     8,
    1, 1, 2, 6, 24, 120, 720, 5040, 40320,
    //     9,      10,       11,        12,
    362880, 3628800, 39916800, 479001600,
  };

  // 小さな値はテーブルから取得
  if ( n < sizeof( factNum ) / sizeof( factNum[0] ) ) {
    *ans = factNum[n];
    return;
  }

  // 乗数(初期値 = 中央値)を求める
  BigNum::Unsigned x( n );
  x >>= 1; x += 1;

  // 処理回数
  BigNum::Unsigned cnt( x );
  cnt -= ( ( n & 1 ) != 0 ) ? 1 : 2;

  *ans = x;  // 初期値 ( = 中央値 ) を代入
  x *= x; // x^2

  BigNum::Unsigned subNum( 1 ); // x^2 から減算する数
  while ( cnt > 0 ) {
    x -= subNum; // ( x + a )( x - a ) = x^2 - a^2 の計算
    *ans *= x;
    subNum += 2;
    cnt -= 1;
  }
}

/*
  OddFact : 奇数の列に対する二重階乗

  min : 数列の最小値
  max : 数列の最大値
  num : 結果を保持する変数へのポインタ
*/
void OddFact( BigNum::UnsignedBuff min, BigNum::UnsignedBuff max, BigNum::Unsigned* num )
{
  // 乗数(初期値 = 中央値)を求める
  BigNum::Unsigned n( ( max - min ) / 2 + min );

  BigNum::Unsigned cnt( n ); // 処理回数
  cnt -= min; cnt >>= 1;

  BigNum::Unsigned subNum;   // n^2 から減算する数

  if ( ( n & 1 ) == 1 ) {
    *num *= n;
    n *= n; // ( n + 2 )( n - 2 ) = n^2 - 4
    subNum = 4;
  } else {
    n *= n; // ( n + 3 )( n - 3 ) = n^2 - 9
    n -= 1;
    *num *= n;
    subNum = 8;
  }

  while ( cnt > 0 ) {
    n -= subNum; // ( x + a )( x - a ) = x^2 - a^2 の計算
    *num *= n;
    subNum += 8;
    cnt -= 1;
  }
}

/*
  Fact3 : 階乗計算(奇数列のみを乗算)

  n : 階乗する数
  ans : 結果を保持する変数へのポインタ
*/
void Fact3( BigNum::UnsignedBuff n, BigNum::Unsigned* ans )
{
  std::vector< BigNum::UnsignedBuff > odd; // 各奇数列の最大値
  BigNum::UnsignedBuff k = 0; // 2のべき乗の指数

  // 各奇数列の最大値だけを抽出
  while ( n >= 10 ) {
    odd.push_back( ( ( n & 1 ) != 0 ) ? n : n - 1 );
    n /= 2;
    k += n;
  }

  // 残った数列を先に処理
  *ans = 1;
  for ( BigNum::Unsigned i( 2 ) ; i <= n ; i++ )
    *ans *= i;

  // 奇数列の階乗計算
  BigNum::Unsigned oddNum( 1 );
  BigNum::UnsignedBuff min( 3 );
  for ( size_t i = odd.size() ; i > 0 ; i-- ) {
    OddFact( min, odd[i - 1], &oddNum );
    *ans *= oddNum;
    min = odd[i - 1] + 2;
  }

  *ans <<= k;
}

namespace BigNum
{
  /* 定数の定義 */

  // 1E+xx での最大値の桁数 - 1
  const size_t Unsigned::DIGIT_LEN10 = std::numeric_limits< Digit >::digits10;
  // 1E+xx での最大値
  const Digit Unsigned::DIGIT_MAX10 = std::pow( static_cast< Digit >( 10 ), static_cast< Digit >( DIGIT_LEN10 ) );

  /*
    StoI : 文字列から数値に変換する

    str : 対象文字列
    [ s, e ) : 変換開始・終了位置
  */
  UnsignedBuff StoI( const string& str, size_t s, size_t e )
  {
    UnsignedBuff ans = 0;

    while ( s < e ) {
      ans *= 10;
      ans += str[s++] - '0';
    }

    return( ans );
  }

  /*
    コンストラクタ(文字列から変換)

    s : 数値を表す文字列
  */
  Unsigned::Unsigned( const string& s )
    : nan_( false )
  {
    assert( sizeof( Digit ) * 2 <= sizeof( UnsignedBuff ) );

    push_upper( 0 );

    // Null 文字列の場合何もせずに終了
    if ( s.size() == 0 ) return;

    // 文字列中の全ての文字が 0-9 の間にあることを確認する
    for ( size_t i = 0 ; i < s.length() ; i++ ) {
      if ( s[i] < '0' || s[i] > '9' ) {
        nan_ = true;
        return;
      }
    }

    size_t l = s.length() % DIGIT_LEN10;

    if ( l > 0 )
      operator+=( StoI( s, 0, l ) );
    size_t cnt = s.length() / DIGIT_LEN10;

    for ( size_t i = 0 ; i < cnt ; i++ ) {
      operator*=( DIGIT_MAX10 );
      operator+=( StoI( s, i * DIGIT_LEN10 + l, ( i + 1 ) * DIGIT_LEN10 + l ) );
    }
  }
}