QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#528445#9225. Fibonacci Fusionucup-team987#AC ✓2574ms67700kbC++1774.0kb2024-08-23 14:15:472024-08-23 14:15:47

Judging History

你现在查看的是最新测评结果

  • [2024-08-23 14:15:47]
  • 评测
  • 测评结果:AC
  • 用时:2574ms
  • 内存:67700kb
  • [2024-08-23 14:15:47]
  • 提交

answer

/**
 * date   : 2024-08-23 15:15:33
 * author : Nyaan
 */

#define NDEBUG

using namespace std;

// intrinstic
#include <immintrin.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tr2/dynamic_bitset>
#include <tuple>
#include <type_traits>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

// utility

namespace Nyaan {
using ll = long long;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;

template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<vector<T>>;
using vi = vector<int>;
using vl = vector<long long>;
using vd = V<double>;
using vs = V<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
template <typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

template <typename T, typename U>
struct P : pair<T, U> {
  template <typename... Args>
  constexpr P(Args... args) : pair<T, U>(args...) {}

  using pair<T, U>::first;
  using pair<T, U>::second;

  P &operator+=(const P &r) {
    first += r.first;
    second += r.second;
    return *this;
  }
  P &operator-=(const P &r) {
    first -= r.first;
    second -= r.second;
    return *this;
  }
  P &operator*=(const P &r) {
    first *= r.first;
    second *= r.second;
    return *this;
  }
  template <typename S>
  P &operator*=(const S &r) {
    first *= r, second *= r;
    return *this;
  }
  P operator+(const P &r) const { return P(*this) += r; }
  P operator-(const P &r) const { return P(*this) -= r; }
  P operator*(const P &r) const { return P(*this) *= r; }
  template <typename S>
  P operator*(const S &r) const {
    return P(*this) *= r;
  }
  P operator-() const { return P{-first, -second}; }
};

using pl = P<ll, ll>;
using pi = P<int, int>;
using vp = V<pl>;

constexpr int inf = 1001001001;
constexpr long long infLL = 4004004004004004004LL;

template <typename T>
int sz(const T &t) {
  return t.size();
}

template <typename T, typename U>
inline bool amin(T &x, U y) {
  return (y < x) ? (x = y, true) : false;
}
template <typename T, typename U>
inline bool amax(T &x, U y) {
  return (x < y) ? (x = y, true) : false;
}

template <typename T>
inline T Max(const vector<T> &v) {
  return *max_element(begin(v), end(v));
}
template <typename T>
inline T Min(const vector<T> &v) {
  return *min_element(begin(v), end(v));
}
template <typename T>
inline long long Sum(const vector<T> &v) {
  return accumulate(begin(v), end(v), 0LL);
}

template <typename T>
int lb(const vector<T> &v, const T &a) {
  return lower_bound(begin(v), end(v), a) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, const T &a) {
  return upper_bound(begin(v), end(v), a) - begin(v);
}

constexpr long long TEN(int n) {
  long long ret = 1, x = 10;
  for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1);
  return ret;
}

template <typename T, typename U>
pair<T, U> mkp(const T &t, const U &u) {
  return make_pair(t, u);
}

template <typename T>
vector<T> mkrui(const vector<T> &v, bool rev = false) {
  vector<T> ret(v.size() + 1);
  if (rev) {
    for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1];
  } else {
    for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];
  }
  return ret;
};

template <typename T>
vector<T> mkuni(const vector<T> &v) {
  vector<T> ret(v);
  sort(ret.begin(), ret.end());
  ret.erase(unique(ret.begin(), ret.end()), ret.end());
  return ret;
}

template <typename F>
vector<int> mkord(int N, F f) {
  vector<int> ord(N);
  iota(begin(ord), end(ord), 0);
  sort(begin(ord), end(ord), f);
  return ord;
}

template <typename T>
vector<int> mkinv(vector<T> &v) {
  int max_val = *max_element(begin(v), end(v));
  vector<int> inv(max_val + 1, -1);
  for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;
  return inv;
}

vector<int> mkiota(int n) {
  vector<int> ret(n);
  iota(begin(ret), end(ret), 0);
  return ret;
}

template <typename T>
T mkrev(const T &v) {
  T w{v};
  reverse(begin(w), end(w));
  return w;
}

template <typename T>
bool nxp(T &v) {
  return next_permutation(begin(v), end(v));
}

// 返り値の型は入力の T に依存
// i 要素目 : [0, a[i])
template <typename T>
vector<vector<T>> product(const vector<T> &a) {
  vector<vector<T>> ret;
  vector<T> v;
  auto dfs = [&](auto rc, int i) -> void {
    if (i == (int)a.size()) {
      ret.push_back(v);
      return;
    }
    for (int j = 0; j < a[i]; j++) v.push_back(j), rc(rc, i + 1), v.pop_back();
  };
  dfs(dfs, 0);
  return ret;
}

// F : function(void(T&)), mod を取る操作
// T : 整数型のときはオーバーフローに注意する
template <typename T>
T Power(T a, long long n, const T &I, const function<void(T &)> &f) {
  T res = I;
  for (; n; f(a = a * a), n >>= 1) {
    if (n & 1) f(res = res * a);
  }
  return res;
}
// T : 整数型のときはオーバーフローに注意する
template <typename T>
T Power(T a, long long n, const T &I = T{1}) {
  return Power(a, n, I, function<void(T &)>{[](T &) -> void {}});
}

template <typename T>
T Rev(const T &v) {
  T res = v;
  reverse(begin(res), end(res));
  return res;
}

template <typename T>
vector<T> Transpose(const vector<T> &v) {
  using U = typename T::value_type;
  if(v.empty()) return {};
  int H = v.size(), W = v[0].size();
  vector res(W, T(H, U{}));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      res[j][i] = v[i][j];
    }
  }
  return res;
}

template <typename T>
vector<T> Rotate(const vector<T> &v, int clockwise = true) {
  using U = typename T::value_type;
  int H = v.size(), W = v[0].size();
  vector res(W, T(H, U{}));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (clockwise) {
        res[W - 1 - j][i] = v[i][j];
      } else {
        res[j][H - 1 - i] = v[i][j];
      }
    }
  }
  return res;
}

}  // namespace Nyaan


// bit operation

namespace Nyaan {
__attribute__((target("popcnt"))) inline int popcnt(const u64 &a) {
  return __builtin_popcountll(a);
}
inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }
inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }
inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; }
template <typename T>
inline int gbit(const T &a, int i) {
  return (a >> i) & 1;
}
template <typename T>
inline void sbit(T &a, int i, bool b) {
  if (gbit(a, i) != b) a ^= T(1) << i;
}
constexpr long long PW(int n) { return 1LL << n; }
constexpr long long MSK(int n) { return (1LL << n) - 1; }
}  // namespace Nyaan


// inout

namespace Nyaan {

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.first << " " << p.second;
  return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  int s = (int)v.size();
  for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
  return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &x : v) is >> x;
  return is;
}

istream &operator>>(istream &is, __int128_t &x) {
  string S;
  is >> S;
  x = 0;
  int flag = 0;
  for (auto &c : S) {
    if (c == '-') {
      flag = true;
      continue;
    }
    x *= 10;
    x += c - '0';
  }
  if (flag) x = -x;
  return is;
}

istream &operator>>(istream &is, __uint128_t &x) {
  string S;
  is >> S;
  x = 0;
  for (auto &c : S) {
    x *= 10;
    x += c - '0';
  }
  return is;
}

ostream &operator<<(ostream &os, __int128_t x) {
  if (x == 0) return os << 0;
  if (x < 0) os << '-', x = -x;
  string S;
  while (x) S.push_back('0' + x % 10), x /= 10;
  reverse(begin(S), end(S));
  return os << S;
}
ostream &operator<<(ostream &os, __uint128_t x) {
  if (x == 0) return os << 0;
  string S;
  while (x) S.push_back('0' + x % 10), x /= 10;
  reverse(begin(S), end(S));
  return os << S;
}

void in() {}
template <typename T, class... U>
void in(T &t, U &...u) {
  cin >> t;
  in(u...);
}

void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u) {
  cout << t;
  if (sizeof...(u)) cout << sep;
  out(u...);
}

struct IoSetupNya {
  IoSetupNya() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(7);
  }
} iosetupnya;

}  // namespace Nyaan


// debug


#ifdef NyaanDebug
#define trc(...) (void(0))
#else
#define trc(...) (void(0))
#endif

#ifdef NyaanLocal
#define trc2(...) (void(0))
#else
#define trc2(...) (void(0))
#endif


// macro

#define each(x, v) for (auto&& x : v)
#define each2(x, y, v) for (auto&& [x, y] : v)
#define all(v) (v).begin(), (v).end()
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
#define reg(i, a, b) for (long long i = (a); i < (b); i++)
#define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--)
#define fi first
#define se second
#define ini(...)   \
  int __VA_ARGS__; \
  in(__VA_ARGS__)
#define inl(...)         \
  long long __VA_ARGS__; \
  in(__VA_ARGS__)
#define ins(...)      \
  string __VA_ARGS__; \
  in(__VA_ARGS__)
#define in2(s, t)                           \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i]);                         \
  }
#define in3(s, t, u)                        \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i], u[i]);                   \
  }
#define in4(s, t, u, v)                     \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i], u[i], v[i]);             \
  }
#define die(...)             \
  do {                       \
    Nyaan::out(__VA_ARGS__); \
    return;                  \
  } while (0)


namespace Nyaan {
void solve();
}
int main() { Nyaan::solve(); }


//



using namespace std;

struct Timer {
  chrono::high_resolution_clock::time_point st;

  Timer() { reset(); }
  void reset() { st = chrono::high_resolution_clock::now(); }

  long long elapsed() {
    auto ed = chrono::high_resolution_clock::now();
    return chrono::duration_cast<chrono::milliseconds>(ed - st).count();
  }
  long long operator()() { return elapsed(); }
};


//



using namespace std;




using namespace std;

namespace internal {
template <typename T>
using is_broadly_integral =
    typename conditional_t<is_integral_v<T> || is_same_v<T, __int128_t> ||
                               is_same_v<T, __uint128_t>,
                           true_type, false_type>::type;

template <typename T>
using is_broadly_signed =
    typename conditional_t<is_signed_v<T> || is_same_v<T, __int128_t>,
                           true_type, false_type>::type;

template <typename T>
using is_broadly_unsigned =
    typename conditional_t<is_unsigned_v<T> || is_same_v<T, __uint128_t>,
                           true_type, false_type>::type;

#define ENABLE_VALUE(x) \
  template <typename T> \
  constexpr bool x##_v = x<T>::value;

ENABLE_VALUE(is_broadly_integral);
ENABLE_VALUE(is_broadly_signed);
ENABLE_VALUE(is_broadly_unsigned);
#undef ENABLE_VALUE

#define ENABLE_HAS_TYPE(var)                                   \
  template <class, class = void>                               \
  struct has_##var : false_type {};                            \
  template <class T>                                           \
  struct has_##var<T, void_t<typename T::var>> : true_type {}; \
  template <class T>                                           \
  constexpr auto has_##var##_v = has_##var<T>::value;

#define ENABLE_HAS_VAR(var)                                     \
  template <class, class = void>                                \
  struct has_##var : false_type {};                             \
  template <class T>                                            \
  struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \
  template <class T>                                            \
  constexpr auto has_##var##_v = has_##var<T>::value;

}  // namespace internal




template <uint32_t mod>
struct LazyMontgomeryModInt {
  using mint = LazyMontgomeryModInt;
  using i32 = int32_t;
  using u32 = uint32_t;
  using u64 = uint64_t;

  static constexpr u32 get_r() {
    u32 ret = mod;
    for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
    return ret;
  }

  static constexpr u32 r = get_r();
  static constexpr u32 n2 = -u64(mod) % mod;
  static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
  static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
  static_assert(r * mod == 1, "this code has bugs.");

  u32 a;

  constexpr LazyMontgomeryModInt() : a(0) {}
  constexpr LazyMontgomeryModInt(const int64_t &b)
      : a(reduce(u64(b % mod + mod) * n2)){};

  static constexpr u32 reduce(const u64 &b) {
    return (b + u64(u32(b) * u32(-r)) * mod) >> 32;
  }

  constexpr mint &operator+=(const mint &b) {
    if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
    return *this;
  }

  constexpr mint &operator-=(const mint &b) {
    if (i32(a -= b.a) < 0) a += 2 * mod;
    return *this;
  }

  constexpr mint &operator*=(const mint &b) {
    a = reduce(u64(a) * b.a);
    return *this;
  }

  constexpr mint &operator/=(const mint &b) {
    *this *= b.inverse();
    return *this;
  }

  constexpr mint operator+(const mint &b) const { return mint(*this) += b; }
  constexpr mint operator-(const mint &b) const { return mint(*this) -= b; }
  constexpr mint operator*(const mint &b) const { return mint(*this) *= b; }
  constexpr mint operator/(const mint &b) const { return mint(*this) /= b; }
  constexpr bool operator==(const mint &b) const {
    return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
  }
  constexpr bool operator!=(const mint &b) const {
    return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
  }
  constexpr mint operator-() const { return mint() - mint(*this); }
  constexpr mint operator+() const { return mint(*this); }

