#919495 (C++17) No.502 階乗を計算するだけ

• 問題: No.502 階乗を計算するだけ
• ユーザー: tonegawa
• 提出日時: 2023-10-11 22:45:28
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: RE
• 実行時間: -
• コード長: 60,821 bytes
• コンパイル時間: 1,569 ms
• コンパイル使用メモリ: 140,440 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-13 22:30:43
• 合計ジャッジ時間: 3,015 ms
• ジャッジサーバーID （参考情報）: judge3 / judge6

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	2 ms; 5,376 KB
testcase_23	AC	2 ms; 5,376 KB
testcase_24	AC	3 ms; 5,376 KB
testcase_25	AC	2 ms; 5,376 KB
testcase_26	AC	3 ms; 5,376 KB
testcase_27	AC	3 ms; 5,376 KB
testcase_28	AC	2 ms; 5,376 KB
testcase_29	AC	3 ms; 5,376 KB
testcase_30	AC	3 ms; 5,376 KB
testcase_31	AC	3 ms; 5,376 KB
testcase_32	AC	3 ms; 5,376 KB
testcase_33	AC	2 ms; 5,376 KB
testcase_34	AC	3 ms; 5,376 KB
testcase_35	AC	3 ms; 5,376 KB
testcase_36	AC	2 ms; 5,376 KB
testcase_37	AC	3 ms; 5,376 KB
testcase_38	AC	2 ms; 5,376 KB
testcase_39	AC	2 ms; 5,376 KB
testcase_40	AC	3 ms; 5,376 KB
testcase_41	RE	-
testcase_42	AC	2 ms; 5,376 KB
testcase_43	AC	2 ms; 5,376 KB
testcase_44	AC	2 ms; 5,376 KB
testcase_45	AC	2 ms; 5,376 KB
testcase_46	AC	2 ms; 5,376 KB
testcase_47	AC	2 ms; 5,376 KB
testcase_48	AC	2 ms; 5,376 KB
testcase_49	AC	2 ms; 5,376 KB
testcase_50	AC	2 ms; 5,376 KB
testcase_51	AC	2 ms; 5,376 KB

ソースコード

#line 1 ".lib/template.hpp"


#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<(int)sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}
void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

#line 1 ".lib/math/mod.hpp"


#line 6 ".lib/math/mod.hpp"
#include <type_traits>
#line 8 ".lib/math/mod.hpp"
#include <ostream>
#line 1 ".lib/math/minior/mod_base.hpp"


#line 4 ".lib/math/minior/mod_base.hpp"
// @param m `1 <= m`
constexpr long long safe_mod(long long x, long long m){
  x %= m;
  if (x < 0) x += m;
  return x;
}
struct barrett{
  unsigned int _m;
  unsigned long long im;
  explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1){}
  unsigned int umod()const{return _m;}
  unsigned int mul(unsigned int a, unsigned int b)const{
    unsigned long long z = a;
    z *= b;
#ifdef _MSC_VER
    unsigned long long x;
    _umul128(z, im, &x);
#else
    unsigned long long x = (unsigned long long)(((unsigned __int128)(z) * im) >> 64);
#endif
    unsigned long long y = x * _m;
    return (unsigned int)(z - y + (z < y ? _m : 0));
  }
};
// @param n `0 <= n`
// @param m `1 <= m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m){
  if(m == 1) return 0;
  unsigned int _m = (unsigned int)(m);
  unsigned long long r = 1;
  unsigned long long y = safe_mod(x, m);
  while(n){
    if (n & 1) r = (r * y) % _m;
    y = (y * y) % _m;
    n >>= 1;
  }
  return r;
}
constexpr bool is_prime_constexpr(int n) {
  if (n <= 1) return false;
  if (n == 2 || n == 7 || n == 61) return true;
  if (n % 2 == 0) return false;
  long long d = n - 1;
  while (d % 2 == 0) d /= 2;
  constexpr long long bases[3] = {2, 7, 61};
  for(long long a : bases){
    long long t = d;
    long long y = pow_mod_constexpr(a, t, n);
    while(t != n - 1 && y != 1 && y != n - 1){
      y = y * y % n;
      t <<= 1;
    }
    if(y != n - 1 && t % 2 == 0){
      return false;
    }
  }
  return true;
}
template<int n>
constexpr bool is_prime = is_prime_constexpr(n);

constexpr int primitive_root_constexpr(int m){
  if(m == 2) return 1;
  if(m == 167772161) return 3;
  if(m == 469762049) return 3;
  if(m == 754974721) return 11;
  if(m == 998244353) return 3;
  int divs[20] = {};
  divs[0] = 2;
  int cnt = 1;
  int x = (m - 1) / 2;
  while (x % 2 == 0) x /= 2;
  for(int i = 3; (long long)(i)*i <= x; i += 2){
    if(x % i == 0){
      divs[cnt++] = i;
      while(x % i == 0){
        x /= i;
      }
    }
  }
  if(x > 1) divs[cnt++] = x;
  for(int g = 2;; g++){
    bool ok = true;
    for(int i = 0; i < cnt; i++){
      if(pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1){
        ok = false;
        break;
      }
    }
    if(ok)return g;
  }
}
template <int m>
constexpr int primitive_root = primitive_root_constexpr(m);

int ceil_pow2(int n){
  int x = 0;
  while ((1U << x) < (unsigned int)(n)) x++;
  return x;
}
int bsf(unsigned int n){
  return __builtin_ctz(n);
}
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b){
  a = safe_mod(a, b);
  if(a == 0) return {b, 0};
  long long s = b, t = a;
  long long m0 = 0, m1 = 1;
  while (t){
    long long u = s / t;
    s -= t * u;
    m0 -= m1 * u;
    auto tmp = s;
    s = t;
    t = tmp;
    tmp = m0;
    m0 = m1;
    m1 = tmp;
  }
  if(m0 < 0) m0 += b / s;
  return {s, m0};
}


#line 13 ".lib/math/mod.hpp"