  constexpr mint pow(u64 n) const {
    mint ret(1), mul(*this);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  constexpr mint inverse() const {
    int x = get(), y = mod, u = 1, v = 0, t = 0, tmp = 0;
    while (y > 0) {
      t = x / y;
      x -= t * y, u -= t * v;
      tmp = x, x = y, y = tmp;
      tmp = u, u = v, v = tmp;
    }
    return mint{u};
  }

  friend ostream &operator<<(ostream &os, const mint &b) {
    return os << b.get();
  }

  friend istream &operator>>(istream &is, mint &b) {
    int64_t t;
    is >> t;
    b = LazyMontgomeryModInt<mod>(t);
    return (is);
  }

  constexpr u32 get() const {
    u32 ret = reduce(a);
    return ret >= mod ? ret - mod : ret;
  }

  static constexpr u32 get_mod() { return mod; }
};






__attribute__((target("sse4.2"))) inline __m128i my128_mullo_epu32(
    const __m128i &a, const __m128i &b) {
  return _mm_mullo_epi32(a, b);
}

__attribute__((target("sse4.2"))) inline __m128i my128_mulhi_epu32(
    const __m128i &a, const __m128i &b) {
  __m128i a13 = _mm_shuffle_epi32(a, 0xF5);
  __m128i b13 = _mm_shuffle_epi32(b, 0xF5);
  __m128i prod02 = _mm_mul_epu32(a, b);
  __m128i prod13 = _mm_mul_epu32(a13, b13);
  __m128i prod = _mm_unpackhi_epi64(_mm_unpacklo_epi32(prod02, prod13),
                                    _mm_unpackhi_epi32(prod02, prod13));
  return prod;
}

__attribute__((target("sse4.2"))) inline __m128i montgomery_mul_128(
    const __m128i &a, const __m128i &b, const __m128i &r, const __m128i &m1) {
  return _mm_sub_epi32(
      _mm_add_epi32(my128_mulhi_epu32(a, b), m1),
      my128_mulhi_epu32(my128_mullo_epu32(my128_mullo_epu32(a, b), r), m1));
}

__attribute__((target("sse4.2"))) inline __m128i montgomery_add_128(
    const __m128i &a, const __m128i &b, const __m128i &m2, const __m128i &m0) {
  __m128i ret = _mm_sub_epi32(_mm_add_epi32(a, b), m2);
  return _mm_add_epi32(_mm_and_si128(_mm_cmpgt_epi32(m0, ret), m2), ret);
}

__attribute__((target("sse4.2"))) inline __m128i montgomery_sub_128(
    const __m128i &a, const __m128i &b, const __m128i &m2, const __m128i &m0) {
  __m128i ret = _mm_sub_epi32(a, b);
  return _mm_add_epi32(_mm_and_si128(_mm_cmpgt_epi32(m0, ret), m2), ret);
}

__attribute__((target("avx2"))) inline __m256i my256_mullo_epu32(
    const __m256i &a, const __m256i &b) {
  return _mm256_mullo_epi32(a, b);
}

__attribute__((target("avx2"))) inline __m256i my256_mulhi_epu32(
    const __m256i &a, const __m256i &b) {
  __m256i a13 = _mm256_shuffle_epi32(a, 0xF5);
  __m256i b13 = _mm256_shuffle_epi32(b, 0xF5);
  __m256i prod02 = _mm256_mul_epu32(a, b);
  __m256i prod13 = _mm256_mul_epu32(a13, b13);
  __m256i prod = _mm256_unpackhi_epi64(_mm256_unpacklo_epi32(prod02, prod13),
                                       _mm256_unpackhi_epi32(prod02, prod13));
  return prod;
}

__attribute__((target("avx2"))) inline __m256i montgomery_mul_256(
    const __m256i &a, const __m256i &b, const __m256i &r, const __m256i &m1) {
  return _mm256_sub_epi32(
      _mm256_add_epi32(my256_mulhi_epu32(a, b), m1),
      my256_mulhi_epu32(my256_mullo_epu32(my256_mullo_epu32(a, b), r), m1));
}

__attribute__((target("avx2"))) inline __m256i montgomery_add_256(
    const __m256i &a, const __m256i &b, const __m256i &m2, const __m256i &m0) {
  __m256i ret = _mm256_sub_epi32(_mm256_add_epi32(a, b), m2);
  return _mm256_add_epi32(_mm256_and_si256(_mm256_cmpgt_epi32(m0, ret), m2),
                          ret);
}

__attribute__((target("avx2"))) inline __m256i montgomery_sub_256(
    const __m256i &a, const __m256i &b, const __m256i &m2, const __m256i &m0) {
  __m256i ret = _mm256_sub_epi32(a, b);
  return _mm256_add_epi32(_mm256_and_si256(_mm256_cmpgt_epi32(m0, ret), m2),
                          ret);
}

namespace ntt_inner {
using u64 = uint64_t;
constexpr uint32_t get_pr(uint32_t mod) {
  if (mod == 2) return 1;
  u64 ds[32] = {};
  int idx = 0;
  u64 m = mod - 1;
  for (u64 i = 2; i * i <= m; ++i) {
    if (m % i == 0) {
      ds[idx++] = i;
      while (m % i == 0) m /= i;
    }
  }
  if (m != 1) ds[idx++] = m;

  uint32_t pr = 2;
  while (1) {
    int flg = 1;
    for (int i = 0; i < idx; ++i) {
      u64 a = pr, b = (mod - 1) / ds[i], r = 1;
      while (b) {
        if (b & 1) r = r * a % mod;
        a = a * a % mod;
        b >>= 1;
      }
      if (r == 1) {
        flg = 0;
        break;
      }
    }
    if (flg == 1) break;
    ++pr;
  }
  return pr;
}

constexpr int SZ_FFT_BUF = 1 << 23;
uint32_t _buf1[SZ_FFT_BUF] __attribute__((aligned(64)));
uint32_t _buf2[SZ_FFT_BUF] __attribute__((aligned(64)));
}  // namespace ntt_inner

template <typename mint>
struct NTT {
  static constexpr uint32_t mod = mint::get_mod();
  static constexpr uint32_t pr = ntt_inner::get_pr(mint::get_mod());
  static constexpr int level = __builtin_ctzll(mod - 1);
  mint dw[level], dy[level];
  mint *buf1, *buf2;

  constexpr NTT() {
    setwy(level);
    union raw_cast {
      mint dat;
      uint32_t _;
    };
    buf1 = &(((raw_cast *)(ntt_inner::_buf1))->dat);
    buf2 = &(((raw_cast *)(ntt_inner::_buf2))->dat);
  }

  constexpr void setwy(int k) {
    mint w[level], y[level];
    w[k - 1] = mint(pr).pow((mod - 1) / (1 << k));
    y[k - 1] = w[k - 1].inverse();
    for (int i = k - 2; i > 0; --i)
      w[i] = w[i + 1] * w[i + 1], y[i] = y[i + 1] * y[i + 1];
    dw[0] = dy[0] = w[1] * w[1];
    dw[1] = w[1], dy[1] = y[1], dw[2] = w[2], dy[2] = y[2];
    for (int i = 3; i < k; ++i) {
      dw[i] = dw[i - 1] * y[i - 2] * w[i];
      dy[i] = dy[i - 1] * w[i - 2] * y[i];
    }
  }

  __attribute__((target("avx2"))) void ntt(mint *a, int n) {
    int k = n ? __builtin_ctz(n) : 0;
    if (k == 0) return;
    if (k == 1) {
      mint a1 = a[1];
      a[1] = a[0] - a[1];
      a[0] = a[0] + a1;
      return;
    }
    if (k & 1) {
      int v = 1 << (k - 1);
      if (v < 8) {
        for (int j = 0; j < v; ++j) {
          mint ajv = a[j + v];
          a[j + v] = a[j] - ajv;
          a[j] += ajv;
        }
      } else {
        const __m256i m0 = _mm256_set1_epi32(0);
        const __m256i m2 = _mm256_set1_epi32(mod + mod);
        int j0 = 0;
        int j1 = v;
        for (; j0 < v; j0 += 8, j1 += 8) {
          __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
          __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
          __m256i naj = montgomery_add_256(T0, T1, m2, m0);
          __m256i najv = montgomery_sub_256(T0, T1, m2, m0);
          _mm256_storeu_si256((__m256i *)(a + j0), naj);
          _mm256_storeu_si256((__m256i *)(a + j1), najv);
        }
      }
    }
    int u = 1 << (2 + (k & 1));
    int v = 1 << (k - 2 - (k & 1));
    mint one = mint(1);
    mint imag = dw[1];
    while (v) {
      if (v == 1) {
        mint ww = one, xx = one, wx = one;
        for (int jh = 0; jh < u;) {
          ww = xx * xx, wx = ww * xx;
          mint t0 = a[jh + 0], t1 = a[jh + 1] * xx;
          mint t2 = a[jh + 2] * ww, t3 = a[jh + 3] * wx;
          mint t0p2 = t0 + t2, t1p3 = t1 + t3;
          mint t0m2 = t0 - t2, t1m3 = (t1 - t3) * imag;
          a[jh + 0] = t0p2 + t1p3, a[jh + 1] = t0p2 - t1p3;
          a[jh + 2] = t0m2 + t1m3, a[jh + 3] = t0m2 - t1m3;
          xx *= dw[__builtin_ctz((jh += 4))];
        }
      } else if (v == 4) {
        const __m128i m0 = _mm_set1_epi32(0);
        const __m128i m1 = _mm_set1_epi32(mod);
        const __m128i m2 = _mm_set1_epi32(mod + mod);
        const __m128i r = _mm_set1_epi32(mint::r);
        const __m128i Imag = _mm_set1_epi32(imag.a);
        mint ww = one, xx = one, wx = one;
        for (int jh = 0; jh < u;) {
          if (jh == 0) {
            int j0 = 0;
            int j1 = v;
            int j2 = j1 + v;
            int j3 = j2 + v;
            int je = v;
            for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
              const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
              const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
              const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
              const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
              const __m128i T0P2 = montgomery_add_128(T0, T2, m2, m0);
              const __m128i T1P3 = montgomery_add_128(T1, T3, m2, m0);
              const __m128i T0M2 = montgomery_sub_128(T0, T2, m2, m0);
              const __m128i T1M3 = montgomery_mul_128(
                  montgomery_sub_128(T1, T3, m2, m0), Imag, r, m1);
              _mm_storeu_si128((__m128i *)(a + j0),
                               montgomery_add_128(T0P2, T1P3, m2, m0));
              _mm_storeu_si128((__m128i *)(a + j1),
                               montgomery_sub_128(T0P2, T1P3, m2, m0));
              _mm_storeu_si128((__m128i *)(a + j2),
                               montgomery_add_128(T0M2, T1M3, m2, m0));
              _mm_storeu_si128((__m128i *)(a + j3),
                               montgomery_sub_128(T0M2, T1M3, m2, m0));
            }
          } else {
            ww = xx * xx, wx = ww * xx;
            const __m128i WW = _mm_set1_epi32(ww.a);
            const __m128i WX = _mm_set1_epi32(wx.a);
            const __m128i XX = _mm_set1_epi32(xx.a);
            int j0 = jh * v;
            int j1 = j0 + v;
            int j2 = j1 + v;
            int j3 = j2 + v;
            int je = j1;
            for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
              const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
              const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
              const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
              const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
              const __m128i MT1 = montgomery_mul_128(T1, XX, r, m1);
              const __m128i MT2 = montgomery_mul_128(T2, WW, r, m1);
              const __m128i MT3 = montgomery_mul_128(T3, WX, r, m1);
              const __m128i T0P2 = montgomery_add_128(T0, MT2, m2, m0);
              const __m128i T1P3 = montgomery_add_128(MT1, MT3, m2, m0);
              const __m128i T0M2 = montgomery_sub_128(T0, MT2, m2, m0);
              const __m128i T1M3 = montgomery_mul_128(
                  montgomery_sub_128(MT1, MT3, m2, m0), Imag, r, m1);
              _mm_storeu_si128((__m128i *)(a + j0),
                               montgomery_add_128(T0P2, T1P3, m2, m0));
              _mm_storeu_si128((__m128i *)(a + j1),
                               montgomery_sub_128(T0P2, T1P3, m2, m0));
              _mm_storeu_si128((__m128i *)(a + j2),
                               montgomery_add_128(T0M2, T1M3, m2, m0));
              _mm_storeu_si128((__m128i *)(a + j3),
                               montgomery_sub_128(T0M2, T1M3, m2, m0));
            }
          }
          xx *= dw[__builtin_ctz((jh += 4))];
        }
      } else {
        const __m256i m0 = _mm256_set1_epi32(0);
        const __m256i m1 = _mm256_set1_epi32(mod);
        const __m256i m2 = _mm256_set1_epi32(mod + mod);
        const __m256i r = _mm256_set1_epi32(mint::r);
        const __m256i Imag = _mm256_set1_epi32(imag.a);
        mint ww = one, xx = one, wx = one;
        for (int jh = 0; jh < u;) {
          if (jh == 0) {
            int j0 = 0;
            int j1 = v;
            int j2 = j1 + v;
            int j3 = j2 + v;
            int je = v;
            for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
              const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
              const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
              const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
              const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
              const __m256i T0P2 = montgomery_add_256(T0, T2, m2, m0);
              const __m256i T1P3 = montgomery_add_256(T1, T3, m2, m0);
              const __m256i T0M2 = montgomery_sub_256(T0, T2, m2, m0);
              const __m256i T1M3 = montgomery_mul_256(
                  montgomery_sub_256(T1, T3, m2, m0), Imag, r, m1);
              _mm256_storeu_si256((__m256i *)(a + j0),
                                  montgomery_add_256(T0P2, T1P3, m2, m0));
              _mm256_storeu_si256((__m256i *)(a + j1),
                                  montgomery_sub_256(T0P2, T1P3, m2, m0));
              _mm256_storeu_si256((__m256i *)(a + j2),
                                  montgomery_add_256(T0M2, T1M3, m2, m0));
              _mm256_storeu_si256((__m256i *)(a + j3),
                                  montgomery_sub_256(T0M2, T1M3, m2, m0));
            }
          } else {
            ww = xx * xx, wx = ww * xx;
            const __m256i WW = _mm256_set1_epi32(ww.a);
            const __m256i WX = _mm256_set1_epi32(wx.a);
            const __m256i XX = _mm256_set1_epi32(xx.a);
            int j0 = jh * v;
            int j1 = j0 + v;
            int j2 = j1 + v;
            int j3 = j2 + v;
            int je = j1;
            for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
              const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
              const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
              const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
              const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
              const __m256i MT1 = montgomery_mul_256(T1, XX, r, m1);
              const __m256i MT2 = montgomery_mul_256(T2, WW, r, m1);
              const __m256i MT3 = montgomery_mul_256(T3, WX, r, m1);
              const __m256i T0P2 = montgomery_add_256(T0, MT2, m2, m0);
              const __m256i T1P3 = montgomery_add_256(MT1, MT3, m2, m0);
              const __m256i T0M2 = montgomery_sub_256(T0, MT2, m2, m0);
              const __m256i T1M3 = montgomery_mul_256(
                  montgomery_sub_256(MT1, MT3, m2, m0), Imag, r, m1);
              _mm256_storeu_si256((__m256i *)(a + j0),
                                  montgomery_add_256(T0P2, T1P3, m2, m0));
              _mm256_storeu_si256((__m256i *)(a + j1),
                                  montgomery_sub_256(T0P2, T1P3, m2, m0));
              _mm256_storeu_si256((__m256i *)(a + j2),
                                  montgomery_add_256(T0M2, T1M3, m2, m0));
              _mm256_storeu_si256((__m256i *)(a + j3),
                                  montgomery_sub_256(T0M2, T1M3, m2, m0));
            }
          }
          xx *= dw[__builtin_ctz((jh += 4))];
        }
      }
      u <<= 2;
      v >>= 2;
    }
  }

  __attribute__((target("avx2"))) void intt(mint *a, int n,
                                            int normalize = true) {
    int k = n ? __builtin_ctz(n) : 0;
    if (k == 0) return;
    if (k == 1) {
      mint a1 = a[1];
      a[1] = a[0] - a[1];
      a[0] = a[0] + a1;
      if (normalize) {
        a[0] *= mint(2).inverse();
        a[1] *= mint(2).inverse();
      }
      return;
    }
    int u = 1 << (k - 2);
    int v = 1;
    mint one = mint(1);
    mint imag = dy[1];
    while (u) {
      if (v == 1) {
        mint ww = one, xx = one, yy = one;
        u <<= 2;
        for (int jh = 0; jh < u;) {
          ww = xx * xx, yy = xx * imag;
          mint t0 = a[jh + 0], t1 = a[jh + 1];
          mint t2 = a[jh + 2], t3 = a[jh + 3];
          mint t0p1 = t0 + t1, t2p3 = t2 + t3;
          mint t0m1 = (t0 - t1) * xx, t2m3 = (t2 - t3) * yy;
          a[jh + 0] = t0p1 + t2p3, a[jh + 2] = (t0p1 - t2p3) * ww;
          a[jh + 1] = t0m1 + t2m3, a[jh + 3] = (t0m1 - t2m3) * ww;
          xx *= dy[__builtin_ctz(jh += 4)];
        }
      } else if (v == 4) {
        const __m128i m0 = _mm_set1_epi32(0);
        const __m128i m1 = _mm_set1_epi32(mod);
        const __m128i m2 = _mm_set1_epi32(mod + mod);
        const __m128i r = _mm_set1_epi32(mint::r);
        const __m128i Imag = _mm_set1_epi32(imag.a);
        mint ww = one, xx = one, yy = one;
        u <<= 2;
        for (int jh = 0; jh < u;) {
          if (jh == 0) {
            int j0 = 0;
            int j1 = v;
            int j2 = v + v;
            int j3 = j2 + v;
            for (; j0 < v; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
              const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
              const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
              const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
              const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
              const __m128i T0P1 = montgomery_add_128(T0, T1, m2, m0);
              const __m128i T2P3 = montgomery_add_128(T2, T3, m2, m0);
              const __m128i T0M1 = montgomery_sub_128(T0, T1, m2, m0);
              const __m128i T2M3 = montgomery_mul_128(
                  montgomery_sub_128(T2, T3, m2, m0), Imag, r, m1);
              _mm_storeu_si128((__m128i *)(a + j0),
                               montgomery_add_128(T0P1, T2P3, m2, m0));
              _mm_storeu_si128((__m128i *)(a + j2),
                               montgomery_sub_128(T0P1, T2P3, m2, m0));
              _mm_storeu_si128((__m128i *)(a + j1),
                               montgomery_add_128(T0M1, T2M3, m2, m0));
              _mm_storeu_si128((__m128i *)(a + j3),
                               montgomery_sub_128(T0M1, T2M3, m2, m0));
            }
          } else {
            ww = xx * xx, yy = xx * imag;
            const __m128i WW = _mm_set1_epi32(ww.a);
            const __m128i XX = _mm_set1_epi32(xx.a);
            const __m128i YY = _mm_set1_epi32(yy.a);
            int j0 = jh * v;
            int j1 = j0 + v;
            int j2 = j1 + v;
            int j3 = j2 + v;
            int je = j1;
            for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
              const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
              const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
              const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
              const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
              const __m128i T0P1 = montgomery_add_128(T0, T1, m2, m0);
              const __m128i T2P3 = montgomery_add_128(T2, T3, m2, m0);
              const __m128i T0M1 = montgomery_mul_128(
                  montgomery_sub_128(T0, T1, m2, m0), XX, r, m1);
              __m128i T2M3 = montgomery_mul_128(
                  montgomery_sub_128(T2, T3, m2, m0), YY, r, m1);
              _mm_storeu_si128((__m128i *)(a + j0),
                               montgomery_add_128(T0P1, T2P3, m2, m0));
              _mm_storeu_si128(
                  (__m128i *)(a + j2),
                  montgomery_mul_128(montgomery_sub_128(T0P1, T2P3, m2, m0), WW,
                                     r, m1));
              _mm_storeu_si128((__m128i *)(a + j1),
                               montgomery_add_128(T0M1, T2M3, m2, m0));
              _mm_storeu_si128(
                  (__m128i *)(a + j3),
                  montgomery_mul_128(montgomery_sub_128(T0M1, T2M3, m2, m0), WW,
                                     r, m1));
            }
          }
          xx *= dy[__builtin_ctz(jh += 4)];
        }
      } else {
        const __m256i m0 = _mm256_set1_epi32(0);
        const __m256i m1 = _mm256_set1_epi32(mod);
        const __m256i m2 = _mm256_set1_epi32(mod + mod);
        const __m256i r = _mm256_set1_epi32(mint::r);
        const __m256i Imag = _mm256_set1_epi32(imag.a);
        mint ww = one, xx = one, yy = one;
        u <<= 2;
        for (int jh = 0; jh < u;) {
          if (jh == 0) {
            int j0 = 0;
            int j1 = v;
            int j2 = v + v;
            int j3 = j2 + v;
            for (; j0 < v; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
              const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
              const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
              const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
              const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
              const __m256i T0P1 = montgomery_add_256(T0, T1, m2, m0);
              const __m256i T2P3 = montgomery_add_256(T2, T3, m2, m0);
              const __m256i T0M1 = montgomery_sub_256(T0, T1, m2, m0);
              const __m256i T2M3 = montgomery_mul_256(
                  montgomery_sub_256(T2, T3, m2, m0), Imag, r, m1);
              _mm256_storeu_si256((__m256i *)(a + j0),
                                  montgomery_add_256(T0P1, T2P3, m2, m0));
              _mm256_storeu_si256((__m256i *)(a + j2),
                                  montgomery_sub_256(T0P1, T2P3, m2, m0));
              _mm256_storeu_si256((__m256i *)(a + j1),
                                  montgomery_add_256(T0M1, T2M3, m2, m0));
              _mm256_storeu_si256((__m256i *)(a + j3),
                                  montgomery_sub_256(T0M1, T2M3, m2, m0));
            }
          } else {
            ww = xx * xx, yy = xx * imag;
            const __m256i WW = _mm256_set1_epi32(ww.a);
            const __m256i XX = _mm256_set1_epi32(xx.a);
            const __m256i YY = _mm256_set1_epi32(yy.a);
            int j0 = jh * v;
            int j1 = j0 + v;
            int j2 = j1 + v;
            int j3 = j2 + v;
            int je = j1;
            for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
              const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
              const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
              const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
              const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
              const __m256i T0P1 = montgomery_add_256(T0, T1, m2, m0);
              const __m256i T2P3 = montgomery_add_256(T2, T3, m2, m0);
              const __m256i T0M1 = montgomery_mul_256(
                  montgomery_sub_256(T0, T1, m2, m0), XX, r, m1);
              const __m256i T2M3 = montgomery_mul_256(
                  montgomery_sub_256(T2, T3, m2, m0), YY, r, m1);
              _mm256_storeu_si256((__m256i *)(a + j0),
                                  montgomery_add_256(T0P1, T2P3, m2, m0));
              _mm256_storeu_si256(
                  (__m256i *)(a + j2),
                  montgomery_mul_256(montgomery_sub_256(T0P1, T2P3, m2, m0), WW,
                                     r, m1));
              _mm256_storeu_si256((__m256i *)(a + j1),
                                  montgomery_add_256(T0M1, T2M3, m2, m0));
              _mm256_storeu_si256(
                  (__m256i *)(a + j3),
                  montgomery_mul_256(montgomery_sub_256(T0M1, T2M3, m2, m0), WW,
                                     r, m1));
            }
          }
          xx *= dy[__builtin_ctz(jh += 4)];
        }
      }
      u >>= 4;
      v <<= 2;
    }
    if (k & 1) {
      v = 1 << (k - 1);
      if (v < 8) {
        for (int j = 0; j < v; ++j) {
          mint ajv = a[j] - a[j + v];
          a[j] += a[j + v];
          a[j + v] = ajv;
        }
      } else {
        const __m256i m0 = _mm256_set1_epi32(0);
        const __m256i m2 = _mm256_set1_epi32(mod + mod);
        int j0 = 0;
        int j1 = v;
        for (; j0 < v; j0 += 8, j1 += 8) {
          const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
          const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
          __m256i naj = montgomery_add_256(T0, T1, m2, m0);
          __m256i najv = montgomery_sub_256(T0, T1, m2, m0);
          _mm256_storeu_si256((__m256i *)(a + j0), naj);
          _mm256_storeu_si256((__m256i *)(a + j1), najv);
        }
      }
    }
    if (normalize) {
      mint invn = mint(n).inverse();
      for (int i = 0; i < n; i++) a[i] *= invn;
    }
  }

  __attribute__((target("avx2"))) void inplace_multiply(
      int l1, int l2, int zero_padding = true) {
    int l = l1 + l2 - 1;
    int M = 4;
    while (M < l) M <<= 1;
    if (zero_padding) {
      for (int i = l1; i < M; i++) ntt_inner::_buf1[i] = 0;
      for (int i = l2; i < M; i++) ntt_inner::_buf2[i] = 0;
    }
    const __m256i m0 = _mm256_set1_epi32(0);
    const __m256i m1 = _mm256_set1_epi32(mod);
    const __m256i r = _mm256_set1_epi32(mint::r);
    const __m256i N2 = _mm256_set1_epi32(mint::n2);
    for (int i = 0; i < l1; i += 8) {
      __m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
      __m256i b = montgomery_mul_256(a, N2, r, m1);
      _mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), b);
    }
    for (int i = 0; i < l2; i += 8) {
      __m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf2 + i));
      __m256i b = montgomery_mul_256(a, N2, r, m1);
      _mm256_storeu_si256((__m256i *)(ntt_inner::_buf2 + i), b);
    }
    ntt(buf1, M);
    ntt(buf2, M);
    for (int i = 0; i < M; i += 8) {
      __m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
      __m256i b = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf2 + i));
      __m256i c = montgomery_mul_256(a, b, r, m1);
      _mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), c);
    }
    intt(buf1, M, false);
    const __m256i INVM = _mm256_set1_epi32((mint(M).inverse()).a);
    for (int i = 0; i < l; i += 8) {
      __m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
      __m256i b = montgomery_mul_256(a, INVM, r, m1);
      __m256i c = my256_mulhi_epu32(my256_mullo_epu32(b, r), m1);
      __m256i d = _mm256_and_si256(_mm256_cmpgt_epi32(c, m0), m1);
      __m256i e = _mm256_sub_epi32(d, c);
      _mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), e);
    }
  }

  void ntt(vector<mint> &a) {
    int M = (int)a.size();
    for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
    ntt(buf1, M);
    for (int i = 0; i < M; i++) a[i].a = buf1[i].a;
  }

  void intt(vector<mint> &a) {
    int M = (int)a.size();
    for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
    intt(buf1, M, true);
    for (int i = 0; i < M; i++) a[i].a = buf1[i].a;
  }

  vector<mint> multiply(const vector<mint> &a, const vector<mint> &b) {
    if (a.size() == 0 && b.size() == 0) return vector<mint>{};
    int l = a.size() + b.size() - 1;
    if (min<int>(a.size(), b.size()) <= 40) {
      vector<mint> s(l);
      for (int i = 0; i < (int)a.size(); ++i)
        for (int j = 0; j < (int)b.size(); ++j) s[i + j] += a[i] * b[j];
      return s;
    }
    assert(l <= ntt_inner::SZ_FFT_BUF);
    int M = 4;
    while (M < l) M <<= 1;
    for (int i = 0; i < (int)a.size(); ++i) buf1[i].a = a[i].a;
    for (int i = (int)a.size(); i < M; ++i) buf1[i].a = 0;
    for (int i = 0; i < (int)b.size(); ++i) buf2[i].a = b[i].a;
    for (int i = (int)b.size(); i < M; ++i) buf2[i].a = 0;
    ntt(buf1, M);
    ntt(buf2, M);
    for (int i = 0; i < M; ++i)
      buf1[i].a = mint::reduce(uint64_t(buf1[i].a) * buf2[i].a);
    intt(buf1, M, false);
    vector<mint> s(l);
    mint invm = mint(M).inverse();
    for (int i = 0; i < l; ++i) s[i] = buf1[i] * invm;
    return s;
  }

  void ntt_doubling(vector<mint> &a) {
    int M = (int)a.size();
    for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
    intt(buf1, M);
    mint r = 1, zeta = mint(pr).pow((mint::get_mod() - 1) / (M << 1));
    for (int i = 0; i < M; i++) buf1[i] *= r, r *= zeta;
    ntt(buf1, M);
    a.resize(2 * M);
    for (int i = 0; i < M; i++) a[M + i].a = buf1[i].a;
  }
};