template<int m>
long long modpow(long long a, long long b){
  assert(0 <= b);
  assert(0 < m);
  a = safe_mod(a, m);
  long long ret = 1;
  while(b){
    if(b & 1) ret = (ret * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return ret;
}
// @param 0 <= b, 0 < m
long long modpow(long long a, long long b, int m){
  assert(0 <= b);
  assert(0 < m);
  a = safe_mod(a, m);
  long long ret = 1;
  while(b){
    if(b & 1) ret = (ret * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return ret;
}

struct modint_base {};
struct static_modint_base : modint_base {};

template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : static_modint_base{
  using mint = static_modint;
public:
  static constexpr int mod(){return m;}
  static mint raw(int v) {
    mint x;
    x._v = v;
    return x;
  }
  static_modint(): _v(0){}
  template <class T>
  static_modint(T v){
    long long x = v % (long long)umod();
    if (x < 0) x += umod();
    _v = x;
  }
  unsigned int val()const{return _v;}
  mint& operator++(){
    _v++;
    if (_v == umod()) _v = 0;
    return *this;
  }
  mint& operator--(){
    if (_v == 0) _v = umod();
    _v--;
    return *this;
  }
  mint operator++(int){
    mint result = *this;
    ++*this;
    return result;
  }
  mint operator--(int){
    mint result = *this;
    --*this;
    return result;
  }
  mint& operator+=(const mint& rhs){
    _v += rhs._v;
    if (_v >= umod()) _v -= umod();
    return *this;
  }
  mint& operator-=(const mint& rhs){
    _v -= rhs._v;
    if (_v >= umod()) _v += umod();
    return *this;
  }
  mint& operator*=(const mint& rhs){
    unsigned long long z = _v;
    z *= rhs._v;
    _v = (unsigned int)(z % umod());
    return *this;
  }
  mint& operator/=(const mint& rhs){return *this = *this * rhs.inv();}
  mint operator+()const{return *this;}
  mint operator-()const{return mint() - *this;}
  mint pow(long long n)const{
    assert(0 <= n);
    mint x = *this, r = 1;
    while(n){
      if (n & 1) r *= x;
      x *= x;
      n >>= 1;
    }
    return r;
  }
  mint inv()const{
    if(prime){
      assert(_v);
      return pow(umod() - 2);
    }else{
      auto eg = inv_gcd(_v, m);
      assert(eg.first == 1);
      return eg.second;
    }
  }
  friend mint operator+(const mint& lhs, const mint& rhs){return mint(lhs) += rhs;}
  friend mint operator-(const mint& lhs, const mint& rhs){return mint(lhs) -= rhs;}
  friend mint operator*(const mint& lhs, const mint& rhs){return mint(lhs) *= rhs;}
  friend mint operator/(const mint& lhs, const mint& rhs){return mint(lhs) /= rhs;}
  friend bool operator==(const mint& lhs, const mint& rhs){return lhs._v == rhs._v;}
  friend bool operator!=(const mint& lhs, const mint& rhs){return lhs._v != rhs._v;}
private:
  unsigned int _v;
  static constexpr unsigned int umod(){return m;}
  static constexpr bool prime = is_prime<m>;
};

template<int id> 
struct dynamic_modint : modint_base{
  using mint = dynamic_modint;
public:
  static int mod(){return (int)(bt.umod());}
  static void set_mod(int m){
    assert(1 <= m);
    bt = barrett(m);
  }
  static mint raw(int v){
    mint x;
    x._v = v;
    return x;
  }
  dynamic_modint(): _v(0){}
  template <class T>
  dynamic_modint(T v){
    long long x = v % (long long)(mod());
    if (x < 0) x += mod();
    _v = x;
  }
  unsigned int val()const{return _v;}
  mint& operator++(){
    _v++;
    if(_v == umod()) _v = 0;
    return *this;
  }
  mint& operator--(){
    if (_v == 0) _v = umod();
    _v--;
    return *this;
  }
  mint operator++(int){
    mint result = *this;
    ++*this;
    return result;
  }
  mint operator--(int){
    mint result = *this;
    --*this;
    return result;
  }
  mint& operator+=(const mint& rhs){
    _v += rhs._v;
    if(_v >= umod()) _v -= umod();
    return *this;
  }
  mint& operator-=(const mint& rhs){
    _v += mod() - rhs._v;
    if(_v >= umod()) _v -= umod();
    return *this;
  }
  mint& operator*=(const mint& rhs){
    _v = bt.mul(_v, rhs._v);
    return *this;
  }
  mint& operator/=(const mint& rhs){return *this = *this * rhs.inv();}
  mint operator+()const{return *this;}
  mint operator-()const{return mint() - *this;}
  mint pow(long long n)const{
    assert(0 <= n);
    mint x = *this, r = 1;
    while(n){
      if (n & 1) r *= x;
      x *= x;
      n >>= 1;
    }
    return r;
  }
  mint inv()const{
    auto eg = inv_gcd(_v, mod());
    assert(eg.first == 1);
    return eg.second;
  }
  friend mint operator+(const mint& lhs, const mint& rhs){return mint(lhs) += rhs;}
  friend mint operator-(const mint& lhs, const mint& rhs){return mint(lhs) -= rhs;}
  friend mint operator*(const mint& lhs, const mint& rhs){return mint(lhs) *= rhs;}
  friend mint operator/(const mint& lhs, const mint& rhs){return mint(lhs) /= rhs;}
  friend bool operator==(const mint& lhs, const mint& rhs){return lhs._v == rhs._v;}
  friend bool operator!=(const mint& lhs, const mint& rhs){return lhs._v != rhs._v;}
private:
  unsigned int _v;
  static barrett bt;
  static unsigned int umod(){return bt.umod();}
};
template <int id>
barrett dynamic_modint<id>::bt(998244353);
using modint = dynamic_modint<-1>;

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
template <class T>
using is_modint = std::is_base_of<modint_base, T>;
template <class T>
using is_modint_t = std::enable_if_t<is_modint<T>::value>;
template <class T>
using is_static_modint = std::is_base_of<static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
template<int m>
std::ostream &operator<<(std::ostream &dest, const static_modint<m> &a){
  dest << a.val();
  return dest;
}
template<int id>
std::ostream &operator<<(std::ostream &dest, const dynamic_modint<id> &a){
  dest << a.val();
  return dest;
}

// 0 <= n < m <= int_max
// 前処理 O(n + log(m))
// 各種計算 O(1)
// 変数 <= n
template<typename mint, is_modint<mint>* = nullptr>
struct modcomb{
private:
  int n;
  std::vector<mint> f, i, fi;
  void init(int _n){
    assert(0 <= _n && _n < mint::mod());
    if(_n < f.size()) return;
    n = _n;
    f.resize(n + 1), i.resize(n + 1), fi.resize(n + 1);
    f[0] = fi[0] = mint(1);
    if(n) f[1] = fi[1] = i[1] = mint(1);
    for(int j = 2; j <= n; j++) f[j] = f[j - 1] * j;
    fi[n] = f[n].inv();
    for(int j = n; j >= 2; j--){
      fi[j - 1] = fi[j] * j;
      i[j] = f[j - 1] * fi[j];
    }
  }
public:
  modcomb(): n(-1){}
  modcomb(int _n){
    init(_n);
  }
  void recalc(int _n){
    init(std::min(mint::mod() - 1, 1 << ceil_pow2(_n)));
  }
  mint comb(int a, int b){
    if((a < 0) || (b < 0) || (a < b)) return 0;
    return f[a] * fi[a - b] * fi[b];
  }
  mint perm(int a, int b){
    if((a < 0) || (b < 0) || (a < b)) return 0;
    return f[a] * fi[a - b];
  }
  mint fac(int x){
    assert(0 <= x && x <= n);
    return f[x];
  }
  mint inv(int x){
    assert(0 < x && x <= n);
    return i[x];
  }
  mint finv(int x){
    assert(0 <= x && x <= n);
    return fi[x];
  }
};
template<typename mint, is_modint<mint>* = nullptr>
struct modpow_table{
  std::vector<mint> v;
  // x^maxkまで計算できる
  modpow_table(){}
  void init(int x, int maxk){
    v.resize(maxk + 1);
    v[0] = 1;
    for(int i = 1; i <= maxk; i++) v[i] = v[i - 1] * x;
  }
  mint pow(int k){
    assert(0 <= k && k < v.size());
    return v[k];
  }
};

#line 3 "b.cpp"
using mint = modint1000000007;

int umekomi_fact_size = 4545;
int umekomi_fact_interval = 220022;
std::vector<int> umekomi_fact{1,639758151,322768529,34696945,45433769,639151195,889626920,716082079,530659519,288860350,997761141,908183309,62041130,731111460,376902927,554968471,250819818,158738584,818474976,376047636,210663801,848443932,725815658,874972859,52455831,217547935,198803624,576121518,726622504,633778308,922746761,454394077,709040077,709696341,42688414,1191965,590308285,486130634,690059163,184071732,226170664,119663892,284186157,555254029,886262084,552281170,279228348,414989229,659977904,415232296,336990229,768174163,848371017,877764292,106175195,302595688,216583773,342455975,131189800,349910800,753494259,569544619,591400828,331408439,715835311,296533856,916669749,196282324,637208314,912606840,805426592,274058284,182877133,329398564,476455044,875895803,115108546,387070262,621283109,329018273,747999408,100020735,464194259,565254056,718308138,641783653,593704213,868833711,838623064,28155523,142961690,505198321,233658377,797840153,491773965,9336713,316721667,473352339,383038781,985278932,290103130,345886726,688888919,80247447,400160382,333855799,721544232,231535061,702278477,177759149,587895998,661546967,404012297,807977893,503968418,136598572,150304093,588754369,920065848,481258887,509949305,89675836,63161497,909736884,774073983,4143216,608914963,694673346,13934564,932079477,638961737,776155492,261343451,320295964,964154978,891629496,699176261,804673840,523272298,815897622,938271592,51568996,508139868,223635916,667986872,923132396,764257235,500017101,502317367,57811585,736278276,535141183,244332089,374533826,495608209,9341747,308344424,606746935,168651872,262851614,111241213,616585263,734328323,276128736,347518144,593263471,587256235,818777666,103891523,146561327,193103156,585885392,54526631,444848495,344350558,699449558,826570294,553861461,778446177,880742964,776443802,220407191,246745055,131201925,429623841,662969153,855622458,205281760,856411319,284089505,704309992,951706094,844972432,262135993,5702280,21968254,736749509,196668013,258366070,594275606,138946350,522062229,589542642,202198710,376363489,437136026,424283323,337711956,368880813,262359690,429717553,294502731,3314436,924757919,836174654,145486006,265274772,759966820,238910763,80325422,773890778,519323993,42606825,800234590,218338663,688215156,858273555,70253485,163811554,952526090,277756067,80582391,306956928,311396618,578610078,977918953,668940620,120961866,166819964,182581925,761428288,626051235,996490001,61212761,989724163,776073524,998751152,883511053,327924744,359541138,561139892,895275383,688132806,919786458,967819754,954764935,799191384,923973659,105317343,34380991,957344083,838326132,157471807,595666203,806668677,39210439,707361333,497912244,471241600,101248446,54928924,868867875,886459361,563058798,166603330,24346201,210301676,151702689,104826801,51179986,256972907,243365736,472404790,613076926,917886739,402618447,813452010,471696385,327979528,329972891,524719969,624025589,681006588,265701525,39026059,583519123,855565144,868926455,546073305,429431618,865472376,883155784,868853871,229877126,204406691,481048644,783770561,411278566,659190759,692026571,414746920,124010469,877939400,990777431,618658141,244723481,214737362,28761772,313769368,104285567,570967993,708579897,856131562,243702768,861590747,621915570,146634678,413925421,237971261,179432655,943283675,645349868,786777617,454178121,65281152,868227332,187287406,64948217,750592831,255453068,522893319,529003608,705955348,871552082,710990135,665333784,255448320,544576672,572295548,465220271,820109182,90374169,205566947,955369130,318806584,925414683,466007459,783734765,162764772,391638075,590163388,469905028,296655101,116473624,660914066,401221056,933003586,593182060,16604045,560582014,44311523,233593325,751764115,164766795,495980653,959394394,110005453,380655732,24744683,832008595,83700664,465258104,829807647,782110751,747879919,505962277,971812591,618317604,513984978,379604563,114035842,864985314,480650725,641866671,455377257,831316475,284542889,20873320,946680857,909009353,931596371,285917729,982804521,597682398,300904395,233732902,102936779,818799778,823874079,827843672,38514791,665958937,385949085,871381645,755579130,883883801,124812122,63905819,915105333,227023388,449584274,404494596,570568014,623663257,270971471,991793531,923343745,753221476,102923076,122800561,914443193,970848574,387294929,262153195,987507707,373845214,390965038,392875765,845254677,484592246,952955437,602391561,996537759,530778563,229376925,844139321,806168617,706285207,764676537,245761443,430489740,194421594,354911133,424164656,114051109,729434388,415089755,450473431,17736421,460262074,24097130,914673267,896052724,934627292,245359399,453683380,273419547,288684503,421240213,735483579,728259885,459664518,919653350,664980527,381566980,564693776,881232628,446288685,507019503,978397029,306309032,673600078,754090444,777737577,812039479,240080944,153416601,244417934,663282950,150184392,198674839,579878858,816005728,948094167,60678274,859381451,25943283,980510429,434377418,437335591,905538679,343032300,888681439,95714840,73318686,759785795,929061738,763178810,655494835,163154884,811675772,705346615,616956941,977443751,500766660,209650147,168491671,170697473,289825509,128520753,43190578,567615976,780480230,943812790,388283522,745203730,920796335,861037701,703380007,10221670,370759972,823386233,234753613,725275632,71710341,455277477,882986843,276122388,224137615,481988857,545959491,325098582,838318899,467989716,225455073,399155836,51886446,863580277,545116189,960538439,263058470,845510200,454921898,50141858,944997746,121891556,581089817,299336308,983663910,289444983,240498451,860256886,548972142,575352043,163874050,682124283,646422227,2754049,64512202,806838204,6368502,537206503,10189176,916432520,995925763,933471957,959082796,416078789,851369269,510858333,637823223,969277272,211129444,893434359,669167708,71879044,852849144,164546350,571327692,228157062,163438096,990746644,437822321,917363939,42382750,523899420,672724919,803681994,260186564,972833495,617258402,500052551,418914155,499029284,493735487,784444237,570188059,200725834,518074710,151277420,604375509,101229406,250957729,742957411,685931727,322685918,599967657,755010475,968395292,882133005,117916124,330624196,459888206,524015588,782428856,882071134,29829186,681549011,567523990,498057816,490349120,679223814,626233989,502442600,827247506,79727599,487300268,839412378,331983622,31756257,895099177,621664463,405007702,351059317,594664649,622584154,73230734,454407871,136493465,518336359,671764868,555790575,929373236,122538510,754601412,995954537,26234107,389608808,333418819,869443783,355761302,511395160,368563275,916852283,549214870,23102864,733314720,664209753,409711000,703652116,521981110,528562757,950317048,426526918,589204073,750118718,792173585,310182257,129803381,453416780,890873193,21375106,448324112,906873928,854608427,474638139,904390999,110295936,63299731,364825308,166718478,862755154,547344348,304609480,114331448,55328874,287865556,460033912,540711514,937639955,682842986,190942525,536721335,339456236,254764240,724752704,738812883,863710605,928034264,832340329,494429348,183923621,740888895,367111544,441553789,22965915,183671307,202429648,704403965,260287668,234807104,338977060,513217280,695396868,96824020,367019513,593844713,627928293,813638532,995897285,557777128,215378196,340048702,773658198,689411838,692007449,95552080,152683199,586388234,113012709,183768460,505264718,523560595,848232155,214317541,562368651,355947398,685519248,6729220,685824170,327631594,683548577,379148748,774772528,482617733,100294616,373467649,563059029,527352141,283798124,459319545,530253714,972314274,5862558,482981421,655589480,89672181,629647752,710924441,193761934,963407582,679942866,365221846,465896364,376413352,408605594,26826801,973289224,535173625,402902404,248411894,212212368,335791243,80474926,746867401,230973276,680297019,877791937,621699368,782506004,928125281,786577721,723489899,954638072,640624402,246283620,295324088,645883981,488129888,171515278,474976853,310230981,393822596,656963889,797363653,802926861,130526124,540317486,26520737,367589196,113755916,228060806,542804683,199150516,161410483,341011706,511960181,46512571,568348078,97758227,313849720,877666585,421512117,784503738,826115149,365056621,598344941,249461560,987039197,437398719,190374109,340531537,51215802,531104649,205228834,350066033,589038350,845975247,867978073,950223437,693145285,197470513,737159461,706689337,242053312,83116322,588183873,4440680,805592794,741606980,984132702,690343024,815223755,284973172,43638985,163838009,864932593,308230558,252348797,230849019,112807066,937314832,341643922,219839359,788064379,129585098,916141650,212325282,314249150,239283023,825256292,882102992,514966771,428884833,482781340,457505989,237078825,293841116,373624446,670514384,499711601,868033610,260138804,884706505,497519994,73234856,474068899,620976020,751528642,640407533,412594278,788586441,52110326,790116388,433450248,201715651,456583050,418914188,962606680,546638603,274232606,541145437,975180264,871097066,536059980,677062221,295848080,626783322,709665789,956323111,816406551,963586677,4980641,644494524,20179489,58060631,140851430,393707241,426167533,941448719,350649139,742559914,514256177,508112429,417150123,1494208,183590804,638072129,906716448,163858710,625579970,743495831,96473938,584346180,325033067,908337397,916322693,190654790,647740868,24188524,408513416,29483542,980269860,804989407,275911417,104006748,902389397,23260399,524386754,904231655,506748361,976053091,717679992,595606072,924369318,665621742,598121277,125235181,923265220,596483932,645446101,749273350,145234227,642346764,86235002,697130638,210383193,318889856,950961156,399168036,31344767,572229036,678351669,600907066,72538045,222534402,595074055,261397317,417385978,899852822,423307876,258202476,684114572,23450523,688201859,223036262,800073559,751592076,297498815,223808327,558955483,339553026,830020431,590133942,871218557,880426846,626036983,486023962,437123686,221267455,916834543,750850489,863190938,894366114,161839505,739083321,109344015,564418702,302025410,1827633,843358913,966591329,742312692,979569513,174294705,485488839,598410503,412239930,529651716,435690943,946048498,448228291,701542105,74342263,518050019,185323040,656206958,824945214,640803065,624413648,129101445,446764510,821962273,414098383,809109348,388090529,962970917,536477707,184154760,269532348,321319943,364453421,898680780,356280754,352171831,700030997,857915376,48149118,535644107,170204284,401628172,84685727,35461438,253980273,899418924,461624017,44770252,860175190,56883498,28362353,648885047,606954059,519492830,735406384,251514320,978007735,631848431,836545195,470049423,998896171,725956763,498933787,193505862,174438896,575764048,417159690,65440740,868839878,499816015,10488292,139429828,89595484,890311610,414922888,920865685,619890686,851834149,411772764,47138679,158545674,365967184,449398932,137278286,6764330,657957517,521550646,886534109,182127429,383971193,205589203,169538139,629019440,762293674,686746100,66703960,246848433,970242004,500170806,341214507,251111481,302414337,321175324,346144844,374618983,442532451,303630894,363026480,471559400,564040004,751178121,67337234,509718126,172895028,323076149,702358578,394811806,74006399,850080361,986169677,441888037,468463372,636680697,159992024,754954803,560121353,327588371,534863544,418896046,24113916,66565834,179541692,76554593,38925190,993471243,943359357,821277382,571000007,371679646,845710986,346533230,379742217,969776145,791080117,786106907,930930118,842750797,605307580,352495289,754475494,460419265,460236674,913981349,964573424,326972715,681520091,954481461,390535979,395278187,967488275,570009796,284277157,387462814,625571219,690869832,468835776,528398111,324380998,577125819,456378471,950150857,207883060,496285738,924623204,169662738,646704924,300072773,960902085,73713140,294620237,340946726,689916773,278971718,423160889,137430131,897492832,933218391,49224092,663133668,827287270,567522080,100897279,989667759,376378631,507615614,945008851,603625619,228715811,581759438,991009809,780314059,538823832,847169838,190516451,217291328,624637954,34569416,15542507,104382850,424997372,13540436,549588862,449932193,74054637,517625637,235583979,920887942,702106587,542044825,979613006,647322921,131082865,109757279,299868323,290760278,164983203,487642828,977450061,4070859,135478349,75993188,585738586,250304621,674911631,37332211,690924529,551400820,606380421,836573725,793230686,881362118,862187611,917991303,940981541,662400384,91607486,100340854,179210548,766938009,2369591,19032627,635924736,591927121,223891643,515527261,810760647,123554787,945803701,991335005,778486244,44663021,754376522,782622354,249545882,669394871,952417313,179105422,180020219,190432014,78468906,808914159,540479719,365647062,771641089,370852669,150366358,872007456,760431966,85687910,352795244,343203416,48508222,557077352,429728244,655990731,634646705,409290251,773325889,671290542,732589478,529394812,434781150,667558225,515879016,758123540,336577434,67213113,166827258,612585223,592223366,624254608,916649154,821772981,71038438,672098212,708886796,571277116,987348709,752126844,745872309,853207840,774040614,327789815,24069074,36207738,156084007,185920259,661691741,534391890,235518258,176768503,368554309,970556445,769271492,396850510,582311056,174493518,335891393,506217506,8612634,820857319,66391808,275424894,143226369,422810331,921250513,188503511,479825318,453431887,442638454,911965528,996916242,358990117,439313044,214370837,226598824,824686284,914518342,384334904,936674482,757353544,999258654,498683126,92235749,82170749,347304327,769076935,315739176,300727533,818876763,169516611,490837837,79784383,769251760,183739917,964834747,111021886,590356622,788126752,544939111,872543845,699875481,168465342,105360403,529030526,299390360,358046935,1646661,388981086,498104115,823060282,591673425,154470015,650145791,454324438,769957850,739137333,661020132,128125753,13533367,22007667,644213856,742745900,245526241,185528777,44719750,146886081,981680053,590492466,569619832,193047272,91697353,39130418,283973700,271890112,882549206,54113769,226431934,844382390,677589243,266539754,484248819,510315402,363497671,72577344,62948754,811671030,672684031,263384410,505992277,614673934,522162896,922105629,866863204,884390511,107154298,408709458,934647062,321855660,151970301,799137886,478483308,902249899,134348913,240517320,928070363,447083044,793834535,616797430,479052322,60198317,598995688,820004557,634287227,837742942,260594537,293961764,877566989,239566603,914051357,841237151,934597308,226645277,657220111,977985262,387768927,355186876,724888121,561269304,770435548,867382263,356569646,448156723,795621096,551373024,814121568,826859176,526792731,232763714,781335985,434629814,182967479,433643384,783037496,549858442,953831395,19671373,394386817,564564590,728064136,927213549,472554211,710146046,145704615,10256748,502699322,565222594,405732138,322755638,156882153,675343062,118352678,68603702,807785836,120445181,267408189,813437183,518341136,660072977,125340027,324447972,863112215,687606997,545746606,102730302,411132970,316653457,218693291,521703087,413291158,396714430,564656536,486659894,128369617,114598139,843475889,170392798,59819772,307324214,625015778,911909778,939223276,716941838,380864027,279993945,945870132,147206015,565758921,448568295,222679244,110634169,805116204,257009463,205475336,457051776,284713043,399883012,870968923,291479793,624913573,446398385,161793390,623741657,622173385,547322271,101422893,354787259,71503150,212225767,95640332,680916684,999093933,616298961,644960904,812687348,660428506,86736114,428993710,779185126,519511120,411062532,866615227,37486030,846815709,186696967,227363928,243914240,906525292,474697700,647555450,541897248,146250893,527313165,312869418,737138881,795038198,4209101,20955438,33126811,876278365,176269186,9626226,222926722,326679002,740491350,692163393,991431176,787360884,297218960,749952488,617960468,510952406,416599423,193891143,465511438,157684303,181501504,598598412,312692906,622881544,237028045,840140719,544954961,149273540,982650713,620313521,798107788,294525987,503519930,170153784,466609102,140909659,987478005,829338829,705098656,556928616,327123343,991713664,598877720,204354666,77530998,958233484,144410605,896065916,211165084,944505846,808446257,399666961,135369221,44079617,780913704,319750497,186524823,875446723,116999555,585700317,4519520,214523717,191569488,342885937,444654395,846437753,158912430,40359503,860111269,442720133,75547211,478152621,992958210,672963001,19829544,431653764,318385624,853868073,474924992,931456485,552558324,399182018,165430394,220842487,257852245,287958121,282691164,343823446,301959053,802745360,877058346,410717464,295420155,85427347,942815001,690961861,393784843,274689542,439680695,930496758,626123261,917329010,156269801,710867522,902133287,40996424,708916878,364307406,686662897,849406596,958677828,787625031,780513280,43161945,166936198,891600071,391420041,208181989,148170657,44391923,599410275,218657174,938406386,793446540,246090548,377420899,114303838,597261724,624463510,406071420,776166882,396157616,876886163,926480793,511751952,810294978,793800998,162572998,750947599,336650460,966099432,380864503,562375208,419443545,152109235,451092623,778803363,909059655,368862804,133604766,646855155,941461189,921289845,659455042,761515581,822459233,557693614,326368924,934464476,699789794,103394698,325782756,740769466,487646685,315674410,92109200,638501808,641678189,65084661,474085825,997583398,58306367,970665382,259635959,568784329,34821773,955237055,447602382,529550154,582051435,303650282,532282438,501787354,828996751,14261835,842990196,87811171,276023305,994480350,318313543,968596918,66228323,142759048,454786171,535626420,43735244,910787382,407316667,914107937,805309029,590670351,918262334,834511090,366422863,520566083,556946384,984800026,277724462,931851303,951800173,91382326,242939760,225655342,283557698,963956292,890738713,845240914,372464396,441876928,193824324,979670062,498039898,439267299,55838297,804320634,701427625,140575595,433554695,33771394,906352765,876709261,514060685,448804181,57505286,601049257,154492315,855457539,977004433,431413145,199756278,304149778,453130114,708446172,821466662,631464656,802290390,734545904,355464581,655206123,851642244,597549034,805517891,530994421,238234856,874919617,721741586,930089970,200305772,205756384,423343962,380546360,798074549,10054186,444172622,832358363,166349703,306430850,679198449,945346995,905900120,865611055,399098881,326168506,562271854,637667725,683925123,825936993,339446110,295464250,446296938,937246919,659578164,265864418,808992912,103940869,57252275,925701435,946818237,88033482,984085308,846405031,495627839,794989920,166616984,132118776,288661302,163595494,845703912,922880162,774730546,626265957,128815366,845006271,135019796,691294467,662748231,549820106,676259714,432224840,106849379,818195274,218143004,820114337,365524545,461538119,584169279,520049023,43237850,224604180,868786903,688571628,885284872,65753184,868122773,588269210,639502036,13369762,910643862,88157399,117677503,1331817,73410036,390515434,974306805,281833327,979592965,69221760,262493238,615949502,814678501,246515878,443101320,424849868,935400055,671904859,211469104,524448966,303513922,347899993,779830145,434333896,857454029,11306029,665172920,63159197,715510827,202120243,474897867,983025351,632650332,312383085,299322038,352424005,187170112,251484629,330707124,777981589,115117221,473540773,143891323,575047384,509263541,95092002,860873532,210340696,805291029,672966538,940646732,659433837,311560243,945697098,866409215,478535297,425527195,369007222,649341328,947029457,228778984,598994640,814934909,861046582,569911260,950914509,990036569,139328668,696783222,725442845,410356834,55578197,206939994,801146431,577929850,977807112,931240238,849031844,88428608,943110889,893715732,168476967,14647722,585837288,904126209,964897756,464308894,685062879,676513955,812958010,872192115,798180255,657191748,141915071,705058555,548048588,597029422,558571476,400743855,806969279,898120083,197723786,545929127,822018776,816300012,247542844,916531638,898237695,209228019,788968508,856385088,174290665,446505837,382011264,285906545,846514654,372165898,27811911,252430889,664026232,733495133,790984434,603358114,426319827,2747819,564935338,804281524,846828578,796849934,910484408,902337627,169678261,286458718,439356296,696909411,918968419,348960577,815694382,698408985,763506125,850855700,283295103,290868882,437364005,195897060,134079197,78951374,233881219,973349051,702060027,931140104,856808456,123969978,336997691,533580224,253634457,745980368,424451727,148449438,425950139,247964449,854952111,135974638,770005340,668656598,284956232,81445734,121239079,190341027,294080422,565855227,469882614,813106892,783925196,668372973,234915615,597519643,106950841,369258620,71003187,412607426,934405060,604834455,329901865,434573139,714377673,472389266,297165430,50072428,632969469,500778197,65511397,521946705,211945810,517997408,624852032,792269807,597755850,508885469,33259231,440821224,824312345,321933115,115889406,460826529,228305764,774377499,656899508,81768713,920920111,695100416,715320022,75396234,621169653,825885580,671400791,324939471,29039560,694379718,355150308,882281300,811536792,551707692,406657924,171813995,320497592,769792990,228927708,554889366,226351090,125324967,440638560,319320853,52209661,165097544,439293918,378219903,622097270,511477130,843696782,570365267,484257680,516351373,657633637,57063845,734269332,34771158,934925785,919106845,89535598,238580397,110552404,671867460,161306729,311994656,149579297,584330732,2754761,258765711,29009444,790855392,7316936,791142568,624426033,463152384,49746330,622724802,312824760,477196895,826830872,810485978,453149234,527874492,661631128,89157234,229518987,457249638,522825344,647919866,299711353,585359367,691964535,845744445,238117752,97491152,321577290,143622392,849407659,959124713,5988748,637665678,954007610,167446638,58452303,25259943,660980338,901858932,856912195,988923111,630766224,1029404,58419732,817516963,528609241,745273392,719490037,346621752,167529398,179479905,876021215,927451030,388026961,750593977,296747477,933199219,7699381,628918132,504292058,382986225,638253189,54643025,157721854,362931375,745982218,857886422,399267906,432578469,790442030,66796454,233434520,189231443,185079904,522797492,450024770,230249089,480670418,106061065,683477402,503629970,700525831,624339271,355890533,341242181,28226532,499863114,278560823,32554170,274319901,587423014,166198407,340143646,17932645,26820982,895231368,525734413,602126866,85149922,734864732,745179370,390384337,959265942,666945741,706096404,865755383,39199374,221770456,473682156,857735918,161462602,595585086,9068960,790148994,223336499,397189770,327630244,182726956,367170620,825650883,768316231,125379084,997107624,592797336,119085337,173142236,390675189,931372982,818018530,60931693,205468349,973840348,207734555,930599304,524923518,453515772,289811773,235651858,951054542,686049493,40900130,617145434,167444507,794887561,150185413,7537786,370576596,242641430,999524954,878418420,965549816,878262944,747539697,511740190,940451907,25204685,877725384,86879890,677462874,433888943,365061158,384157628,866276412,706367799,888281246,424916990,73705263,170286482,708267909,358549479,976455886,663392440,420167384,116769559,838309929,529886625,67870845,271012125,507792630,757948856,403166478,333208843,607817272,732531530,756717804,795602896,981267871,463444137,397590783,425416532,899039271,535794053,383605753,326636620,260259896,502594234,863351354,295151642,52258007,423722586,736955814,268375677,427398984,504540611,314041109,654733260,446037668,562413948,964159565,703394853,74997864,541990908,944563637,881511082,361816937,670599575,896995197,705333447,508750735,483219524,858831089,890432831,13353795,564963612,895952688,237358377,882398889,918898315,888811104,100217957,914682385,972577177,975270879,580024578,968337079,344588203,822231774,960678365,327532298,74119923,481786564,346455678,343274849,32221296,118464146,133783909,229488544,388298080,23787140,828310861,578289747,25317836,218697687,273125615,384573350,173264358,456644745,148744311,302038469,474396832,829169220,993146140,493503006,173859408,631186547,834810062,589198331,931466601,188077573,268564455,634048183,32263770,544069050,174706142,744751139,643787156,448154958,749980530,853508611,469806393,77628438,359194128,516782419,836809054,309000202,798482743,256302498,294188235,644446096,456410780,168831545,691312402,375365405,659177330,957344018,645802997,13993212,39596159,797574729,269642602,674902428,780315614,548067824,423241946,904542831,4722395,111832331,946733338,870763068,969186433,227309752,136611487,748303102,142524613,693938536,492790215,145937407,341306069,719360609,673396401,810237503,448050899,887041365,127344976,434057094,881557575,218466415,570219,283945813,643835006,573035837,690775986,618571690,27024992,930278777,274672672,412486060,820205487,603662144,334901046,202005796,632516632,732101567,205038653,479408571,329610459,218426959,332479696,469430600,808764519,468610115,206900309,921936882,137707846,634548525,285284015,163993910,730826103,631818231,947055654,643781458,392915911,947920253,483024314,655898871,832489888,157596941,317154957,809183297,833884080,330984011,506285501,626644000,242575237,850920274,341810114,379160501,697672253,109896831,960691777,322829167,797276439,133246954,218453778,487050261,184788801,692178842,24071375,865344109,198845530,215589467,366931322,463483835,589424076,29233772,932739089,467250109,955500485,970285018,501935898,684986803,704401832,756262989,487674930,950546275,384876956,761508698,485860679,25770792,696793890,964159214,616793750,956857471,448627150,512893957,214169949,786296550,567912407,301365040,129057677,842916341,63433453,259031122,476280395,120315098,751833064,210909439,118851774,999936016,891017550,210538513,719838265,875584448,492353690,59500601,185396417,407962001,642021145,273794019,499062012,127093961,365370972,81468410,740290187,116361465,668137885,920541865,223708799,984665138,907429311,229915530,729790035,758739887,235568417,684038510,805608517,563601745,604559023,549037217,783289776,828791650,388987197,842904790,148789760,522309130,46085829,896312257,646814952,908665417,3726614,850385644,337740639,120553337,706795588,843285497,400533879,184624194,549917412,36986430,748894119,919094720,262975771,282043509,303011462,707453953,315059282,720242363,485290979,31749538,110621889,373929063,629104442,57747335,131004669,873823599,968387140,812442653,902464437,835850554,343614454,386783334,727816214,519612990,875083614,302803725,293534588,626648073,413733901,184596688,112104784,647584891,144181476,815876348,236802449,530697772,383567817,332417628,743722084,47256494,911906236,923947390,438047887,101286883,859150606,314445819,652032686,360637147,74340617,141294369,875435890,886622205,563771677,898730808,39777020,594906453,168244145,226556383,464732930,483078759,264026777,531477936,525493335,681397977,647554960,220960723,312284843,409412253,500589888,940446090,475597390,661431121,196157420,520039174,662366865,69252517,917179329,373441727,252210595,608516397,957062550,606536197,222596799,101523426,144703610,879677512,972099166,854853009,206381064,681634558,416053125,343384958,890894333,938916365,941838709,710014995,453440954,112281794,247586627,285080864,718859000,869318454,335101238,323532019,547125134,906623505,842226519,714069344,262539522,424278486,228029897,772784901,232883643,943125711,637554387,834939166,540708126,605592962,74042370,336836709,930745120,146076734,198621934,15695579,901281674,560654301,31201681,313522878,407100260,85015566,539969632,876062155,357645100,863636301,532765546,821122710,213492937,623912683,400011752,888791616,553817918,200322945,456811426,442328991,290045496,422319531,903442123,728977105,741215585,654764607,636306634,915571890,337002841,424407394,604623838,599277633,889911774,146837307,809224464,357900781,866006313,363412816,870169178,302371023,560154356,869335552,91323602,157386573,727168345,82776210,473860945,838004807,35053904,815031101,260325674,363554578,75038610,44051875,729695197,566534702,673157818,939382338,142059381,316688953,631981980,69854201,63468944,389869712,675564355,25420789,249068509,543388385,957928782,472648380,559320462,490375753,426094859,112778336,151615466,623810820,760816794,637743850,928487430,408048924,838538483,561107143,934260906,520826870,240142763,692821240,94014703,280511767,275068313,824509335,285262999,4348409,382754992,445652560,868543276,980778423,813036470,696291274,218707347,245126358,471605478,308325865,771743747,422493863,481403642,863898713,856304180,738628765,980681687,284963994,948605806,666111614,533040259,289438056,240212900,316651103,64625779,1992844,62783421,968673430,968586834,883475674,895530967,287453637,729863628,259783430,497046523,142016919,983108625,395927429,18487246,412847738,210558761,992259779,639875559,20922561,328454392,645022973,149087379,876321744,9191200,565842717,513234330,210452011,31456939,153879043,56408351,874758180,366938213,541885262,223747204,103781833,710670728,708046790,307893196,806175190,387976300,16599830,754494135,253347413,985998343,267392527,593289334,217466810,678582601,169280099,28248936,251122908,900361969,595453337,468852043,488239897,261850051,784600933,5408464,240840086,195570979,706182828,132999241,581992783,974249762,884859262,689341129,629426803,595197240,343074438,865831603,49376425,97059667,594579024,343416800,650313103,884733761,254949308,579943645,777172248,719583787,161533000,22465557,291865786,101279494,404031366,797224305,885489599,784461262,927123328,628697419,902420185,303147107,569396314,895129982,92232653,964466847,697854608,313174783,392925509,112088212,352380163,536062540,813783350,296842277,331377261,929291819,392190906,113665502,382421970,298617374,489530616,616444009,144250774,321685256,674576812,303199127,452189008,982875499,495579421,190748784,983354319,766082677,865792482,346132859,890311491,875548175,694127899,720572838,19629340,543177561,806902399,375449301,144812368,302190058,174366340,941552665,923046839,638786408,234849535,181814176,69484522,93681485,790354604,686684079,134743561,441160848,549670627,76859986,806573970,862090476,465255105,456151119,788201743,830268241,360832680,517899215,764856179,511897513,752569554,425478071,635426107,47998127,103884087,364183906,299113255,183366299,634154155,136973472,716216632,861685064,877434488,45807501,488893369,622116401,746743771,897369535,29009136,265787148,603379225,860833491,774560604,226715754,368455872,461451597,613234161,801341004,452353485,956394689,538196542,920238263,739090709,294115465,814567010,990400254,173272607,824615386,83885972,728764513,997974862,310331237,315474311,82367995,277870557,418101646,292927738,820511455,915854609,215390423,223239576,640837565,564539804,604567681,546267077,563713185,531782907,753331328,266032105,521172730,259806913,254046534,374780597,160918211,276308754,676053127,337776777,679612694,285464982,189659345,238194817,489194392,667914508,514820822,689765758,702110138,80129725,663587998,46853701,476060643,210696833,129265174,960455581,942498725,646600816,406186405,489599347,444425045,909400477,75281802,542586490,869863911,334348569,541971108,759538272,44283087,773589813,690870985,348390012,896190800,427085427,621744445,899863552,186214387,54207386,534096388,911483591,209029479,653720621,893775251,392263893,220703335,312646871,115533540,935603492,254556815,607520526,727971117,226665349,145085650,668366211,769469911,294759968,324382377,630000237,261880806,796286069,5860142,34614207,164048295,224369315,37035199,205221078,519644056,410452455,110686051,753193882,344915213,627752820,231260164,807579894,895422381,950096956,477829423,565495139,154386973,657388870,574687833,220054679,413209849,96016711,818135567,380374603,247066850,790581185,788498355,353382843,665730851,496743210,774858040,809594946,513369628,623650185,63064950,783770690,443784026,616401291,936206021,637402608,138021546,553191241,59164645,455453444,200064177,854439835,628147335,42872065,748440853,638992402,342065460,132193436,485498698,775651237,687998492,553544171,804213485,856170092,168431709,649292046,546783530,852499397,737422992,849794354,469316576,117921067,117684460,330368380,751045838,545678998,14313289,225080214,474087031,327044563,675017055,69845313,376442387,632024505,942766134,489708295,654871248,602790643,377841844,334082534,543543984,942771975,12368889,384300398,620549853,16637691,440950099,989097915,544638131,225884949,668814568,846776252,906955602,882060624,79377593,106987946,208543069,873431167,233546801,651188078,68139380,95951644,669294143,594786749,639796083,21454709,226361430,364937297,384710955,926564890,732682787,304753359,594839396,95480422,656681506,151627017,77570878,222993566,755178156,999175982,569231180,114485988,201020727,926356964,344246465,766516479,369105263,893872665,684921116,194218626,656514846,343171649,370323481,549160351,598008213,215787132,804033619,879398561,145732262,845161196,478426968,756156317,926661599,106948976,297496743,862216109,845644969,239218783,148524666,905185994,1497115,945493098,683807630,801478201,131408555,470378608,460460358,425185914,261338396,43377296,699888885,609450244,610596629,711229527,738317187,443108241,37594488,308911630,690658430,567305961,103492784,169131903,81355428,469831781,478971170,655692970,537856555,400505753,700031766,426415806,339332186,291003865,696673860,877725250,120129167,488655308,537476323,52128934,942617676,646744792,32815809,731011151,159534029,875223799,888626320,27590025,284857906,146067378,761651449,331027057,963199921,633008033,137267635,487906076,505692597,305560167,357748790,395548263,569913101,740436789,369608566,23722929,277530384,851122227,694543631,261443089,538940989,78026567,605079861,22638149,394436561,369907480,381334056,422002820,960339551,526701555,389999282,425680664,794322646,961123080,634392113,330434232,746404602,105213346,26759314,339201030,809245713,699206137,21675218,924776694,546438047,380815302,869279047,71097048,157201443,102137735,946618047,839730453,525687395,139881331,127383309,219366367,261275276,656961525,223680251,815297261,955299376,813326148,113585006,860613579,217382897,793066117,114062359,672937585,817547198,381523503,456305531,423341125,851838607,28473694,439245033,706317381,723424556,337172888,719371553,362297165,36066262,984926631,832609539,699217182,801386893,317800092,926738613,430283465,264727122,454010873,255275814,347072278,363927490,662110126,297418432,619349695,486007932,938271455,78710513,778872359,250912604,622181594,350764907,839639685,834755557,694896849,905852486,187333121,49390757,781457438,356889832,948956286,45882931,609505242,859246159,877712711,998426335,80614139,329349465,863874782,355319798,617167283,890738641,450973607,530665311,955495034,975754247,253336406,869474991,739361109,451886454,750944860,984515460,739434,319534562,532257731,661477859,935276223,916867357,173147644,538934042,311580534,402823125,489026828,180389915,867877596,235332437,280781500,550257219,769834338,999407288,672629330,689336802,200665283,160818172,677284455,61586541,142252687,463497357,645465590,860574010,336437006,115427318,512582926,641997108,123597049,19681042,197899934,987583488,76260896,934375631,459152808,794959336,812651094,626353502,23205370,709932947,724294750,825716852,434748307,956089712,757385189,117403267,163103737,867889786,700368143,323250622,51706872,98188820,935013450,43204207,587831583,905202712,392831987,939622400,721654419,851142202,793277780,8168896,192737165,576155889,712393515,764033403,31427513,820648713,369350350,420003393,711755566,711588818,753186306,130169996,824220537,459266937,390077196,503794424,429703297,10933804,405395552,360373704,512357990,709820034,115249553,545007341,164522692,885911631,915956122,723534881,655148652,609554099,572140456,76963461,434776598,778531269,442937099,995869174,620857989,782450809,444695055,912154354,431411510,812258746,828945167,408979783,760461669,779264541,722995497,592645492,378582589,529038564,880742468,762455821,650436172,326935577,496455661,278670556,176560033,356879501,32614480,89248530,445480183,187961107,213703335,78057079,631800893,693705455,962620249,276440108,802335135,7544136,387681169,956719688,332702244,58196806,236654245,233120036,315703790,256064255,964255038,778707398,347934437,844516861,961621025,108363820,39679594,43796069,378098193,195661487,179665520,133365015,806653315,380109939,6607379,375660276,48533735,570829491,71976413,228237650,129627568,809806356,745689662,72140697,721871404,530702881,877036856,396078007,737035962,358558726,95020727,603406850,244614049,998770378,164358601,361686128,752409904,723429878,403559024,785588982,862201994,502165430,902323109,528906661,750581840,631762206,754191291,40612365,471584395,928364356,253236447,692938385,968245236,650599925,741450948,709375162,637293931,882518075,616286652,76447454,57309350,531778449,357081139,227059309,874067412,223107188,869649448,474718616,236177185,30747955,678665952,112789463,731654996,403614888,152307687,323139157,341379679,885536485,805399013,782696470,921835856,175854141,845497433,924216398,656785262,77259686,249742779,798611539,721367935,843684880,434201335,783237876,621247054,512724187,519152708,273944902,972800447,388512495,272265007,614744662,936953969,360087658,587493594,326380194,985345152,807272800,384533001,484758591,145110595,903605969,786298329,880321894,414537833,546789334,711941619,288424159,601945613,922500240,35819140,111003100,928938663,150195114,36801681,849671264,789181727,558086754,268797310,424679628,275650786,97484357,483960686,9279549,427420016,717382154,711454809,361137529,996419581,352012082,916924832,247403597,454720254,511013630,378155659,544471023,921009297,610170496,419757304,331816553,586105584,523013895,792357414,542359218,535093720,327331017,446147623,653833931,821170333,304838348,479875671,116818950,437420339,74926088,667044061,179481581,667666467,247204469,753963355,695558062,733634198,466114381,174934561,435938828,772756250,428581247,692158600,700495649,927349097,946466758,838673929,78481669,894677634,894981946,821476607,288610046,259658850,15531051,884565971,504571010,803543900,773486578,142423216,177011294,918021135,743515674,313085309,495181650,170499602,943530787,969802323,135721062,774348379,362104704,923285858,721213828,955293758,491766539,442195427,927889965,164039553,602616106,689771371,29572605,507187993,633935045,209046156,77684140,611320164,979397344,230918393,977738245,378194206,495385119,814155945,358115076,980848447,773201344,22047466,699423576,501996120,501018609,625229987,700825716,592386180,998097376,681590623,745019890,980513054,182324583,654237377,863012251,921771183,146323810,950634282,213199514,752427805,70913063,311947569,655441040,146365633,861506216,622290365,746137994,372311191,333562092,385543505,49023998,400286554,369839711,233025465,420760675,239944107,971656413,36071312,86409949,431511164,741194600,993818571,511207532,819181632,388902626,734639065,147244598,975394172,701202377,187733964,799044674,843382082,358595606,401037884,177936674,831278540,662319462,573500370,638307807,27154623,163863072,86202976,346145898,975716433,466936532,691135478,554326882,886639146,78275188,854548951,760830800,13456382,870903980,873680860,678010982,593746259,441491597,190008137,465848761,39799845,618158787,715218680,543513637,11057524,349412978,427323773,1679031,552287491,352469003,971851228,905216203,412530013,902355816,915127892,309489453,277834380,928690270,59381620,658710551,453240206,4499216,232018689,714098555,679785151,26372420,631680548,145408598,116806086,843529780,885536141,872198941,372748700,929674968,626356239,982142018,198610346,544684342,130560072,832990888,10740354,769654905,847869601,259596787,983980576,865685701,774734550,850060411,931730045,912943379,236647155,669800700,408961512,565914183,778803223,490875884,101230241,768040812,504601649,351402173,458110946,32373693,79124308,625911883,368064971,213837445,845865630,729333006,831213449,135008309,582143022,724126383,565374390,961747398,769035600,789251622,771868085,581527464,294385785,676552503,634213348,366264992,542946355,873749978,498831787,142239066,289831710,49058118,262576811,165561173,428173524,895840557,42824812,701463277,718979545,419001716,234650658,925529653,579678161,690695037,309983185,397297660,492171630,914514021,349498318,109653238,181426317,498442684,538345645,206330058,219942169,153635109,337147007,331345622,607857559,538401787,451347054,246165338,908534151,937169395,450872575,538361185,43610121,443400798,297658238,954096528,442498954,157366376,999464050,179279406,728618258,731116373,397105740,214284693,546885314,91193981,781177962,620147256,425593125,797701432,100415685,282254069,12825110,164870950,517638149,817276258,367510795,680690382,434002360,68477341,947265216,261143981,851898625,915639043,199853915,5019792,921328404,532438966,216075890,578702777,759062905,163248090,377936337,751987788,432698769,789397768,450425761,578745756,697298244,178178536,776068168,594279026,903264069,645984199,562729483,936306168,512280841,88525324,967266378,344731806,513345009,219301704,133998757,711898059,668539660,245112893,401920616,301052167,452032090,247799178,49274259,935965646,385312739,138565473,287383463,186365206,760911102,635758970,460926159,274038256,279918946,371751111,674814711,480327580,146825425,860705697,42904454,14809049,906870134,261751821,994228752,606699208,789176995,196933399,840285820,785027990,130825413,780298528,986072730,902993070,889219380,638211004,940961837,421547094,186431628,998232694,181590794,259737229,208903449,386031400,464575796,761864521,578859883,320847398,363985596,580617659,366106681,290665827,964930891,829501036,184004565,911909191,373848911,660326645,689432791,42160150,376759860,351335186,70586592,126689153,619314669,770824188,14255878,847267173,514060501,375249710,939067815,298379074,616040434,906938047,379199563,525212150,889047773,775802820,428175964,429481115,39496833,117107598,535787237,135800515,328894754,429379877,467407153,595565071,96228796,69990855,463423382,432907310,643856482,385045297,860748283,853485432,422090166,235519415,264256149,545330718,836332031,575728799,609456326,465644026,324277859,305794309,872191889,68233734,203288835,571293020,409259508,52290142,767520535,352012270,338275041,295584576,117343700,337182842,654986564,454999950,432714617,302837996,269723377,756923254,131780763,53891643,513140358,569270947,747658979,223744511,236418632,640795870,918253484,466690434,503295518,185774166,32417878,888071177,834470491,137302576,938447001,649299294,973469173,864698296,975124196,367175127,969452234,470290413,158414353,625318321,563653904,916847991,343135111,468605108,102207966,57689898,456332918,696176262,477428246,789201159,512732061,248066132,756147393,323918470,474063109,887570603,115771491,644249505,183658909,145551872,783775371,343682891,253261887,163903109,650232333,743400448,92171611,447619739,571409056,617655378,564972273,115438474,960082750,887757609,290809824,197703482,775660789,751045715,260966740,742595754,958081973,545311428,936636173,948466262,43096085,559546109,346434288,480977406,485550612,744515947,774171486,128022568,841637875,116785311,965239712,468092756,986144490,309304101,464825777,681806209,180097787,346836217,636586611,561133515,139283945,572353914,612556133,497611882,51133086,870857272,636029869,508723805,412770917,806583532,985288557,348665282,830172854,660011151,385393215,94922130,703573217,705080811,578600249,298692166,200984450,564363003,349772269,417085827,328397898,109602722,343108714,6206514,207034387,72196965,149746442,70998283,427159087,437833295,587935481,901742780,71441485,340888574,552864734,21964173,796163183,339244382,820811285,332707896,656983280,918151243,418622261,100272831,401625056,148662660,280206678,876961573,135233611,956915084,97981838,805435756,40061119,447754611,398864114,597372727,673352208,687810966,33634960,674201123,103303616,20682377,349401336,287541585,327851924,906651583,197246524,27637264,50915646,262132277,232676426,192557015,171981524,569182960,860332182,126631473,139601834,516355755,204890890,504561080,281685938,806379147,358868957,906446543,996209164,410607934,18946984,873399013,562176611,507988124,325813588,659399128,955210893,541481719,879873491,903437414,494373459,66453050,140272775,507909474,659744590,265749955,428485595,632022838,14777324,301815282,435123542,404048038,430097196,567549501,924762212,816768521,275211821,760165874,686564267,5112323,482412516,331746006,633901971,712707641,116916414,77548071,839204114,17240042,559932416,188056739,197254005,121429577,146701767,957373997,27005801,550368912,658828625,47850235,9765548,244245228,562856966,653651319,411350897,400578314,736785251,190160705,455516081,750688805,639631362,985326163,66480109,279499536,447951518,254315601,998301453,887647661,67312317,828310262,548475770,55311344,327636118,222958366,558326062,361008865,222057409,677533365,858715891,62486504,943569021,951166326,646126559,139531487,322822068,590397467,685259604,363959008,917152430,281380637,199960729,453959554,289388333,551786867,863579949,166455127,988212670,838252452,131598258,261163442,};

// max_length: 文字数制限
// max_lengthに収まるように埋め込む
template<typename mint>
void umekomi_factorial_mod(int max_length){
  int w = size(std::to_string(mint::mod())) + 1; // 1要素 + 区切り文字のサイズ
  int n = max_length / w, m = mint::mod() / n;
  std::cout << "int umekomi_fact_size = " << n << ';' << '\n';
  std::cout << "int umekomi_fact_interval = " << m << ';' << '\n';
  mint z = 1 % mint::mod();
  std::cout << "std::vector<int> umekomi_fact{" << z << ',';
  int next = m;
  for(int i = 1; i < mint::mod(); i++){
    z *= i;
    if(i == next){
      std::cout << z << ',';
      next += m;
    }
  }
  std::cout << "};" << '\n';
}

template<typename mint>
mint umekomi_factorial_mod_decode(long long n){
  if(n >= mint::mod()) return 0;
  int b = n / umekomi_fact_interval;
  assert(b < umekomi_fact_size);
  mint x = umekomi_fact[b];
  for(int i = b * umekomi_fact_interval + 1; i <= n; i++) x *= i;
  return x;
}

int main(){
  io_init();
  long long n;
  std::cin >> n;
  mint ans = umekomi_factorial_mod_decode<mint>(n);
  std::cout << ans << '\n';
}