namespace ArbitraryNTT {
using i64 = int64_t;
using u128 = __uint128_t;
constexpr int32_t m0 = 167772161;
constexpr int32_t m1 = 469762049;
constexpr int32_t m2 = 754974721;
using mint0 = LazyMontgomeryModInt<m0>;
using mint1 = LazyMontgomeryModInt<m1>;
using mint2 = LazyMontgomeryModInt<m2>;
constexpr int r01 = mint1(m0).inverse().get();
constexpr int r02 = mint2(m0).inverse().get();
constexpr int r12 = mint2(m1).inverse().get();
constexpr int r02r12 = i64(r02) * r12 % m2;
constexpr i64 w1 = m0;
constexpr i64 w2 = i64(m0) * m1;

template <typename T, typename submint>
vector<submint> mul(const vector<T> &a, const vector<T> &b) {
  static NTT<submint> ntt;
  vector<submint> s(a.size()), t(b.size());
  for (int i = 0; i < (int)a.size(); ++i) s[i] = i64(a[i] % submint::get_mod());
  for (int i = 0; i < (int)b.size(); ++i) t[i] = i64(b[i] % submint::get_mod());
  return ntt.multiply(s, t);
}

template <typename T>
vector<int> multiply(const vector<T> &s, const vector<T> &t, int mod) {
  auto d0 = mul<T, mint0>(s, t);
  auto d1 = mul<T, mint1>(s, t);
  auto d2 = mul<T, mint2>(s, t);
  int n = d0.size();
  vector<int> ret(n);
  const int W1 = w1 % mod;
  const int W2 = w2 % mod;
  for (int i = 0; i < n; i++) {
    int n1 = d1[i].get(), n2 = d2[i].get(), a = d0[i].get();
    int b = i64(n1 + m1 - a) * r01 % m1;
    int c = (i64(n2 + m2 - a) * r02r12 + i64(m2 - b) * r12) % m2;
    ret[i] = (i64(a) + i64(b) * W1 + i64(c) * W2) % mod;
  }
  return ret;
}

template <typename mint>
vector<mint> multiply(const vector<mint> &a, const vector<mint> &b) {
  if (a.size() == 0 && b.size() == 0) return {};
  if (min<int>(a.size(), b.size()) < 128) {
    vector<mint> ret(a.size() + b.size() - 1);
    for (int i = 0; i < (int)a.size(); ++i)
      for (int j = 0; j < (int)b.size(); ++j) ret[i + j] += a[i] * b[j];
    return ret;
  }
  vector<int> s(a.size()), t(b.size());
  for (int i = 0; i < (int)a.size(); ++i) s[i] = a[i].get();
  for (int i = 0; i < (int)b.size(); ++i) t[i] = b[i].get();
  vector<int> u = multiply<int>(s, t, mint::get_mod());
  vector<mint> ret(u.size());
  for (int i = 0; i < (int)u.size(); ++i) ret[i] = mint(u[i]);
  return ret;
}

template <typename T>
vector<u128> multiply_u128(const vector<T> &s, const vector<T> &t) {
  if (s.size() == 0 && t.size() == 0) return {};
  if (min<int>(s.size(), t.size()) < 128) {
    vector<u128> ret(s.size() + t.size() - 1);
    for (int i = 0; i < (int)s.size(); ++i)
      for (int j = 0; j < (int)t.size(); ++j) ret[i + j] += i64(s[i]) * t[j];
    return ret;
  }
  auto d0 = mul<T, mint0>(s, t);
  auto d1 = mul<T, mint1>(s, t);
  auto d2 = mul<T, mint2>(s, t);
  int n = d0.size();
  vector<u128> ret(n);
  for (int i = 0; i < n; i++) {
    i64 n1 = d1[i].get(), n2 = d2[i].get();
    i64 a = d0[i].get();
    i64 b = (n1 + m1 - a) * r01 % m1;
    i64 c = ((n2 + m2 - a) * r02r12 + (m2 - b) * r12) % m2;
    ret[i] = a + b * w1 + u128(c) * w2;
  }
  return ret;
}
}  // namespace ArbitraryNTT


namespace MultiPrecisionIntegerImpl {
struct TENS {
  static constexpr int offset = 30;
  constexpr TENS() : _tend() {
    _tend[offset] = 1;
    for (int i = 1; i <= offset; i++) {
      _tend[offset + i] = _tend[offset + i - 1] * 10.0;
      _tend[offset - i] = 1.0 / _tend[offset + i];
    }
  }
  long double ten_ld(int n) const {
    assert(-offset <= n and n <= offset);
    return _tend[n + offset];
  }

 private:
  long double _tend[offset * 2 + 1];
};
}  // namespace MultiPrecisionIntegerImpl

// 0 は neg=false, dat={} として扱う
struct MultiPrecisionInteger {
  using M = MultiPrecisionInteger;
  inline constexpr static MultiPrecisionIntegerImpl::TENS tens = {};

  static constexpr int D = 1000000000;
  static constexpr int logD = 9;
  bool neg;
  vector<int> dat;

  MultiPrecisionInteger() : neg(false), dat() {}

  MultiPrecisionInteger(bool n, const vector<int>& d) : neg(n), dat(d) {}

  template <typename I,
            enable_if_t<internal::is_broadly_integral_v<I>>* = nullptr>
  MultiPrecisionInteger(I x) : neg(false) {
    if constexpr (internal::is_broadly_signed_v<I>) {
      if (x < 0) neg = true, x = -x;
    }
    while (x) dat.push_back(x % D), x /= D;
  }

  MultiPrecisionInteger(const string& S) : neg(false) {
    assert(!S.empty());
    if (S.size() == 1u && S[0] == '0') return;
    int l = 0;
    if (S[0] == '-') ++l, neg = true;
    for (int ie = S.size(); l < ie; ie -= logD) {
      int is = max(l, ie - logD);
      long long x = 0;
      for (int i = is; i < ie; i++) x = x * 10 + S[i] - '0';
      dat.push_back(x);
    }
    while(!dat.empty() and dat.back() == 0) dat.pop_back();
  }

  friend M operator+(const M& lhs, const M& rhs) {
    if (lhs.neg == rhs.neg) return {lhs.neg, _add(lhs.dat, rhs.dat)};
    if (_leq(lhs.dat, rhs.dat)) {
      // |l| <= |r|
      auto c = _sub(rhs.dat, lhs.dat);
      bool n = _is_zero(c) ? false : rhs.neg;
      return {n, c};
    }
    auto c = _sub(lhs.dat, rhs.dat);
    bool n = _is_zero(c) ? false : lhs.neg;
    return {n, c};
  }
  friend M operator-(const M& lhs, const M& rhs) { return lhs + (-rhs); }

  friend M operator*(const M& lhs, const M& rhs) {
    auto c = _mul(lhs.dat, rhs.dat);
    bool n = _is_zero(c) ? false : (lhs.neg ^ rhs.neg);
    return {n, c};
  }
  friend pair<M, M> divmod(const M& lhs, const M& rhs) {
    auto dm = _divmod_newton(lhs.dat, rhs.dat);
    bool dn = _is_zero(dm.first) ? false : lhs.neg != rhs.neg;
    bool mn = _is_zero(dm.second) ? false : lhs.neg;
    return {M{dn, dm.first}, M{mn, dm.second}};
  }
  friend M operator/(const M& lhs, const M& rhs) {
    return divmod(lhs, rhs).first;
  }
  friend M operator%(const M& lhs, const M& rhs) {
    return divmod(lhs, rhs).second;
  }

  M& operator+=(const M& rhs) { return (*this) = (*this) + rhs; }
  M& operator-=(const M& rhs) { return (*this) = (*this) - rhs; }
  M& operator*=(const M& rhs) { return (*this) = (*this) * rhs; }
  M& operator/=(const M& rhs) { return (*this) = (*this) / rhs; }
  M& operator%=(const M& rhs) { return (*this) = (*this) % rhs; }

  M operator-() const {
    if (is_zero()) return *this;
    return {!neg, dat};
  }
  M operator+() const { return *this; }
  friend M abs(const M& m) { return {false, m.dat}; }
  bool is_zero() const { return _is_zero(dat); }

  friend bool operator==(const M& lhs, const M& rhs) {
    return lhs.neg == rhs.neg && lhs.dat == rhs.dat;
  }
  friend bool operator!=(const M& lhs, const M& rhs) {
    return lhs.neg != rhs.neg || lhs.dat != rhs.dat;
  }
  friend bool operator<(const M& lhs, const M& rhs) {
    if (lhs == rhs) return false;
    return _neq_lt(lhs, rhs);
  }
  friend bool operator<=(const M& lhs, const M& rhs) {
    if (lhs == rhs) return true;
    return _neq_lt(lhs, rhs);
  }
  friend bool operator>(const M& lhs, const M& rhs) {
    if (lhs == rhs) return false;
    return _neq_lt(rhs, lhs);
  }
  friend bool operator>=(const M& lhs, const M& rhs) {
    if (lhs == rhs) return true;
    return _neq_lt(rhs, lhs);
  }

  // a * 10^b (1 <= |a| < 10) の形で渡す
  // 相対誤差:10^{-16} ~ 10^{-19} 程度 (処理系依存)
  pair<long double, int> dfp() const {
    if (is_zero()) return {0, 0};
    int l = max<int>(0, _size() - 3);
    int b = logD * l;
    string prefix{};
    for (int i = _size() - 1; i >= l; i--) {
      prefix += _itos(dat[i], i != _size() - 1);
    }
    b += prefix.size() - 1;
    long double a = 0;
    for (auto& c : prefix) a = a * 10.0 + (c - '0');
    a *= tens.ten_ld(-((int)prefix.size()) + 1);
    a = clamp<long double>(a, 1.0, nextafterl(10.0, 1.0));
    if (neg) a = -a;
    return {a, b};
  }
  string to_string() const {
    if (is_zero()) return "0";
    string res;
    if (neg) res.push_back('-');
    for (int i = _size() - 1; i >= 0; i--) {
      res += _itos(dat[i], i != _size() - 1);
    }
    return res;
  }
  long double to_ld() const {
    auto [a, b] = dfp();
    if (-tens.offset <= b and b <= tens.offset) {
      return a * tens.ten_ld(b);
    }
    return a * powl(10, b);
  }
  long long to_ll() const {
    long long res = _to_ll(dat);
    return neg ? -res : res;
  }
  __int128_t to_i128() const {
    __int128_t res = _to_i128(dat);
    return neg ? -res : res;
  }

  friend istream& operator>>(istream& is, M& m) {
    string s;
    is >> s;
    m = M{s};
    return is;
  }

  friend ostream& operator<<(ostream& os, const M& m) {
    return os << m.to_string();
  }

  // 内部の関数をテスト
  static void _test_private_function(const M&, const M&);

 private:
  // size
  int _size() const { return dat.size(); }
  // a == b
  static bool _eq(const vector<int>& a, const vector<int>& b) { return a == b; }
  // a < b
  static bool _lt(const vector<int>& a, const vector<int>& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    for (int i = a.size() - 1; i >= 0; i--) {
      if (a[i] != b[i]) return a[i] < b[i];
    }
    return false;
  }
  // a <= b
  static bool _leq(const vector<int>& a, const vector<int>& b) {
    return _eq(a, b) || _lt(a, b);
  }
  // a < b (s.t. a != b)
  static bool _neq_lt(const M& lhs, const M& rhs) {
    assert(lhs != rhs);
    if (lhs.neg != rhs.neg) return lhs.neg;
    bool f = _lt(lhs.dat, rhs.dat);
    if (f) return !lhs.neg;
    return lhs.neg;
  }
  // a == 0
  static bool _is_zero(const vector<int>& a) { return a.empty(); }
  // a == 1
  static bool _is_one(const vector<int>& a) {
    return (int)a.size() == 1 && a[0] == 1;
  }
  // 末尾 0 を削除
  static void _shrink(vector<int>& a) {
    while (a.size() && a.back() == 0) a.pop_back();
  }
  // 末尾 0 を削除
  void _shrink() {
    while (_size() && dat.back() == 0) dat.pop_back();
  }
  // a + b
  static vector<int> _add(const vector<int>& a, const vector<int>& b) {
    vector<int> c(max(a.size(), b.size()) + 1);
    for (int i = 0; i < (int)a.size(); i++) c[i] += a[i];
    for (int i = 0; i < (int)b.size(); i++) c[i] += b[i];
    for (int i = 0; i < (int)c.size() - 1; i++) {
      if (c[i] >= D) c[i] -= D, c[i + 1]++;
    }
    _shrink(c);
    return c;
  }
  // a - b
  static vector<int> _sub(const vector<int>& a, const vector<int>& b) {
    assert(_leq(b, a));
    vector<int> c{a};
    int borrow = 0;
    for (int i = 0; i < (int)a.size(); i++) {
      if (i < (int)b.size()) borrow += b[i];
      c[i] -= borrow;
      borrow = 0;
      if (c[i] < 0) c[i] += D, borrow = 1;
    }
    assert(borrow == 0);
    _shrink(c);
    return c;
  }
  // a * b (fft)
  static vector<int> _mul_fft(const vector<int>& a, const vector<int>& b) {
    if (a.empty() || b.empty()) return {};
    auto m = ArbitraryNTT::multiply_u128(a, b);
    vector<int> c;
    c.reserve(m.size() + 3);
    __uint128_t x = 0;
    for (int i = 0;; i++) {
      if (i >= (int)m.size() && x == 0) break;
      if (i < (int)m.size()) x += m[i];
      c.push_back(x % D);
      x /= D;
    }
    _shrink(c);
    return c;
  }
  // a * b (naive)
  static vector<int> _mul_naive(const vector<int>& a, const vector<int>& b) {
    if (a.empty() || b.empty()) return {};
    vector<long long> prod(a.size() + b.size() - 1 + 1);
    for (int i = 0; i < (int)a.size(); i++) {
      for (int j = 0; j < (int)b.size(); j++) {
        long long p = 1LL * a[i] * b[j];
        prod[i + j] += p;
        if (prod[i + j] >= (4LL * D * D)) {
          prod[i + j] -= 4LL * D * D;
          prod[i + j + 1] += 4LL * D;
        }
      }
    }
    vector<int> c(prod.size() + 1);
    long long x = 0;
    int i = 0;
    for (; i < (int)prod.size(); i++) x += prod[i], c[i] = x % D, x /= D;
    while (x) c[i] = x % D, x /= D, i++;
    _shrink(c);
    return c;
  }
  // a * b
  static vector<int> _mul(const vector<int>& a, const vector<int>& b) {
    if (_is_zero(a) || _is_zero(b)) return {};
    if (_is_one(a)) return b;
    if (_is_one(b)) return a;
    if (min<int>(a.size(), b.size()) <= 128) {
      return a.size() < b.size() ? _mul_naive(b, a) : _mul_naive(a, b);
    }
    return _mul_fft(a, b);
  }
  // 0 <= A < 1e18, 1 <= B < 1e9
  static pair<vector<int>, vector<int>> _divmod_li(const vector<int>& a,
                                                   const vector<int>& b) {
    assert(0 <= (int)a.size() && (int)a.size() <= 2);
    assert((int)b.size() == 1);
    long long va = _to_ll(a);
    int vb = b[0];
    return {_integer_to_vec(va / vb), _integer_to_vec(va % vb)};
  }
  // 0 <= A < 1e18, 1 <= B < 1e18
  static pair<vector<int>, vector<int>> _divmod_ll(const vector<int>& a,
                                                   const vector<int>& b) {
    assert(0 <= (int)a.size() && (int)a.size() <= 2);
    assert(1 <= (int)b.size() && (int)b.size() <= 2);
    long long va = _to_ll(a), vb = _to_ll(b);
    return {_integer_to_vec(va / vb), _integer_to_vec(va % vb)};
  }
  // 1 <= B < 1e9
  static pair<vector<int>, vector<int>> _divmod_1e9(const vector<int>& a,
                                                    const vector<int>& b) {
    assert((int)b.size() == 1);
    if (b[0] == 1) return {a, {}};
    if ((int)a.size() <= 2) return _divmod_li(a, b);
    vector<int> quo(a.size());
    long long d = 0;
    int b0 = b[0];
    for (int i = a.size() - 1; i >= 0; i--) {
      d = d * D + a[i];
      assert(d < 1LL * D * b0);
      int q = d / b0, r = d % b0;
      quo[i] = q, d = r;
    }
    _shrink(quo);
    return {quo, d ? vector<int>{int(d)} : vector<int>{}};
  }
  // 0 <= A, 1 <= B
  static pair<vector<int>, vector<int>> _divmod_naive(const vector<int>& a,
                                                      const vector<int>& b) {
    if (_is_zero(b)) {
      cerr << "Divide by Zero Exception" << endl;
      exit(1);
    }
    assert(1 <= (int)b.size());
    if ((int)b.size() == 1) return _divmod_1e9(a, b);
    if (max<int>(a.size(), b.size()) <= 2) return _divmod_ll(a, b);
    if (_lt(a, b)) return {{}, a};
    // B >= 1e9, A >= B
    int norm = D / (b.back() + 1);
    vector<int> x = _mul(a, {norm});
    vector<int> y = _mul(b, {norm});
    int yb = y.back();
    vector<int> quo(x.size() - y.size() + 1);
    vector<int> rem(x.end() - y.size(), x.end());
    for (int i = quo.size() - 1; i >= 0; i--) {
      if (rem.size() < y.size()) {
        // do nothing
      } else if (rem.size() == y.size()) {
        if (_leq(y, rem)) {
          quo[i] = 1, rem = _sub(rem, y);
        }
      } else {
        assert(y.size() + 1 == rem.size());
        long long rb = 1LL * rem[rem.size() - 1] * D + rem[rem.size() - 2];
        int q = rb / yb;
        vector<int> yq = _mul(y, {q});
        // 真の商は q-2 以上 q+1 以下だが自信が無いので念のため while を回す
        while (_lt(rem, yq)) q--, yq = _sub(yq, y);
        rem = _sub(rem, yq);
        while (_leq(y, rem)) q++, rem = _sub(rem, y);
        quo[i] = q;
      }
      if (i) rem.insert(begin(rem), x[i - 1]);
    }
    _shrink(quo), _shrink(rem);
    auto [q2, r2] = _divmod_1e9(rem, {norm});
    assert(_is_zero(r2));
    return {quo, q2};
  }

  // 0 <= A, 1 <= B
  static pair<vector<int>, vector<int>> _divmod_dc(const vector<int>& a,
                                                   const vector<int>& b);

  // 1 / a を 絶対誤差 B^{-deg} で求める
  static vector<int> _calc_inv(const vector<int>& a, int deg) {
    assert(!a.empty() && D / 2 <= a.back() and a.back() < D);
    int k = deg, c = a.size();
    while (k > 64) k = (k + 1) / 2;
    vector<int> z(c + k + 1);
    z.back() = 1;
    z = _divmod_naive(z, a).first;
    while (k < deg) {
      vector<int> s = _mul(z, z);
      s.insert(begin(s), 0);
      int d = min(c, 2 * k + 1);
      vector<int> t{end(a) - d, end(a)}, u = _mul(s, t);
      u.erase(begin(u), begin(u) + d);
      vector<int> w(k + 1), w2 = _add(z, z);
      copy(begin(w2), end(w2), back_inserter(w));
      z = _sub(w, u);
      z.erase(begin(z));
      k *= 2;
    }
    z.erase(begin(z), begin(z) + k - deg);
    return z;
  }

  static pair<vector<int>, vector<int>> _divmod_newton(const vector<int>& a,
                                                       const vector<int>& b) {
    if (_is_zero(b)) {
      cerr << "Divide by Zero Exception" << endl;
      exit(1);
    }
    if ((int)b.size() <= 64) return _divmod_naive(a, b);
    if ((int)a.size() - (int)b.size() <= 64) return _divmod_naive(a, b);
    int norm = D / (b.back() + 1);
    vector<int> x = _mul(a, {norm});
    vector<int> y = _mul(b, {norm});
    int s = x.size(), t = y.size();
    int deg = s - t + 2;
    vector<int> z = _calc_inv(y, deg);
    vector<int> q = _mul(x, z);
    q.erase(begin(q), begin(q) + t + deg);
    vector<int> yq = _mul(y, {q});
    while (_lt(x, yq)) q = _sub(q, {1}), yq = _sub(yq, y);
    vector<int> r = _sub(x, yq);
    while (_leq(y, r)) q = _add(q, {1}), r = _sub(r, y);
    _shrink(q), _shrink(r);
    auto [q2, r2] = _divmod_1e9(r, {norm});
    assert(_is_zero(r2));
    return {q, q2};
  }

  // int -> string
  // 先頭かどうかに応じて zero padding するかを決める
  static string _itos(int x, bool zero_padding) {
    assert(0 <= x && x < D);
    string res;
    for (int i = 0; i < logD; i++) {
      res.push_back('0' + x % 10), x /= 10;
    }
    if (!zero_padding) {
      while (res.size() && res.back() == '0') res.pop_back();
      assert(!res.empty());
    }
    reverse(begin(res), end(res));
    return res;
  }

  // convert ll to vec
  template <typename I,
            enable_if_t<internal::is_broadly_integral_v<I>>* = nullptr>
  static vector<int> _integer_to_vec(I x) {
    if constexpr (internal::is_broadly_signed_v<I>) {
      assert(x >= 0);
    }
    vector<int> res;
    while (x) res.push_back(x % D), x /= D;
    return res;
  }

  static long long _to_ll(const vector<int>& a) {
    long long res = 0;
    for (int i = (int)a.size() - 1; i >= 0; i--) res = res * D + a[i];
    return res;
  }

  static __int128_t _to_i128(const vector<int>& a) {
    __int128_t res = 0;
    for (int i = (int)a.size() - 1; i >= 0; i--) res = res * D + a[i];
    return res;
  }

  static void _dump(const vector<int>& a, string s = "") {
    if (!s.empty()) cerr << s << " : ";
    cerr << "{ ";
    for (int i = 0; i < (int)a.size(); i++) cerr << a[i] << ", ";
    cerr << "}" << endl;
  }
};

using bigint = MultiPrecisionInteger;

/**
 * @brief 多倍長整数
 */









using namespace std;

// {rank, det(非正方行列の場合は未定義)} を返す
// 型が double や Rational でも動くはず?(未検証)
//
// pivot 候補 : [0, pivot_end)
template <typename T>
std::pair<int, T> GaussElimination(vector<vector<T>> &a, int pivot_end = -1,
                                   bool diagonalize = false) {
  if (a.empty()) return {0, 1};
  int H = a.size(), W = a[0].size(), rank = 0;
  if (pivot_end == -1) pivot_end = W;
  T det = 1;
  for (int j = 0; j < pivot_end; j++) {
    int idx = -1;
    for (int i = rank; i < H; i++) {
      if (a[i][j] != T(0)) {
        idx = i;
        break;
      }
    }
    if (idx == -1) {
      det = 0;
      continue;
    }
    if (rank != idx) det = -det, swap(a[rank], a[idx]);
    det *= a[rank][j];
    if (diagonalize && a[rank][j] != T(1)) {
      T coeff = T(1) / a[rank][j];
      for (int k = j; k < W; k++) a[rank][k] *= coeff;
    }
    int is = diagonalize ? 0 : rank + 1;
    for (int i = is; i < H; i++) {
      if (i == rank) continue;
      if (a[i][j] != T(0)) {
        T coeff = a[i][j] / a[rank][j];
        for (int k = j; k < W; k++) a[i][k] -= a[rank][k] * coeff;
      }
    }
    rank++;
  }
  return make_pair(rank, det);
}


template <typename mint>
vector<vector<mint>> inverse_matrix(const vector<vector<mint>>& a) {
  int N = a.size();
  assert(N > 0);
  assert(N == (int)a[0].size());

  vector<vector<mint>> m(N, vector<mint>(2 * N));
  for (int i = 0; i < N; i++) {
    copy(begin(a[i]), end(a[i]), begin(m[i]));
    m[i][N + i] = 1;
  }

  auto [rank, det] = GaussElimination(m, N, true);
  if (rank != N) return {};

  vector<vector<mint>> b(N);
  for (int i = 0; i < N; i++) {
    copy(begin(m[i]) + N, end(m[i]), back_inserter(b[i]));
  }
  return b;
}


template <class T>
struct Matrix {
  vector<vector<T> > A;

  Matrix() = default;
  Matrix(int n, int m) : A(n, vector<T>(m, T())) {}
  Matrix(int n) : A(n, vector<T>(n, T())){};

  int H() const { return A.size(); }

  int W() const { return A[0].size(); }

  int size() const { return A.size(); }

  inline const vector<T> &operator[](int k) const { return A[k]; }

  inline vector<T> &operator[](int k) { return A[k]; }

  static Matrix I(int n) {
    Matrix mat(n);
    for (int i = 0; i < n; i++) mat[i][i] = 1;
    return (mat);
  }

  Matrix &operator+=(const Matrix &B) {
    int n = H(), m = W();
    assert(n == B.H() && m == B.W());
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) (*this)[i][j] += B[i][j];
    return (*this);
  }

  Matrix &operator-=(const Matrix &B) {
    int n = H(), m = W();
    assert(n == B.H() && m == B.W());
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) (*this)[i][j] -= B[i][j];
    return (*this);
  }

  Matrix &operator*=(const Matrix &B) {
    int n = H(), m = B.W(), p = W();
    assert(p == B.H());
    vector<vector<T> > C(n, vector<T>(m, T{}));
    for (int i = 0; i < n; i++)
      for (int k = 0; k < p; k++)
        for (int j = 0; j < m; j++) C[i][j] += (*this)[i][k] * B[k][j];
    A.swap(C);
    return (*this);
  }

  Matrix &operator^=(long long k) {
    Matrix B = Matrix::I(H());
    while (k > 0) {
      if (k & 1) B *= *this;
      *this *= *this;
      k >>= 1LL;
    }
    A.swap(B.A);
    return (*this);
  }

  Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); }

  Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); }

  Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); }

  Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); }

  bool operator==(const Matrix &B) const {
    assert(H() == B.H() && W() == B.W());
    for (int i = 0; i < H(); i++)
      for (int j = 0; j < W(); j++)
        if (A[i][j] != B[i][j]) return false;
    return true;
  }

  bool operator!=(const Matrix &B) const {
    assert(H() == B.H() && W() == B.W());
    for (int i = 0; i < H(); i++)
      for (int j = 0; j < W(); j++)
        if (A[i][j] != B[i][j]) return true;
    return false;
  }

  Matrix inverse() const {
    assert(H() == W());
    Matrix B(H());
    B.A = inverse_matrix(A);
    return B;
  }

  friend ostream &operator<<(ostream &os, const Matrix &p) {
    int n = p.H(), m = p.W();
    for (int i = 0; i < n; i++) {
      os << (i ? "   " : "") << "[";
      for (int j = 0; j < m; j++) {
        os << p[i][j] << (j + 1 == m ? "]\n" : ",");
      }
    }
    return (os);
  }

  T determinant() const {
    Matrix B(*this);
    assert(H() == W());
    T ret = 1;
    for (int i = 0; i < H(); i++) {
      int idx = -1;
      for (int j = i; j < W(); j++) {
        if (B[j][i] != 0) {
          idx = j;
          break;
        }
      }
      if (idx == -1) return 0;
      if (i != idx) {
        ret *= T(-1);
        swap(B[i], B[idx]);
      }
      ret *= B[i][i];
      T inv = T(1) / B[i][i];
      for (int j = 0; j < W(); j++) {
        B[i][j] *= inv;
      }
      for (int j = i + 1; j < H(); j++) {
        T a = B[j][i];
        if (a == 0) continue;
        for (int k = i; k < W(); k++) {
          B[j][k] -= B[i][k] * a;
        }
      }
    }
    return ret;
  }
};

/**
 * @brief 行列ライブラリ
 */







using namespace std;

namespace internal {
unsigned long long non_deterministic_seed() {
  unsigned long long m =
      chrono::duration_cast<chrono::nanoseconds>(
          chrono::high_resolution_clock::now().time_since_epoch())
          .count();
  m ^= 9845834732710364265uLL;
  m ^= m << 24, m ^= m >> 31, m ^= m << 35;
  return m;
}
unsigned long long deterministic_seed() { return 88172645463325252UL; }

// 64 bit の seed 値を生成 (手元では seed 固定)
// 連続で呼び出すと同じ値が何度も返ってくるので注意
// #define RANDOMIZED_SEED するとシードがランダムになる
unsigned long long seed() {
#if defined(NyaanLocal) && !defined(RANDOMIZED_SEED)
  return deterministic_seed();
#else
  return non_deterministic_seed();
#endif
}

}  // namespace internal


namespace my_rand {
using i64 = long long;
using u64 = unsigned long long;

// [0, 2^64 - 1)
u64 rng() {
  static u64 _x = internal::seed();
  return _x ^= _x << 7, _x ^= _x >> 9;
}

// [l, r]
i64 rng(i64 l, i64 r) {
  assert(l <= r);
  return l + rng() % u64(r - l + 1);
}

// [l, r)
i64 randint(i64 l, i64 r) {
  assert(l < r);
  return l + rng() % u64(r - l);
}

// choose n numbers from [l, r) without overlapping
vector<i64> randset(i64 l, i64 r, i64 n) {
  assert(l <= r && n <= r - l);
  unordered_set<i64> s;
  for (i64 i = n; i; --i) {
    i64 m = randint(l, r + 1 - i);
    if (s.find(m) != s.end()) m = r - i;
    s.insert(m);
  }
  vector<i64> ret;
  for (auto& x : s) ret.push_back(x);
  sort(begin(ret), end(ret));
  return ret;
}

// [0.0, 1.0)
double rnd() { return rng() * 5.42101086242752217004e-20; }
// [l, r)
double rnd(double l, double r) {
  assert(l < r);
  return l + rnd() * (r - l);
}

template <typename T>
void randshf(vector<T>& v) {
  int n = v.size();
  for (int i = 1; i < n; i++) swap(v[i], v[randint(0, i + 1)]);
}

}  // namespace my_rand

using my_rand::randint;
using my_rand::randset;
using my_rand::randshf;
using my_rand::rnd;
using my_rand::rng;





using namespace std;





namespace internal {


using namespace std;

// a mod p
template <typename T>
T safe_mod(T a, T p) {
  a %= p;
  if constexpr (is_broadly_signed_v<T>) {
    if (a < 0) a += p;
  }
  return a;
}

// 返り値:pair(g, x)
// s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
template <typename T>
pair<T, T> inv_gcd(T a, T p) {
  static_assert(is_broadly_signed_v<T>);
  a = safe_mod(a, p);
  if (a == 0) return {p, 0};
  T b = p, x = 1, y = 0;
  while (a != 0) {
    T q = b / a;
    swap(a, b %= a);
    swap(x, y -= q * x);
  }
  if (y < 0) y += p / b;
  return {b, y};
}

// 返り値 : a^{-1} mod p
// gcd(a, p) != 1 が必要
template <typename T>
T inv(T a, T p) {
  static_assert(is_broadly_signed_v<T>);
  a = safe_mod(a, p);
  T b = p, x = 1, y = 0;
  while (a != 0) {
    T q = b / a;
    swap(a, b %= a);
    swap(x, y -= q * x);
  }
  assert(b == 1);
  return y < 0 ? y + p : y;
}

// T : 底の型
// U : T*T がオーバーフローしない かつ 指数の型
template <typename T, typename U>
T modpow(T a, U n, T p) {
  a = safe_mod(a, p);
  T ret = 1 % p;
  while (n != 0) {
    if (n % 2 == 1) ret = U(ret) * a % p;
    a = U(a) * a % p;
    n /= 2;
  }
  return ret;
}

// 返り値 : pair(rem, mod)
// 解なしのときは {0, 0} を返す
template <typename T>
pair<T, T> crt(const vector<T>& r, const vector<T>& m) {
  static_assert(is_broadly_signed_v<T>);
  assert(r.size() == m.size());
  int n = int(r.size());
  T r0 = 0, m0 = 1;
  for (int i = 0; i < n; i++) {
    assert(1 <= m[i]);
    T r1 = safe_mod(r[i], m[i]), m1 = m[i];
    if (m0 < m1) swap(r0, r1), swap(m0, m1);
    if (m0 % m1 == 0) {
      if (r0 % m1 != r1) return {0, 0};
      continue;
    }
    auto [g, im] = inv_gcd(m0, m1);
    T u1 = m1 / g;
    if ((r1 - r0) % g) return {0, 0};
    T x = (r1 - r0) / g % u1 * im % u1;
    r0 += x * m0;
    m0 *= u1;
    if (r0 < 0) r0 += m0;
  }
  return {r0, m0};
}

}  // namespace internal



using namespace std;

template <typename Int, typename UInt, typename Long, typename ULong, int id>
struct ArbitraryLazyMontgomeryModIntBase {
  using mint = ArbitraryLazyMontgomeryModIntBase;

  inline static UInt mod;
  inline static UInt r;
  inline static UInt n2;
  static constexpr int bit_length = sizeof(UInt) * 8;

  static UInt get_r() {
    UInt ret = mod;
    while (mod * ret != 1) ret *= UInt(2) - mod * ret;
    return ret;
  }
  static void set_mod(UInt m) {
    assert(m < (UInt(1u) << (bit_length - 2)));
    assert((m & 1) == 1);
    mod = m, n2 = -ULong(m) % m, r = get_r();
  }
  UInt a;

  ArbitraryLazyMontgomeryModIntBase() : a(0) {}
  ArbitraryLazyMontgomeryModIntBase(const Long &b)
      : a(reduce(ULong(b % mod + mod) * n2)){};

  static UInt reduce(const ULong &b) {
    return (b + ULong(UInt(b) * UInt(-r)) * mod) >> bit_length;
  }

  mint &operator+=(const mint &b) {
    if (Int(a += b.a - 2 * mod) < 0) a += 2 * mod;
    return *this;
  }
  mint &operator-=(const mint &b) {
    if (Int(a -= b.a) < 0) a += 2 * mod;
    return *this;
  }
  mint &operator*=(const mint &b) {
    a = reduce(ULong(a) * b.a);
    return *this;
  }
  mint &operator/=(const mint &b) {
    *this *= b.inverse();
    return *this;
  }

  mint operator+(const mint &b) const { return mint(*this) += b; }
  mint operator-(const mint &b) const { return mint(*this) -= b; }
  mint operator*(const mint &b) const { return mint(*this) *= b; }
  mint operator/(const mint &b) const { return mint(*this) /= b; }

  bool operator==(const mint &b) const {
    return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
  }
  bool operator!=(const mint &b) const {
    return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
  }
  mint operator-() const { return mint(0) - mint(*this); }
  mint operator+() const { return mint(*this); }

  mint pow(ULong n) const {
    mint ret(1), mul(*this);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul, n >>= 1;
    }
    return ret;
  }

  friend ostream &operator<<(ostream &os, const mint &b) {
    return os << b.get();
  }

  friend istream &operator>>(istream &is, mint &b) {
    Long t;
    is >> t;
    b = ArbitraryLazyMontgomeryModIntBase(t);
    return (is);
  }

  mint inverse() const {
    Int x = get(), y = get_mod(), u = 1, v = 0;
    while (y > 0) {
      Int t = x / y;
      swap(x -= t * y, y);
      swap(u -= t * v, v);
    }
    return mint{u};
  }

  UInt get() const {
    UInt ret = reduce(a);
    return ret >= mod ? ret - mod : ret;
  }

  static UInt get_mod() { return mod; }
};

// id に適当な乱数を割り当てて使う
template <int id>
using ArbitraryLazyMontgomeryModInt =
    ArbitraryLazyMontgomeryModIntBase<int, unsigned int, long long,
                                      unsigned long long, id>;
template <int id>
using ArbitraryLazyMontgomeryModInt64bit =
    ArbitraryLazyMontgomeryModIntBase<long long, unsigned long long, __int128_t,
                                      __uint128_t, id>;


namespace fast_factorize {

template <typename T, typename U>
bool miller_rabin(const T& n, vector<T> ws) {
  if (n <= 2) return n == 2;
  if (n % 2 == 0) return false;

  T d = n - 1;
  while (d % 2 == 0) d /= 2;
  U e = 1, rev = n - 1;
  for (T w : ws) {
    if (w % n == 0) continue;
    T t = d;
    U y = internal::modpow<T, U>(w, t, n);
    while (t != n - 1 && y != e && y != rev) y = y * y % n, t *= 2;
    if (y != rev && t % 2 == 0) return false;
  }
  return true;
}

bool miller_rabin_u64(unsigned long long n) {
  return miller_rabin<unsigned long long, __uint128_t>(
      n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}

template <typename mint>
bool miller_rabin(unsigned long long n, vector<unsigned long long> ws) {
  if (n <= 2) return n == 2;
  if (n % 2 == 0) return false;

  if (mint::get_mod() != n) mint::set_mod(n);
  unsigned long long d = n - 1;
  while (~d & 1) d >>= 1;
  mint e = 1, rev = n - 1;
  for (unsigned long long w : ws) {
    if (w % n == 0) continue;
    unsigned long long t = d;
    mint y = mint(w).pow(t);
    while (t != n - 1 && y != e && y != rev) y *= y, t *= 2;
    if (y != rev && t % 2 == 0) return false;
  }
  return true;
}

bool is_prime(unsigned long long n) {
  using mint32 = ArbitraryLazyMontgomeryModInt<96229631>;
  using mint64 = ArbitraryLazyMontgomeryModInt64bit<622196072>;

  if (n <= 2) return n == 2;
  if (n % 2 == 0) return false;
  if (n < (1uLL << 30)) {
    return miller_rabin<mint32>(n, {2, 7, 61});
  } else if (n < (1uLL << 62)) {
    return miller_rabin<mint64>(
        n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
  } else {
    return miller_rabin_u64(n);
  }
}

}  // namespace fast_factorize

using fast_factorize::is_prime;

/**
 * @brief Miller-Rabin primality test
 */


using namespace Nyaan;

void q() {
  Timer timer;
  ll p = 0;
  do {
    p = rng(9 * TEN(17), TEN(18));
  } while (!is_prime(p));
  auto modulo = [&](bigint x) -> ll { return (x % p).to_ll(); };

  Matrix<bigint> m(2);
  m[0][0] = m[0][1] = m[1][0] = 1;
  m[1][1] = 0;

  V<Matrix<bigint>> ms;
  ms.push_back(m);
  while (true) {
    auto bc = ms.back();
    bc *= bc;
    if (bc[1][1].dfp().second > 2 * TEN(6) + 10) break;
    ms.push_back(bc);
  }

  trc2(timer());

  // (t 以下の fib のうち最大, 2 番目)
  auto get = [&](bigint t) -> pair<bigint, bigint> {
    int r = 0;
    while (r < sz(ms) and ms[r][0][0] <= t) r++;
    bigint x = 1, y = 0;
    repr(i, r) {
      bigint nx = ms[i][0][0] * x;
      if (nx > t) continue;
      nx += ms[i][0][1] * y;
      if (nx > t) continue;
      bigint ny = ms[i][1][0] * x + ms[i][1][1] * y;
      x = nx, y = ny;
    }
    return {x, y};
  };

#ifdef NyaanLocal
  rep1(t, 1000) {
    auto [x, y] = get(t);
    assert(x <= t and x + y > t);
  }
  trc2("OK");
#endif

  inl(N);
  V<bigint> v(N);
  in(v);
  sort(all(v));

  map<ll, int> mp;
  ll ans = 0;
  each(t, v) {
    auto [x, y] = get(t);
    trc(t, x, y);
    rep(_, 2) {
      bigint z = x + y;
      ans += mp[modulo(z - t)];
      y = x, x = z;
    }
    mp[modulo(t)]++;
  }
  out(ans);

  trc2(timer());
}

void Nyaan::solve() {
  int t = 1;
  // in(t);
  while (t--) q();
}

详细

Test #1:

score: 100
Accepted
time: 666ms
memory: 41712kb

input:

6
50
8
8
5
72
354224848179261915070

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 2539ms
memory: 40260kb

input:

28
200878223506436882933619847964496455022155117513398820563747455993172799881403389571477889821109288771413214004090719097929400406252135763028179112130390003528046316900603668569910008417315162907579003880220844686222148696041857432602133894827753998572080650383305777912447151917272483538029469449...

output:

27

result:

ok 1 number(s): "27"

Test #3:

score: 0
Accepted
time: 993ms
memory: 39864kb

input:

5187
2640352926124261912741724778991366987330659389621881876017670644497364093930668042530271338851702874394631009332660937266680740235862107353443518003194307853104942996827176097428402408674756368623972812842571069642405111849826172879369776309763468485788964245903781380419155348915131587410703749...

output:

6073

result:

ok 1 number(s): "6073"

Test #4:

score: 0
Accepted
time: 858ms
memory: 41836kb

input:

200000
2
2
2
2
1
2
1
1
2
2
1
1
1
2
2
1
1
2
1
1
2
2
1
2
2
2
1
1
1
1
2
2
1
2
1
2
1
1
2
2
1
1
1
2
1
1
2
1
2
2
2
2
1
2
2
1
1
1
2
1
1
1
1
1
2
1
2
2
1
1
1
2
2
2
1
1
2
1
1
2
1
2
1
1
1
2
2
2
1
1
1
1
2
1
2
1
1
2
2
1
1
2
1
1
2
1
2
2
1
2
1
2
2
1
1
2
1
1
1
2
2
2
1
2
2
1
1
2
2
2
2
1
2
1
1
2
1
2
2
1
1
1
1
2
2
2
2...

output:

15003749259

result:

ok 1 number(s): "15003749259"

Test #5:

score: 0
Accepted
time: 1728ms
memory: 67700kb

input:

200000
944176313232170622314
2590599414036674999101
753315073608896000424
9299685298577430049245
9361800333778142620806
8988699166328904060999
9606920674025578304023
4203331868598952026136
5183047027116137697788
3968714342776915029801
8130984095583566992354
3206443643596048048798
6248561214283254355...

output:

0

result:

ok 1 number(s): "0"

Test #6:

score: 0
Accepted
time: 1174ms
memory: 40172kb

input:

200000
9
10
3
5
9
3
3
9
8
5
1
2
7
8
4
6
2
3
3
9
5
5
4
9
7
5
8
2
6
10
9
7
2
2
1
10
10
6
10
7
4
7
9
7
2
2
10
4
5
8
2
2
5
8
9
5
3
9
2
1
7
6
8
8
6
3
8
2
2
9
10
2
9
7
1
9
1
4
5
9
2
7
10
1
8
7
4
8
1
10
6
4
4
9
1
9
7
3
6
5
6
9
5
3
6
6
4
4
6
1
8
6
10
3
10
2
1
4
1
4
8
2
9
1
4
8
10
8
2
2
3
6
4
7
10
10
9
4
7
6...

output:

4388485679

result:

ok 1 number(s): "4388485679"

Test #7:

score: 0
Accepted
time: 1250ms
memory: 66336kb

input:

200000
6828421000391895
1989111434563275
5896525738540342
7580233289915833
7220157112714422
6690072177484914
6664449707566084
8245839001391019
3008772159581769
8148007474169818
9400853099859484
6346860654847919
7403109176990407
2581313740335401
1273038733901266
9824983373567665
7206452987542085
7181...

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 1170ms
memory: 65708kb

input:

200000
163414517
35065810
104946881
686842158
509604537
114869915
194658958
55736013
211143419
526188788
18298540
311113507
727676120
517103071
25044427
38567543
386683792
246028194
750300322
4412101
865997254
674545866
775054146
977862574
699213474
347544102
740489922
632436817
297903184
435135324
...

output:

59

result:

ok 1 number(s): "59"

Test #9:

score: 0
Accepted
time: 1751ms
memory: 41412kb

input:

2
2088564186870382794642016448725374479500907752342156600368614861600912666885211013490310624029649329209019866849808883315545780833167257516031795949145341911463438482795792374909577113387320732207052482556858037878075154734524317145645776084240387870219160545328462016106959746495953786767421892196...

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 1025ms
memory: 40032kb

input:

200000
6
1
3
9
1
8
9
9
2
6
8
6
2
3
9
2
2
7
4
7
8
8
4
8
2
7
8
9
2
9
2
4
4
1
10
6
2
10
2
6
8
3
10
3
6
10
10
10
2
4
6
4
7
8
1
2
1
1
4
10
5
5
4
10
3
8
5
6
1
7
8
1
2
6
3
8
9
9
5
1
9
5
6
10
9
4
1
7
8
3
10
4
3
2
7
7
9
4
5
6
6
7
8
10
6
6
3
6
8
1
7
4
2
6
10
8
4
2
7
4
2
5
4
9
10
5
2
3
2
4
8
7
9
7
7
8
2
5
7
2
...

output:

4400854684

result:

ok 1 number(s): "4400854684"

Test #11:

score: 0
Accepted
time: 1224ms
memory: 66604kb

input:

200000
3118333850638
35270102833223
62994441325054
21050207685515
79452732606523
43405025574846
14676822470608
40589739145551
72610266245240
95906978427970
59399311725881
80286412880911
98171197939601
15555757959003
68766133429050
11529744877477
36884730947747
93994258932707
21245575958503
287958909...

output:

0

result:

ok 1 number(s): "0"

Test #12:

score: 0
Accepted
time: 1134ms
memory: 66260kb

input:

200000
1218982
621720
5848120
1753415
5889366
1747270
7735728
8089704
4279399
7927020
9269797
1332511
6334797
8964092
9525679
7325470
1527918
893049
8483303
1134021
8872739
532622
8977450
4503590
6512507
4903981
4892296
6522908
9237430
2297267
8063244
1546378
5054973
8702942
4392067
7868582
2029729
...

output:

5695

result:

ok 1 number(s): "5695"

Test #13:

score: 0
Accepted
time: 1778ms
memory: 40572kb

input:

2
2088564186870382794642016448725374479500907752342156600368614861600912666885211013490310624029649329209019866849808883315545780833167257516031795949145341911463438482795792374909577113387320732207052482556858037878075154734524317145645776084240387870219160545328462016106959746495953786767421892196...

output:

0

result:

ok 1 number(s): "0"

Test #14:

score: 0
Accepted
time: 2574ms
memory: 40624kb

input:

7
1337338011484742791299410909385691591046809197321138600848517667449672944525104556519885455609314839827342014896149347803816156838828377155724440687227582622225528496005639283622580269360626125544811511998701746678193286138664078007880894120371020695543061391758951301196457121332483784041873539166...

output:

3

result:

ok 1 number(s): "3"

Test #15:

score: 0
Accepted
time: 1673ms
memory: 40852kb

input:

274
36199225654659696764078634911736913237817300779619275513532816361663892134832409526194170532894366762053993742963156407869241123825595148459428450874407641181641292360313933002704706339921470798414371554709977458935038423965022899542511184991008496997550268720067992926078576871685757638601127765...

output:

273

result:

ok 1 number(s): "273"

Test #16:

score: 0
Accepted
time: 1434ms
memory: 42672kb

input:

200000
4
3
8
5
8
9
4
10
1
3
7
1
3
10
1
10
10
7
8
2
8
9
6
6
1
2
2
6
6
7
10
7
1
3
6
2
8
4
3
3
8
9
4
3
9
6
4
1
6
3
3
5
4
2
3
9
3
3
6
7
6
1
5
5
2
10
2
1
5
9
6
7
3
2
9
1
3
8
8
3
10
7
5
5
6
9
10
8
1
5
6
2
1
8
5
4
1
7
9
9
2
8
9
8
5
7
4
9
3
3
4
7
9
1
8
1
5
9
8
8
7
10
1
4
2
3
7
8
6
1
10
10
8
9
4
10
4
5
5
6
9...

output:

4387062637

result:

ok 1 number(s): "4387062637"

Test #17:

score: 0
Accepted
time: 1853ms
memory: 65872kb

input:

200000
8244945625103564139
31587720380738895055
95764870267791202443
90342450187757930095
57990438361916446378
37041843791326956160
92044245094014254241
52147231507776742459
57440162490738372914
75951472709544205529
91095641579841704038
6354859395638708014
13171197741013485755
31875767906879519150
2...

output:

0

result:

ok 1 number(s): "0"

Test #18:

score: 0
Accepted
time: 672ms
memory: 39896kb

input:

10
6
8
6
6
7
6
3
3
2
6

output:

12

result:

ok 1 number(s): "12"

Test #19:

score: 0
Accepted
time: 1763ms
memory: 39980kb

input:

2
2088564186870382794642016448725374479500907752342156600368614861600912666885211013490310624029649329209019866849808883315545780833167257516031795949145341911463438482795792374909577113387320732207052482556858037878075154734524317145645776084240387870219160545328462016106959746495953786767421892196...

output:

0

result:

ok 1 number(s): "0"

Test #20:

score: 0
Accepted
time: 1249ms
memory: 66032kb

input:

200000
51732486464
15203118134
55665354475
37097810807
44823788729
92577384010
20189320156
62707564695
81665154265
89603063623
48003727587
14457078372
37230540002
65288477498
52282695470
76070393338
26054936545
14171092817
61770329497
85319218123
57730830347
20295186479
9036398880
63607160628
825711...

output:

1

result:

ok 1 number(s): "1"

Test #21:

score: 0
Accepted
time: 681ms
memory: 39996kb

input:

1000
7
2
6
10
8
6
1
4
5
4
8
6
9
4
1
5
1
5
2
10
6
8
10
10
1
3
4
2
10
1
9
2
7
6
7
9
10
6
9
8
3
2
10
7
6
5
4
3
1
10
5
3
5
1
8
6
5
10
5
7
10
4
9
1
10
9
4
8
8
7
8
5
9
1
5
6
2
10
1
10
9
10
10
10
1
5
3
10
10
3
3
9
10
3
9
1
5
7
6
5
2
9
7
9
10
4
9
1
7
7
5
8
10
8
8
5
5
6
1
5
5
6
10
2
1
1
2
5
9
5
3
5
6
8
5
3
8...

output:

108128

result:

ok 1 number(s): "108128"

Test #22:

score: 0
Accepted
time: 1495ms
memory: 40688kb

input:

170297
36618903089511909212027904
295898671290484359833820549055
855922209609024693421257591054
104046893712788281969810034913
294974348216094859258128389147
898675289823399842963411259541
849917444544425201790051381287
554091687601993279655091754543
100543835187751461953816001432
324625661878684349...

output:

669637

result:

ok 1 number(s): "669637"

Test #23:

score: 0
Accepted
time: 2248ms
memory: 41256kb

input:

9
1554055664340235444670436446744662342403532554270354440324316254234564540613440405260344004460144314614345467104554712624142524427154124266304046362254623626323466324132625200314136012323044624260020307414632254233433163613166424734133322715601644464634614352434441422431546266431240655123113002704...

output:

0

result:

ok 1 number(s): "0"

Test #24:

score: 0
Accepted
time: 658ms
memory: 41008kb

input:

30
173224810532175
17167616931584
361
605
17167680176960
956658780060
4052737359577
497497353099204
1548072001901
190392490708530
789347852872433
5
804010804445736
139520616464
43988911432793
4052739537276
514224
2178304
25273161431631
53314112869
17114366064696
20097096794
26821231255228
4944012745...

output:

29

result:

ok 1 number(s): "29"

Test #25:

score: 0
Accepted
time: 1814ms
memory: 41008kb

input:

100
11549310117176145486225764017375125851223984720694884717797775426631366931455266419214045399503089615971818090352858567015012529938870819767662704737995190471260542479965705803468920094883954929878415301662741322840828368641397254767329039284292920968364857914289821588505056486091849012400101879...

output:

36

result:

ok 1 number(s): "36"

Test #26:

score: 0
Accepted
time: 1379ms
memory: 44052kb

input:

100223
94009034043768394308211497706411911232935573312371
90700235808140495519523074128684120917303691406421
72874906060637684247409916135076680433361225881761
80161826274205256086415063126094978143520789283159
98145703778166390989463238108464755254200147417281
70995217131009339533392756476859088949...

output:

0

result:

ok 1 number(s): "0"

Test #27:

score: 0
Accepted
time: 663ms
memory: 40364kb

input:

6
50
8
8
5
72
354224848179261915070

output:

4

result:

ok 1 number(s): "4"

Test #28:

score: 0
Accepted
time: 1115ms
memory: 40584kb

input:

3161
7
14
130
1467
16244
105149
1241120
13689232
151890909
1684420994
10901848031
128682014414
1419326741506
15748353436059
101920677024935
1203048867903722
13269285156772499
147231358659594589
1632748057345119600
10567412357776757138
124734439986929988911
1375786096219966094366
15265241654400597567...

output:

3160

result:

ok 1 number(s): "3160"

Test #29:

score: 0
Accepted
time: 1267ms
memory: 66892kb

input:

200000
7930099016
7136448262
4599143849
4725192685
4685680672
739140078
7214691825
5031750793
4820916507
6017675339
485443032
2327198454
8808146518
7746012012
713572475
4706110510
3560774990
7482541413
8975601524
3896030632
3018545943
7048325939
2370597692
7867568189
6902951191
333917381
112842576
9...

output:

7

result:

ok 1 number(s): "7"

Test #30:

score: 0
Accepted
time: 731ms
memory: 40380kb

input:

60123
4
3
4
7
5
7
5
1
2
6
9
10
7
4
2
1
8
6
4
6
4
2
8
6
2
8
5
4
5
7
1
10
7
5
1
9
7
4
8
8
8
5
2
6
8
4
6
4
9
7
3
9
5
6
2
8
10
2
10
2
1
4
9
5
10
9
7
2
1
9
3
9
10
1
8
7
6
5
7
1
4
10
5
9
8
10
4
10
4
9
3
7
4
4
10
4
1
7
4
10
4
9
10
2
2
8
3
7
1
1
6
4
10
9
9
4
8
3
4
7
5
7
6
10
10
2
8
1
8
10
6
9
4
7
3
8
2
5
6
...

output:

399686351

result:

ok 1 number(s): "399686351"

Test #31:

score: 0
Accepted
time: 662ms
memory: 41660kb

input:

20
11142320330634256153203413422244004724022423010341634226101444226235404243251
1510233372263004374041444256322353356243032432623343544033530634305504714430614564334410564323262245
3315442551434205740422347432544540327016564444656542244600440525402604662333366
53153452623340724302644316423336472713...

output:

0

result:

ok 1 number(s): "0"

Test #32:

score: 0
Accepted
time: 661ms
memory: 40480kb

input:

15
9227465
832040
701408733
2178309
267914296
433494437
165580141
1346269
5702887
3524578
102334155
24157817
14930352
63245986
39088169

output:

14

result:

ok 1 number(s): "14"

Test #33:

score: 0
Accepted
time: 762ms
memory: 41252kb

input:

10011
5327909559109070794570420158512927656597532686406620479564191583982981578330651724849734045529811497
9659152635523321620063357842120653540264735554377366787893904211734024058449827205523008852363337860
74727969709789190305111991663528709940303307406256850364862896747520682645094217166643105732...

output:

0

result:

ok 1 number(s): "0"

Test #34:

score: 0
Accepted
time: 1000ms
memory: 40880kb

input:

10051
63063334260332707210045601560460743222655443603043556526226343270234640534370464564114515210165526527443654044521634373434642424304154632545440427364312534131536671541443033313334224226302334143144172200431314323334240461563243422303322351122343066463334623434
625665325411647124616714317265541...

output:

14

result:

ok 1 number(s): "14"

Test #35:

score: 0
Accepted
time: 1345ms
memory: 67168kb

input:

200000
3231427058997
5671035772108
505876205893
9869979702346
336233080766
4805367039084
270125613380
929924360332
6390838551951
1896341268898
3923051450784
397979630166
6527843499305
1937207519921
9355189911971
953387547771
5307619807657
6689006266290
517624961010
1532034993156
1921439567851
331239...

output:

0

result:

ok 1 number(s): "0"

Test #36:

score: 0
Accepted
time: 2060ms
memory: 40732kb

input:

30
167491015938836604073444715975948275020752570351918554475806772549228015468626967999929915531115950274814727218152384400389926950026165552262394643249255747252904223055992443689134599380405599101636105379410012227917206510976118633243994494607279010051579617303878166798657109212106136099974387457...

output:

29

result:

ok 1 number(s): "29"

Test #37:

score: 0
Accepted
time: 1082ms
memory: 40564kb

input:

200000
31520
9835
67679
91981
37157
27950
36846
70635
13880
18818
52443
46788
38014
56271
48270
28452
36146
82523
60850
55346
16869
95814
89245
98640
40746
68625
53391
63023
4402
36521
95532
52344
24072
70060
11619
12227
98964
78211
95010
83216
22122
46697
31271
85556
57237
82689
92115
88247
9186
85...

output:

555586

result:

ok 1 number(s): "555586"

Test #38:

score: 0
Accepted
time: 1751ms
memory: 40948kb

input:

2
7471143542670631923583760838674866685142093708045228091216520373087113961892117195149240140968159205634006625906479367372855893882103887377565868731323681755476477285090435798416695243644387513257156317699123267511524797133211810893688279220755514610253525742595752854587254548452737426517576583616...

output:

1

result:

ok 1 number(s): "1"

Test #39:

score: 0
Accepted
time: 747ms
memory: 40088kb

input:

80000
6
4
5
5
4
5
9
8
5
6
2
2
1
10
6
9
4
10
6
5
3
4
3
3
4
5
10
2
6
4
6
2
6
2
4
7
9
6
6
8
1
1
7
10
10
2
7
2
2
9
8
5
4
9
1
5
7
4
7
7
6
7
7
9
8
9
9
4
10
7
2
9
9
9
4
2
8
4
9
1
3
9
1
4
2
1
2
4
3
2
1
10
5
7
10
5
9
3
6
3
4
4
1
8
1
8
10
8
6
6
2
5
1
3
6
8
2
2
10
6
6
3
2
6
3
8
4
10
8
10
3
9
9
2
8
8
10
4
5
5
7...

output:

706251650

result:

ok 1 number(s): "706251650"

Test #40:

score: 0
Accepted
time: 1447ms
memory: 42732kb

input:

200000
9
1
4
4
5
2
4
9
7
5
3
6
6
8
4
7
2
1
9
10
8
2
1
4
9
3
10
8
1
5
5
8
2
9
3
1
9
3
9
4
9
10
4
5
4
4
2
1
1
7
5
7
7
3
6
8
10
6
4
1
5
2
5
5
9
4
10
2
10
7
9
5
2
7
4
9
7
5
2
1
4
7
6
7
10
9
10
2
10
4
9
1
7
5
7
3
1
4
5
2
6
6
2
4
8
8
7
9
10
4
10
2
1
10
10
5
10
1
1
6
7
8
8
7
5
8
3
8
1
1
10
8
9
10
7
3
8
6
4...

output:

4417250451

result:

ok 1 number(s): "4417250451"

Test #41:

score: 0
Accepted
time: 1195ms
memory: 40956kb

input:

84752
86009844223237105273313186367406421847273312848013100091343
340516459610995530579473198046278412250343444815876655725270
62236463822700922600990709332929319814536375509143833251557
5611500219672931601067284378715174151735452175901717138530
64201778346042476353565735947990316834224189505881
609...

output:

420579

result:

ok 1 number(s): "420579"

Test #42:

score: 0
Accepted
time: 1602ms
memory: 67296kb

input:

200000
7127173784651987052
4249291679502906721
9703708230592019478
4404701921242244700
2344941043578422215
3091914365064271594
9867051863259427168
9880844309023770200
7211977710785226267
1694381065563438860
201683809955321192
4085536489000602058
7553409623903962290
4033981640350364868
54455660173955...

output:

0

result:

ok 1 number(s): "0"

Test #43:

score: 0
Accepted
time: 1540ms
memory: 44316kb

input:

200000
9
9
2
10
3
4
3
9
7
7
8
5
9
9
7
5
8
5
7
1
5
6
3
2
7
5
7
7
2
9
8
6
2
1
8
1
3
4
10
2
3
4
4
7
4
10
8
6
1
5
3
3
3
5
5
8
6
9
3
6
5
4
2
8
10
9
1
5
1
4
8
9
4
3
4
9
10
3
6
2
10
3
3
6
6
7
4
9
5
2
1
8
8
7
308061521170126
7
4
6
1
9
3
9
9
3
1
10
8
7
2
9
10
6
2
6
10
8
5
1
5
1
7
9
5
3
6
1
4
2
6
2
8
5
3
1
6
...

output:

4397248166

result:

ok 1 number(s): "4397248166"

Test #44:

score: 0
Accepted
time: 921ms
memory: 41328kb

input:

156
18459619692692557705784877669569448552986613407875981372394172107449477143544507182981317111359110933094916231296859516709399078435198069511763391151449973008095601542066128297192521457018669738382503324519683244087838172215626103362576668917140635977557324975206273718561053735845026938082217687...

output:

155

result:

ok 1 number(s): "155"

Test #45:

score: 0
Accepted
time: 1422ms
memory: 41564kb

input:

200000
1
10
4
3
10
1
9
5
9
4
9
1
6
6
1
7
2
1
10
3
2
3
4
7
7
3
9
9
10
3
4
10
10
7
7
2
5
10
9
6
8
1
4
4
5
8
8
6
5
10
10
9
10
9
5
1
7
6
5
10
2
4
1
7
10
6
7
8
2
3
3
10
1
7
6
10
2
7
1
9
6
10
8
4
7
3
9
1
6
9
2
3
4
8
7
8
3
6
4
10
2
2
1
9
7
2
2
8
2
1
2
10
5
4
10
9
9
7
9
4
3
10
9
1
2
9
9
2
7
1
6
7
10
6
5
9
6...

output:

4407433502

result:

ok 1 number(s): "4407433502"

Test #46:

score: 0
Accepted
time: 1108ms
memory: 41212kb

input:

51002
376123568879569384290612536925367837315702704676220875375604948366932308891841579226324979782110
28623980260058260408921525210046136035459718869538444006842678034295486291710095655185249062457587
21690449377523978494384257361181223226054780834691728496618681724478608654823982012150023238151530...

output:

81486

result:

ok 1 number(s): "81486"

Test #47:

score: 0
Accepted
time: 1304ms
memory: 67180kb

input:

200000
478606336755874083
603529542039676573
240066379679942455
20635508638460497
945472883349378253
395868479387568634
865948317871000880
136079313625171264
764680881358360622
195117422398549932
143437863196805305
907507515211279442
723479709912499971
671617918537158715
439287855279754360
202716825...

output:

0

result:

ok 1 number(s): "0"

Test #48:

score: 0
Accepted
time: 2283ms
memory: 39808kb

input:

19
114661534643152246311744033174352334643324503262044605562234546544736534426056314403004340112331342520053464440541422433562206354434233744572233143044234304056542423441346156352252422334142225474302135741207345424432300443162054415443457163346015613444533444074633135446264371437171714063445404655...

output:

0

result:

ok 1 number(s): "0"

Test #49:

score: 0
Accepted
time: 1273ms
memory: 66560kb

input:

200000
497856383454
506720870857
899176487457
12145678485
541966940864
272264831455
178825186059
7038707436
481602633783
181735126537
559631305498
335603421321
761406732158
369431205173
615437274239
923671138603
543441698085
733638673698
858564208935
726626729204
880133143653
415511404815
9211110013...

output:

1

result:

ok 1 number(s): "1"

Test #50:

score: 0
Accepted
time: 2480ms
memory: 40068kb

input:

5
2011068126132617886949194530211424837999019187297342375967282498616949073685995418305378991927261698758022155241855161670361072821581948280878066032787805987660111096801265330758292151243775781982581126595354464038574958455139626266660161003165949122588221798586300395825356961553839057885407409810...

output:

4

result:

ok 1 number(s): "4"

Test #51:

score: 0
Accepted
time: 948ms
memory: 41216kb

input:

200000
91
67
28
7
87
97
87
80
71
5
67
1
98
85
60
62
99
46
9
81
10
7
15
91
74
69
11
34
85
47
56
48
29
16
25
5
46
9
73
24
84
10
97
22
78
18
29
70
92
98
61
43
54
66
55
15
77
20
25
16
84
11
93
65
61
91
18
59
31
93
53
33
34
59
90
41
21
27
82
49
33
64
96
18
46
71
94
95
30
62
47
9
62
79
29
28
65
67
32
48
9...

output:

591328867

result:

ok 1 number(s): "591328867"

Extra Test:

score: 0
Extra Test Passed