#include <bits/stdc++.h>

#include <cassert>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using xy = pair<ll, ll>;
using coord = pair<double, double>;
using bs8 = bitset<8>;
using bs16 = bitset<16>;
using bs32 = bitset<32>;
using bs64 = bitset<64>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vvs = vector<vs>;
using vxy = vector<xy>;
using vvxy = vector<vxy>;
using vcoord = vector<coord>;
using vvcoord = vector<vcoord>;
#define rep(var, n) for (ll var = 0; var < (ll)(n); var++)
#define cnt(var, n, m) for (ll var = (n); var <= (ll)(m); var++)
#define rcnt(var, n, m) for (ll var = (n); var >= (ll)(m); var--)
#define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;
#define MOD107 1000000007
#define MOD998 998244353
#define MOD897 897581057
#define MOD880 880803841
#define ZINIT 1

#if __has_include("zout.h")
#include "zout.h"
#else
namespace zz_print {
class dbg {
 public:
  static inline string margin = "", separated = "", indentS = "";
  static inline int hierarchical = 0, topHier = 0, precision = 6;
  static inline bool unprint = false, exponential = false;
  static void setFloat(const int prec, const bool expo) {
    precision = prec;
    exponential = expo;
  }
  template <int hier = 0, int sep = 2, int mgn = 1, typename... Args>
  static void zout(Args&&... args) {}
};
}  // namespace zz_print
using namespace zz_print;
#endif

namespace zz_time {
using Clock = std::chrono::steady_clock;
inline Clock::time_point start_time() {
  static const Clock::time_point st = Clock::now();
  return st;
}
inline ll elapsed_ms() {
  return std::chrono::duration_cast<std::chrono::milliseconds>(Clock::now() - start_time()).count();
}
inline bool within(ll limit_ms) { return (elapsed_ms() < limit_ms); }
inline bool timeout(ll limit_ms) { return (elapsed_ms() >= limit_ms); }
}  // namespace zz_time
using namespace zz_time;

namespace zz_random {
struct Xoshiro256 {
  static inline ull rotl(ull x, int k) { return (x << k) | (x >> (64 - k)); }
  static inline ull splitmix64(ull& x) {
    ull z = (x += 0x9e3779b97f4a7c15ULL);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
    z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
    return z ^ (z >> 31);
  }
  ull s[4];
  explicit Xoshiro256(ull seed = 1) {
    ull x = seed;
    for (size_t i = 0; i < 4; i++) s[i] = splitmix64(x);
  }
  inline ull next() {
    ull res = rotl(s[1] * 5, 7) * 9, t = s[1] << 17;
    s[2] ^= s[0], s[3] ^= s[1], s[1] ^= s[2], s[0] ^= s[3], s[2] ^= t;
    s[3] = rotl(s[3], 45);
    return res;
  }
  inline ull operator()() { return next(); }

  /// integer [0, n)
  inline ll intn(const ll n = 2) { return (ll)(next() % (ull)n); }
  /// integer [l, r]
  inline ll range(const ll l, const ll r) { return l + intn(r - l + 1); }
  /// real (0, 1)
  inline double real() { return (next() >> 11) * (1.0 / (1ULL << 53)); }
  inline double real(const double r) { return real() * r; }
  inline double real(const double l, const double r) { return (l + real() * (r - l)); }
  // Box–Muller 用キャッシュ
  bool has_spare = false;
  double spare;
  /// 標準正規分布 N(0,1)
  inline double normal01() {
    if (has_spare) {
      has_spare = false;
      return spare;
    }
    double u = 0.0, v;
    while (u <= 0.0) u = real();  // (0,1)
    v = real();
    double r = sqrt(-2.0 * log(u)), theta = 2.0 * M_PI * v;
    spare = r * sin(theta), has_spare = true;
    return r * cos(theta);
  }
  /// 正規分布 N(mean, stddev^2)
  inline double normal(const double mean, const double stddev) { return mean + stddev * normal01(); }
};
}  // namespace zz_random
using namespace zz_random;

namespace zz_numeric {
xy gcdEX(ll a, ll b, ll& d) {
  d = abs(b);
  if (a == 0) return xy{0, 1 - 2 * (b < 0)};
  vxy vec;
  vl rvs;
  while (a != 0 || b != 0) {
    rvs.push_back(abs(a) < abs(b));
    if (rvs.back()) swap(a, b);
    if (b == 0) {
      d = abs(a);
      vec.emplace_back(1 - 2 * (a < 0), 0);
      break;
    }
    vec.emplace_back(a, b);
    swap(a, b);
    b %= a;
  }
  if (rvs.back()) swap(vec.back().first, vec.back().second);
  for (size_t i = vec.size() - 1; i > 0; i--) {
    vec[i - 1] = xy{vec[i].second, vec[i].first - (vec[i - 1].first / vec[i - 1].second) * vec[i].second};
    if (rvs[i - 1]) swap(vec[i - 1].first, vec[i - 1].second);
  }
  return vec[0];
}
xy gcdEX(ll a, ll b) {
  ll d;
  return gcdEX(a, b, d);
}
xy gcdEX(xy ab, ll& d) { return gcdEX(ab.first, ab.second, d); }
xy gcdEX(xy ab) { return gcdEX(ab.first, ab.second); }
ll gcd(ll a, ll b) {
  ll d;
  gcdEX(a, b, d);
  return d;
}
ll gcd(xy ab) { return gcd(ab.first, ab.second); }
ll lcm(ll a, ll b) {
  ll d = gcd(a, b);
  return ((a / d) * b);
}
ll lcm(xy ab) { return lcm(ab.first, ab.second); }
ll gcd(vl vec) {
  size_t n = vec.size(), m = 1;
  while (m < n) {
    for (size_t i = 0; (i + m) < n; i += 2 * m) vec[i] = gcd(vec[i], vec[i + m]);
    m <<= 1;
  }
  return vec[0];
}
ll lcm(vl vec) {
  size_t n = vec.size(), m = 1;
  while (m < n) {
    for (size_t i = 0; (i + m) < n; i += 2 * m) vec[i] = lcm(vec[i], vec[i + m]);
    m <<= 1;
  }
  return vec[0];
}
ll modinv(ll x, ll mod) {
  assert(x != 0);
  ll d;
  xy ans = gcdEX(x, mod, d);
  assert(d == 1);
  ans.first %= mod, ans.first += mod & -(ans.first < 0);
  return ans.first;
}
ll modexp(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  if (x == 0) return 0;
  ll ans = 1;
  if (n < 0) {
    x = modinv(x, mod), n *= -1;
  }
  while (n > 0) {
    if (n & 1) ans = (ans * x) % mod;
    x = (x * x) % mod, n >>= 1;
  }
  return ans;
}
}  // namespace zz_numeric
using namespace zz_numeric;

namespace zz_mod {
template <ll mod>
class pp {
 public:
  ll val;
  explicit pp(ll x = 0, bool flush = true) {
    val = x;
    if (flush) val %= mod, val += mod & -(val < 0);
  }
  pp<mod> flip() const { return pp<mod>(((mod - val) & -(val > 0)), false); }
  pp<mod> inv() const { return pp<mod>(modinv(val, mod), false); };
  pp<mod> exp(const ll n) const { return pp<mod>(modexp(val, n, mod), false); };
  pp<mod>& fliped() {
    val = ((mod - val) & -(val > 0));
    return (*this);
  };
  pp<mod>& inved() {
    val = modinv(val, mod);
    return (*this);
  };
  pp<mod>& exped(const ll n) {
    val = modexp(val, n, mod);
    return (*this);
  };

  pp<mod>& operator+=(const ll x) {
    val = ((__int128)val + x) % mod, val += mod & -(val < 0);
    return (*this);
  };
  pp<mod>& operator-=(const ll x) {
    val = ((__int128)val - x) % mod, val += mod & -(val < 0);
    return (*this);
  };
  pp<mod>& operator*=(const ll x) {
    val = ((__int128)val * x) % mod, val += mod & -(val < 0);
    return (*this);
  };
  pp<mod>& operator/=(const ll x) {
    val = ((__int128)val * modinv(x, mod)) % mod, val += mod & -(val < 0);
    return (*this);
  };
  pp<mod>& operator+=(const pp<mod> a) {
    val += a.val, val -= mod & -(val >= mod);
    return (*this);
  };
  pp<mod>& operator-=(const pp<mod> a) {
    val -= a.val, val += mod & -(val < 0);
    return (*this);
  };
  pp<mod>& operator*=(const pp<mod> a) {
    val = ((__int128)val * a.val) % mod;
    return (*this);
  };
  pp<mod>& operator/=(const pp<mod> a) {
    val = ((__int128)val * modinv(a.val, mod)) % mod;
    return (*this);
  };

  friend pp<mod> operator+(pp<mod> a, const ll x) {
    a += x;
    return a;
  }
  friend pp<mod> operator+(const ll x, pp<mod> a) {
    a += x;
    return a;
  }
  friend pp<mod> operator+(pp<mod> a, const pp<mod> b) {
    a += b;
    return a;
  }

  friend pp<mod> operator-(pp<mod> a, const ll x) {
    a -= x;
    return a;
  }
  friend pp<mod> operator-(const ll x, pp<mod> a) {
    a -= x, a.fliped();
    return a;
  }
  friend pp<mod> operator-(pp<mod> a, const pp<mod> b) {
    a -= b;
    return a;
  }

  friend pp<mod> operator*(pp<mod> a, const ll x) {
    a *= x;
    return a;
  }
  friend pp<mod> operator*(const ll x, pp<mod> a) {
    a *= x;
    return a;
  }
  friend pp<mod> operator*(pp<mod> a, const pp<mod> b) {
    a *= b;
    return a;
  }

  friend pp<mod> operator/(pp<mod> a, const ll x) {
    a /= x;
    return a;
  }
  friend pp<mod> operator/(const ll x, pp<mod> a) {
    a.inved() *= x;
    return a;
  }
  friend pp<mod> operator/(pp<mod> a, const pp<mod> b) {
    a /= b;
    return a;
  }
};

template <ll mod>
class modfactor {
 public:
  static inline vl modfactor_invs = vl{}, modfactor_nums = vl{}, modfactor_dens = vl{};
  void set(const size_t n) {
    assert(n >= 1);
    modfactor_invs.resize(n + 1, 1);
    modfactor_nums.resize(n + 1, 1);
    modfactor_dens.resize(n + 1, 1);
    modfactor_invs[0] = 1, modfactor_invs[1] = 1;
    modfactor_nums[0] = 1, modfactor_nums[1] = 1;
    modfactor_dens[0] = 1, modfactor_dens[1] = 1;
    for (size_t i = 2; i <= n; i++) {
      modfactor_nums[i] = ((__int128)modfactor_nums[i - 1] * i) % mod;
      modfactor_invs[i] = (mod - ((__int128)(mod / i) * modfactor_invs[mod % i])) % mod;
      modfactor_invs[i] += mod & -(modfactor_invs[i] < 0);
      modfactor_dens[i] = ((__int128)modfactor_dens[i - 1] * modfactor_invs[i]) % mod;
    }
  }
  modfactor(const size_t n) { set(n); }
  void resize(const size_t n) {
    if (modfactor_invs.size() < (n + 1)) set(n);
  }

  ll inv(const size_t i) const { return modfactor_invs[i]; }
  ll factorial(const size_t i) const { return modfactor_nums[i]; }
  ll factorial_inv(const size_t i) const { return modfactor_dens[i]; }
  ll P(const size_t n, const size_t m) const {
    if (n <= m) return factorial(n);
    return ((__int128)factorial(n) * factorial_inv(n - m)) % mod;
  }
  ll C(const size_t n, const size_t m) const {
    if (n < m) return 1;
    ll den = ((__int128)factorial_inv(n - m) * factorial_inv(m)) % mod;
    return ((__int128)factorial(n) * den) % mod;
  }
};
}  // namespace zz_mod
using namespace zz_mod;

namespace zz_prime {
class prime {
 public:
  static inline vl sieves = vl{};
  static constexpr array<ll, 14> pre_trial_division =
      array<ll, 14>{3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
  static void set(const ll n) {
    sieves = vl(n + 1, 1);
    for (size_t i = 2; i <= n; i++) {
      if (sieves[i] != 1) continue;
      size_t j = 2 * i;
      while (j <= n) {
        if (sieves[j] == 1) sieves[j] = i;
        j += i;
      }
    }
  }
  prime(const size_t n) { set(n); }
  static void resize(const size_t n) {
    if (sieves.size() < (n + 1)) set(n);
  }
  static bool millerRabin(const ll n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if ((n & 1) == 0) return false;
    vl a = vl{2, 7, 61};
    if (n >= 4759123141) a = vl{2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    size_t m = a.size();
    for (size_t i = 0; i < m; i++) {
      if (a[i] >= n) break;
      size_t d = n - 1;
      while ((d & 1) == 0) d >>= 1;
      ll x = 1, b = a[i] % n, c = d;
      while (c > 0) {
        if (c & 1) x = ((__int128)x * b) % n;
        b = ((__int128)b * b) % n, c >>= 1;
      }
      if (x == 1 || x == (n - 1)) continue;
      bool OK = false;
      while (d < (n - 1)) {
        if (x == (n - 1)) {
          OK = true;
          break;
        }
        x = ((__int128)x * x) % n, d <<= 1;
      }
      if (OK) continue;
      return false;
    }
    return true;
  }
  static bool isPrime(const ll x) {
    if (sieves.size() <= x) return millerRabin(x);
    if (x < 2) return false;
    return (sieves[x] == 1);
  }
  static vxy pollardsRho(ll x) {
    if (x < 2) return vxy();
    vl prms;
    Xoshiro256 rnd;
    function<ll(ll, const ll, const ll)> F = [&rnd](ll x, const ll c, const ll m) -> ll {
      return (((__int128)x * x + c) % m);
    };
    function<void(ll)> Pollards = [&rnd, &F, &prms, &Pollards](const ll n) {
      if (n < 2) return;
      if (millerRabin(n)) {
        prms.push_back(n);
        return;
      }
      ll r = sqrtl(n);
      if ((r * r) == n) {
        Pollards(r), Pollards(r);
        return;
      }
      while (true) {
        ll a = rnd.range(2, n - 1), b = a, c = rnd.range(1, n - 1), d = 1, loopCnt = 0;
        do {
          loopCnt++;
          ll e = 1, k = 64;
          while (k > 0) {
            a = F(a, c, n), b = F(F(b, c, n), c, n);
            ll tmp = ((__int128)e * abs(a - b)) % n;
            if (tmp == 0) break;
            e = tmp, k--;
          }
          d = gcd(e, n);
        } while (d == 1 && loopCnt < 20);
        if (loopCnt >= 20) continue;
        if (d != n) {
          Pollards(d), Pollards(n / d);
          return;
        }
      }
    };
    while ((x & 1) == 0) {
      x >>= 1, prms.push_back(2);
    }
    for (size_t i = 0; i < pre_trial_division.size(); i++) {
      if (x < pre_trial_division[i]) break;
      while ((x % pre_trial_division[i]) == 0) {
        x /= pre_trial_division[i];
        prms.push_back(pre_trial_division[i]);
      }
    }
    Pollards(x);
    vxy ans;
    sort(prms.begin(), prms.end());
    for (size_t i = 0; i < prms.size(); i++) {
      if (ans.empty() || ans.back().first != prms[i]) {
        ans.emplace_back(prms[i], 1);
      } else {
        ans.back().second++;
      }
    }
    return ans;
  }
  static vxy factorization(ll x) {
    if (sieves.size() <= x) return pollardsRho(x);
    vl prms;
    if (x < 2) return vxy();
    while (sieves[x] != 1) {
      x /= sieves[x], prms.push_back(sieves[x]);
    }
    if (x != 1) prms.push_back(x);
    sort(prms.begin(), prms.end());
    vxy ans;
    for (size_t i = 0; i < prms.size(); i++) {
      if (ans.empty() || ans.back().first != prms[i]) {
        ans.emplace_back(prms[i], 1);
      } else {
        ans.back().second++;
      }
    }
    return ans;
  }
  static vl divisor(const vxy& fac, const bool srt) {
    vl ans;
    function<void(ll, ll)> func = [&ans, &fac, &func](ll at, ll e) -> void {
      if (at == fac.size()) return;
      ll a = 1;
      for (size_t _i = 0; _i <= fac[at].second; _i++) {
        if (a != 1) ans.push_back(e * a);
        func(at + 1, e * a), a *= fac[at].first;
      }
    };
    func(0, 1);
    if (srt) sort(ans.begin(), ans.end());
    return ans;
  }
  static vl divisor(const ll n, const bool srt) { return divisor(factorization(n), srt); }
};
}  // namespace zz_prime
using namespace zz_prime;

namespace zz_ganer {
ll ganer_prefix(span<xy> vec, const ll mod) {
  size_t n = vec.size();
  for (size_t i = 0; i < n; i++) {
    for (size_t j = 0; j < i; j++) {
      ll d = gcd(vec[i].second, vec[j].second);
      if ((vec[i].first - vec[j].first) % d != 0) return -1;
      vec[i].second /= d, vec[j].second /= d;
      ll di = gcd(vec[i].second, d), dj = d / di;
      do {
        d = gcd(di, dj), di *= d, dj /= d;
      } while (d != 1);
      vec[i].second *= di, vec[j].second *= dj, vec[i].first %= vec[i].second, vec[j].first %= vec[j].second;
    }
  }
  ll lcm_val = 1;
  each(ite, vec) lcm_val = ((__int128)lcm_val * ite->second) % mod;
  return lcm_val;
}
template <ll m = 1>
ll ganer(vxy vec, bool pos = false, bool prefix = true) {
  ll n = vec.size(), mod = m;
  bool zero_possible = true;
  for (size_t i = 0; i < n; i++) {
    if (vec[i].first > 0) {
      zero_possible = false;
      break;
    }
  }
  if (prefix) {
    ll pre_ans = ganer_prefix(vec, m);
    if (pre_ans == -1) return -1;
    if (pos && zero_possible) return pre_ans;
  }
  if (n == 0) return -1;
  if (mod <= 1) {
    mod = 1;
    for (size_t i = 0; i < n; i++) mod *= vec[i].second;
  }
  vl coef(n + 1, 1), cval(n + 1, 0);
  vec.emplace_back(0, mod);
  for (size_t i = 0; i < n; i++) {
    ll r = vec[i].first, p = vec[i].second;
    // xy ans = gcdEX(coef[i], p);
    // ll ta = (r - cval[i]) % p, tb = ans.first % p;
    ll ta = (r - cval[i]) % p, tb = modinv(coef[i], p);
    ta += p & -(ta < 0), tb += p & -(tb < 0);
    ll t = ((__int128)ta * tb) % p;
    cnt(j, i + 1, n) {
      cval[j] = (cval[j] + (__int128)t * coef[j]) % vec[j].second;
      coef[j] = ((__int128)coef[j] * p) % vec[j].second;
    }
  }
  return cval.back();
}
}  // namespace zz_ganer
using namespace zz_ganer;

namespace zz_poly {
template <const ll mod = 998244353>
class poly {
 public:
  vl fps;
  static inline size_t show_size = 7;
  static inline constexpr array<array<array<ll, 24>, 2>, 3> roots = array<array<array<ll, 24>, 2>, 3>{
      array<array<ll, 24>, 2>{
          array<ll, 24>{1,         998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469,
                        476477967, 166035806, 258648936, 584193783, 63912897,  350007156, 666702199, 968855178,
                        629671588, 24514907,  996173970, 363395222, 565042129, 733596141, 267099868, 15311432},
          array<ll, 24>{1,         998244352, 86583718,  509520358, 337190230, 87557064,  609441965, 135236158,
                        304459705, 685443576, 381598368, 335559352, 129292727, 358024708, 814576206, 708402881,
                        283043518, 3707709,   121392023, 704923114, 950391366, 428961804, 382752275, 469870224}},
      array<array<ll, 24>, 2>{
          array<ll, 24>{1,         897581056, 200527991, 850960045, 227655573, 685177417, 661961559, 717889083,
                        688546301, 64431346,  762907769, 781659575, 604882016, 471181658, 242773703, 313099125,
                        288794207, 732004569, 437566725, 430897771, 279727937, 91704119,  523358721, 872686320},
          array<ll, 24>{1,         897581056, 697053066, 442470459, 502631723, 192192108, 366473218, 285218810,
                        627498913, 632928577, 715124372, 829482092, 895669752, 835819291, 210274124, 7242324,
                        530138839, 365592405, 712687518, 812501856, 244025573, 353112847, 793229247, 354917575}},
      array<array<ll, 24>, 2>{
          array<ll, 24>{1,         880803840, 121444121, 547680885, 836988352, 170630252, 547743738, 390590270,
                        755881750, 119481987, 622213777, 634844223, 496183605, 872875137, 41469254,  551868471,
                        219288049, 198000217, 579409128, 733691905, 566136041, 374515633, 402082372, 273508579},
          array<ll, 24>{1,         880803840, 759359720, 339414624, 282082127, 83908436,  623501316, 879302015,
                        26105166,  708522529, 769895303, 843755407, 710708181, 623500536, 528308065, 542164623,
                        817679620, 571049407, 409417309, 504998132, 352282463, 252040680, 400443141, 109748732}}};
  friend std::ostream& operator<<(std::ostream& os, poly<mod>& ply) {
    string s = "[ ";
    size_t n = min<size_t>(ply.size(), show_size);
    for (size_t i = 0; i < n; i++) s += " " + to_string(ply[i]) + " ";
    if (n < ply.size()) s += " ~ ";
    return os << s << " ]";
  }
  const ll at(const size_t n) const {
    assert(n < size());
    return fps[n];
  }
  ll& at(const size_t n) {
    assert(n < size());
    return fps[n];
  }
  const ll operator[](const size_t n) const { return at(n); }
  ll& operator[](const size_t n) { return at(n); }
  poly<mod>& shift(const ll m) {
    if (m == 0) return (*this);
    ll n = size();
    if (m > 0) {
      vl vec(n + m, 0);
      for (size_t i = 0; i < n; i++) vec[i + m] = fps[i];
      swap(vec, fps);
    } else if (n > -m) {
      n += m;
      vl vec(n, 0);
      for (size_t i = 0; i < n; i++) vec[i] = fps[-m + i];
      swap(vec, fps);
    } else {
      fps.clear();
    }
    return (*this);
  }
  const size_t degree() const { return max<ll>(0, fps.size() - 1); }
  const size_t size() const { return fps.size(); }
  poly<mod>& resize(const size_t n, const ll elm = 0) {
    fps.resize(n, elm);
    return (*this);
  }
  poly<mod>& redegree(const size_t n, const ll elm = 0) {
    fps.resize(n + 1, elm);
    return (*this);
  }
  poly<mod>& shrink() {
    size_t n = size();
    while (n > 0 && at(n - 1) == 0) n--;
    resize(n);
    return (*this);
  }
  poly(size_t n = 0, const ll elm = 0) { resize(n, elm); }
  explicit poly(span<const ll> vec) {
    ll n = vec.size();
    resize(n);
    for (size_t i = 0; i < n; i++) at(i) += vec[i];
  }
  static ll getModType() {
    if (mod == MOD998) return 0;
    if (mod == MOD897) return 1;
    if (mod == MOD880) return 2;
    return -1;
  }

  poly<mod>& flip() {
    size_t n = size();
    for (size_t i = 0; i < n; i++) fps[i] = (fps[i] ? mod - fps[i] : 0);
    return (*this);
  }

  poly<mod>& operator+=(span<const ll> ply) {
    size_t n = ply.size();
    if (size() < n) resize(n);
    for (size_t i = 0; i < n; i++) {
      fps[i] += ply[i];
      if (fps[i] >= mod) fps[i] -= mod;
    }
    return (*this);
  }
  poly<mod>& operator+=(const poly<mod>& ply) { return ((*this) += ply.fps); }
  friend poly<mod> operator+(poly<mod> plyA, span<const ll> plyB) { return (plyA += plyB); }
  friend poly<mod> operator+(span<const ll> plyA, poly<mod> plyB) { return (plyB += plyA); }
  friend poly<mod> operator+(poly<mod> plyA, const poly<mod>& plyB) { return (plyA += plyB); }

  poly<mod>& operator-=(span<const ll> ply) {
    size_t n = ply.size();
    if (size() < n) resize(n);
    for (size_t i = 0; i < n; i++) {
      fps[i] -= ply[i];
      if (fps[i] < 0) fps[i] += mod;
    }
    return (*this);
  }
  poly<mod>& operator-=(const poly<mod>& ply) { return ((*this) -= ply.fps); }
  friend poly<mod> operator-(poly<mod> plyA, span<const ll> plyB) { return (plyA -= plyB); }
  friend poly<mod> operator-(const vl& plyA, const poly<mod>& plyB) { return (poly<mod>(plyA) -= plyB.fps); }
  friend poly<mod> operator-(poly<mod> plyA, const poly<mod>& plyB) { return (plyA -= plyB.fps); }
  static void furie2_bit_rev(span<ll> a) {
    size_t n = a.size();
    for (size_t i = 1, j = 0; i < n; i++) {
      size_t bit = (n >> 1);
      for (; j & bit; bit >>= 1) j ^= bit;
      j |= bit;
      if (i < j) swap(a[i], a[j]);
    }
  }
  static void furie2_buttfly(span<ll> a, bool rvs = false) {
    ll typ = getModType(), n = a.size(), Rt, tmp;
    for (size_t m = 1, b = 1; m < n; m <<= 1, b++) {
      for (size_t i = 0; i < n; i += (m << 1)) {
        Rt = 1;
        for (size_t j = 0; j < m; j++) {
          //      dbg::zout("m=", m, j, roots[typ][rvs][b], Rt);
          tmp = (a[i + j + m] * Rt) % mod;
          //    dbg::zout("  a=", a[i + j], a[i + j + m], tmp);
          a[i + j + m] = a[i + j] + (mod - tmp), a[i + j + m] -= mod & -(a[i + j + m] >= mod);
          a[i + j] += tmp, a[i + j] -= mod & -(a[i + j] >= mod);
          //  dbg::zout("  a=", a[i + j], a[i + j + m]);
          Rt = (Rt * roots[typ][rvs][b]) % mod;
        }
      }
    }

    if (rvs) {
      n = a.size();
      ll nInv = modinv(n, mod);
      for (size_t i = 0; i < n; i++) a[i] = (a[i] * nInv) % mod;
    }
    return;
  }

  void conv_normal(vl a, vl b, vl& c) {
    assert(mod == 998244353 || mod == 897581057 || mod == 880803841);
    c.clear();
    size_t n = (a.size() + b.size()), m = 1, blen = 0;
    if (n == 0) return;
    while (m < n) {
      m <<= 1, blen++;
    }
    a.resize(m), b.resize(m);
    furie2_bit_rev(a), furie2_bit_rev(b);
    furie2_buttfly(a), furie2_buttfly(b);
    c.resize(m);
    for (size_t i = 0; i < m; i++) c[i] = ((__int128)a[i] * b[i]) % mod;
    furie2_bit_rev(c);
    furie2_buttfly(c, true), c.resize(n - 1);
  }
  void conv_ganer(vl a998, vl b998, vl& c) {
    c.clear();
    size_t n = (a998.size() + b998.size()), m = 1, blen = 0;
    if (n == 0) return;
    while (m < n) {
      m <<= 1, blen++;
    }
    a998.resize(m), b998.resize(m);
    poly<mod>::furie2_bit_rev(a998), poly<mod>::furie2_bit_rev(b998);
    vl a897(m), b897(m), a880(m), b880(m);
    copy(a998.begin(), a998.end(), a897.begin());
    copy(b998.begin(), b998.end(), b897.begin());
    copy(a998.begin(), a998.end(), a880.begin());
    copy(b998.begin(), b998.end(), b880.begin());
    poly<MOD998>::furie2_buttfly(a998);
    poly<MOD998>::furie2_buttfly(b998);
    poly<MOD897>::furie2_buttfly(a897);
    poly<MOD897>::furie2_buttfly(b897);
    poly<MOD880>::furie2_buttfly(a880);
    poly<MOD880>::furie2_buttfly(b880);
    vvl C(3, vl(m));
    for (size_t i = 0; i < m; i++) {
      C[0][i] = ((__int128)a998[i] * b998[i]) % MOD998;
      C[1][i] = ((__int128)a897[i] * b897[i]) % MOD897;
      C[2][i] = ((__int128)a880[i] * b880[i]) % MOD880;
    }
    poly<mod>::furie2_bit_rev(C[0]);
    poly<MOD998>::furie2_buttfly(C[0], true);
    C[0].resize(n - 1);
    poly<mod>::furie2_bit_rev(C[1]);
    poly<MOD897>::furie2_buttfly(C[1], true);
    C[1].resize(n - 1);
    poly<mod>::furie2_bit_rev(C[2]);
    poly<MOD880>::furie2_buttfly(C[2], true);
    C[2].resize(n - 1);
    c.resize(n - 1);
    for (size_t i = 0; i < (n - 1); i++) {
      c[i] = ganer<mod>(vxy{xy{C[0][i], MOD998}, xy{C[1][i], MOD897}, xy{C[2][i], MOD880}}, false, false);
    }
  }

  void prod(const vl& a, const vl& b, vl& c) {
    size_t n = a.size(), m = b.size();
    bool naive_flg = (min<size_t>(n, m) <= 65);
    //    naive_flg = false;
    if (naive_flg) {
      vl d(n + m - 1, 0);
      for (size_t i = 0; i < n; i++)
        for (size_t j = 0; j < m; j++) d[i + j] = (d[i + j] + (__int128)a[i] * b[j]) % mod;
      swap(d, c);
    } else if (getModType() != -1)
      conv_normal(a, b, c);
    else
      conv_ganer(a, b, c);
  }

  poly<mod>& operator*=(const ll x) {
    size_t n = size();
    for (size_t i = 0; i < n; i++) fps[i] = ((__int128)fps[i] * x) % mod;
    return (*this);
  }
  friend poly<mod> operator*(poly<mod> plyA, const ll x) { return (plyA *= x); }
  friend poly<mod> operator*(const ll x, poly<mod> plyA) { return (plyA *= x); }

  poly<mod>& operator*=(const vl& plyA) {
    prod(fps, plyA, fps);
    return (*this);
  }
  poly<mod>& operator*=(const poly<mod>& plyA) {
    prod(fps, plyA.fps, fps);
    return (*this);
  }

  friend poly<mod> operator*(poly<mod> plyA, const vl& x) { return (plyA *= x); }
  friend poly<mod> operator*(const vl& x, poly<mod> plyA) { return (plyA *= x); }
  friend poly<mod> operator*(poly<mod> plyA, const poly<mod>& plyB) { return (plyA *= plyB); }

  poly<mod> inv() const {
    //  dbg::zout("fps=", fps);
    assert(!fps.empty() && fps[0]);
    size_t n = size();
    poly<mod> plyG(1, modinv(fps[0], mod));
    poly<mod> ply2_FG;
    size_t m = 1;
    vl plyF(1, fps[0]);
    while (m < n) {
      m <<= 1;
      if (m > n) m = n;
      if (plyF.size() < m) {
        plyF.resize(m);
        for (size_t i = plyG.size(); i < m; i++) plyF[i] = fps[i];
      }
      //      dbg::zout("m=", m);
      plyF.resize(m), plyG.resize(m, 0);
      //      dbg::zout("plyF=", plyF);
      //     dbg::zout("plyG=", plyG.fps);
      ply2_FG = plyF * plyG;
      ply2_FG.resize(m);
      //    dbg::zout("ply2_FG=", ply2_FG.fps);

      ply2_FG.flip();
      ply2_FG.fps[0] += 2;
      if (ply2_FG.fps[0] >= mod) ply2_FG.fps[0] -= mod;
      //  dbg::zout("ply2_FG=", ply2_FG.fps);
      plyG *= ply2_FG;
      plyG.resize(m);
    }
    return plyG;
  }

  poly<mod>& operator/=(ll x) {
    x = modinv(x, mod);
    return ((*this) *= x);
  }
  friend poly<mod> operator/(poly<mod> plyA, const ll x) { return (plyA /= x); }

  poly<mod>& operator/=(const poly<mod>& plyA) { return ((*this) *= plyA.inv()); }
  friend poly<mod> operator/(poly<mod> plyA, const poly<mod>& plyB) { return (plyA /= plyB); }

  poly<mod> differential() const {
    size_t n = size();
    poly<mod> ply;
    if (n == 0) return ply;
    ply.resize(n - 1);
    for (size_t i = 0; i < n - 1; i++) ply.fps[i] = ((__int128)fps[i + 1] * (i + 1)) % mod;
    return ply;
  }
  poly<mod> integral() const {
    poly<mod> ply(1, 0);
    ll n = size();
    ply.resize(n + 1);
    for (size_t i = 0; i < n; i++) ply.fps[i + 1] = ((__int128)fps[i] * modinv(i + 1, mod)) % mod;
    return ply;
  }

  poly<mod> log() {
    assert(!fps.empty() && fps[0] == 1);
    poly<mod> plyF = differential() / (*this);
    plyF.resize(size());
    plyF = plyF.integral();
    plyF.resize(size());
    return plyF;
  }
  poly<mod> exp() {
    assert(!fps.empty() && fps[0] == 0);
    poly<mod> plyG(1, 1), plyF;
    while (plyG.size() < size()) {
      plyG.resize(min<ll>(plyG.size() * 2, size()));
      while (plyF.size() < plyG.size()) plyF.fps.push_back(fps[plyF.size()]);
      poly<mod> ply1F_G = (plyF - plyG.log());
      ply1F_G.fps[0]++;
      if (ply1F_G.fps[0] >= mod) ply1F_G.fps[0] -= mod;

      plyG = plyG * ply1F_G;
      plyG.resize(plyF.size());
    }
    return plyG;
  }

  vector<poly<mod>> get_quotientRemainder(const poly<mod>& plyB) const {
    ll n = size(), m = plyB.size();
    vector<poly<mod>> plys(2);
    if (n < m) {
      plys[1] = *this;
      return plys;
    }
    poly<mod> RplyA, RplyB;
    reach(ite, fps) RplyA.fps.push_back(*ite);
    reach(ite, plyB.fps) RplyB.fps.push_back(*ite);
    RplyA.resize(n - m + 1, 0), RplyB.resize(n - m + 1, 0);
    poly<mod> Rply3 = (RplyA / RplyB);
    Rply3.resize(n - m + 1);
    for (size_t i = 0; i < n - m + 1; i++) plys[0].fps.push_back(Rply3[n - m - i]);
    poly<mod> ply3 = plyB * plys[0];
    plys[1] = (this->fps - ply3);
    plys[1].resize(m - 1);
    return plys;
  }

  ll get_bostanMori(poly<mod> plyD, ll n) {
    assert(plyD.size() > 0);

    poly<mod> plyH;
    poly<mod> plyN = (*this);
    plyN.resize(plyD.size());
    while (n) {
      plyH = plyD;
      ll m = plyH.size() / 2;
      for (size_t i = 0; i < m; i++) plyH[2 * i + 1] = (plyD[2 * i + 1] != 0 ? mod - plyD[2 * i + 1] : 0);
      plyN *= plyH;
      plyD = plyD * plyH;
      plyH.resize((plyD.size() + 1) / 2);
      for (size_t i = 0; i < plyH.size(); i++) plyH[i] = plyD[2 * i];
      swap(plyD, plyH);
      if (n % 2 == 0) {
        plyH.resize((plyN.size() + 1) / 2);
        for (size_t i = 0; i < plyH.size(); i++) plyH[i] = plyN[2 * i];
      } else {
        plyH.resize(plyN.size() / 2);
        for (size_t i = 0; i < plyH.size(); i++) plyH[i] = plyN[2 * i + 1];
      }
      swap(plyH, plyN);
      n >>= 1;
    }
    return ((__int128)plyN[0] * modinv(plyD[0], mod)) % mod;
  }

  poly<mod>& pow(ll k) {
    if (k == 0) {
      fps = vl(size(), 0);
      fps[0] = 1;
      return (*this);
    }
    size_t n = size();
    ll m = 0;
    for (size_t i = 0; i < n; i++) {
      if (fps[i] != 0) break;
      m++;
    }
    if (n == m) return (*this);

    // dbg::zout(vl{(ll)n, m});
    ll a = fps[m];
    //   dbg::zout(n, m, a, fps);
    shift(-m);
    //    dbg::zout(n, m, a, fps);
    if (a != 1) (*this) /= a;

    *this = ((*this).log() * k).exp();

    if (a != 1) {
      a = modexp(a, k, mod);
      (*this) *= a;
    }
    shift(m * k);
    resize(n);
    return *this;
  }
};
}  // namespace zz_poly
using namespace zz_poly;

namespace zz_segtree {
template <typename S>
class segtree {
 public:
  const size_t N;
  vector<S> vecS;
  size_t head;
  bool getyet = true;
  void build() {
    size_t l = head >> 1, r = (head + N - 1) >> 1;
    while (l > 0) {
      for (size_t i = l; i <= r; i++) vecS[i] = vecS[i << 1] * vecS[(i << 1) + 1];
      l >>= 1, r >>= 1;
    }
  }
  segtree(const size_t n) : N(n) {
    head = 1;
    while (head < N) head <<= 1;
    vecS = vector<S>(head << 1, S::e());
    for (size_t i = 0; i < head; i++) vecS[i + head] = S::init();
  }
  template <typename... Arg>
  S s(Arg... arg) {
    return S(arg...);
  }
  void setS(size_t i, const S s) {
    assert(i < N);
    i += head;
    vecS[i] = s;
    if (getyet) return;
    i >>= 1;
    while (i > 0) {
      vecS[i] = vecS[i << 1] * vecS[(i << 1) + 1];
      i >>= 1;
    }
  }
  S get(size_t l, size_t r) {
    assert(l <= r && r <= N);
    if (l == r) return S::e();
    if (getyet) {
      getyet = false, build();
    }
    S ans_l = S::e(), ans_r = S::e();
    l += head, r += head;
    while (l < r) {
      if (l & 1) ans_l &= vecS[l++];
      if (r & 1) ans_r *= vecS[--r];
      l >>= 1, r >>= 1;
    }
    return (ans_l * ans_r);
  }
};
template <typename S, typename F>
class lazy_segtree {
 public:
  const size_t N;
  vector<S> vecS;
  vector<F> vecF;
  size_t head, Nb;
  bool fyet = true;

 private:
  void update(const size_t i, const F add) {
    vecS[i] *= add;
    if (i < head) vecF[i] *= add;
  }
  void updates(size_t l, size_t r, const F add) {
    l += head, r += head;
    while (l < r) {
      if (l & 1) update(l++, add);
      if (r & 1) update(--r, add);
      l >>= 1, r >>= 1;
    }
  }
  S calc(size_t l, size_t r) {
    l += head, r += head;
    S ans_l = S::e(), ans_r = S::e();
    while (l < r) {
      if (l & 1) ans_l &= vecS[l++];
      if (r & 1) ans_r *= vecS[--r];
      l >>= 1, r >>= 1;
    }
    return (ans_l * ans_r);
  }
  void give(const size_t i) {
    update(i << 1, vecF[i]), update((i << 1) + 1, vecF[i]);
    vecF[i] = F::id();
  }
  void gives(size_t l, size_t r) {
    l += head, r += head;
    for (size_t i = Nb; i > 0; i--) {
      if (((l >> i) << i) != l) give(l >> i);
      if (((r >> i) << i) != r) give(r >> i);
    }
  }
  void collect(const size_t i) {
    if (i < head) vecS[i] = vecS[i << 1] * vecS[(i << 1) + 1];
  }
  void collects(size_t l, size_t r) {
    l += head, r += head;
    for (size_t i = 1; i <= Nb; i++) {
      if (((l >> i) << i) != l) collect(l >> i);
      if (((r >> i) << i) != r) collect(r >> i);
    }
  }

 public:
  void build() {
    size_t l = head >> 1, r = (head + N - 1) >> 1;
    while (l > 0) {
      for (size_t i = l; i <= r; i++) vecS[i] = vecS[i << 1] * vecS[(i << 1) + 1];
      l >>= 1, r >>= 1;
    }
  }
  void setS(const size_t at, const S s) {
    assert(at < N);
    if (fyet) {
      vecS[at + head] = s;
      return;
    }
    gives(at, at + 1);
    vecS[at + head] = s;
    collects(at, at + 1);
  }
  void setF(const size_t l, const size_t r, const F f) {
    assert(l < r && r <= N);
    if (fyet) {
      fyet = false, build();
    }
    gives(l, r);
    updates(l, r, f);
    collects(l, r);
  }
  S get(const size_t l, const size_t r) {
    assert(l <= r && r <= N);
    if (l == r) return S::e();
    if (fyet) {
      fyet = false, build();
    }
    gives(l, r);
    return calc(l, r);
  }
  lazy_segtree(const size_t _N) : N(_N) {
    Nb = 0;
    while ((1 << Nb) < N) Nb++;
    head = (1 << Nb);
    vecS = vector<S>(head << 1, S::e());
    vecF = vector<F>(head, F::id());
    for (size_t i = 0; i < head; i++) vecS[i + head] = S::init();
  }
  template <typename... Arg>
  S s(Arg... arg) {
    return S(arg...);
  }
  template <typename... Arg>
  F f(Arg... arg) {
    return F(arg...);
  }
};

struct F_affine {
  ll a, b;
  F_affine(const ll _a = 1, const ll _b = 0) : a(_a), b(_b) {}
  static constexpr F_affine id() noexcept { return F_affine(); };
  F_affine operator*=(const F_affine add) {
    a *= add.a, b = add.a * b + add.b;
    return (*this);
  }
};

struct S_min {
  ll val;
  S_min(const ll _val = LONG_LONG_MAX) : val(_val) {}
  static constexpr S_min e() noexcept { return S_min(); };
  static constexpr S_min init() noexcept { return S_min(); };
  S_min& operator*=(const F_affine add) {
    val = add.a * val + add.b;
    return (*this);
  }
  S_min& operator*=(const S_min add) {
    val = min<ll>(val, add.val);
    return (*this);
  }
  S_min& operator&=(const S_min old) {
    val = min<ll>(val, old.val);
    return (*this);
  }
  friend S_min operator*(const S_min add, S_min s) {
    s *= add;
    return s;
  }
};
struct S_max {
  ll val;
  S_max(const ll _val = -LONG_LONG_MAX) : val(_val) {}
  static constexpr S_max e() noexcept { return S_max(); };
  static constexpr S_max init() noexcept { return S_max(); };
  S_max& operator*=(const F_affine add) {
    val = add.a * val + add.b;
    return (*this);
  }
  S_max& operator*=(const S_max add) {
    val = max<ll>(val, add.val);
    return (*this);
  }
  S_max& operator&=(const S_max old) {
    val = max<ll>(val, old.val);
    return (*this);
  }
  friend S_max operator*(const S_max add, S_max s) {
    s *= add;
    return s;
  }
};
struct S_sum {
  ll val, len;
  S_sum(const ll _val = 0, const ll _len = 0) : val(_val), len(_len) {}
  static constexpr S_sum e() noexcept { return S_sum(); };
  static constexpr S_sum init() noexcept { return S_sum(0, 1); };
  S_sum& operator*=(const F_affine add) {
    val = add.a * val + add.b * len;
    return (*this);
  }
  S_sum& operator*=(const S_sum add) {
    val += add.val, len += add.len;
    return (*this);
  }
  S_sum& operator&=(const S_sum old) {
    val += old.val, len += old.len;
    return (*this);
  }
  friend S_sum operator*(const S_sum add, S_sum s) {
    s *= add;
    return s;
  }
};
struct F_affineMOD998 {
  ll a, b;
  F_affineMOD998(const ll _a = 1, const ll _b = 0) : a(_a), b(_b) {}
  static constexpr F_affineMOD998 id() noexcept { return F_affineMOD998(); };
  F_affineMOD998 operator*=(const F_affineMOD998 add) {
    a = (a * add.a) % MOD998, b = ((__int128)add.a * b + add.b) % MOD998;
    return (*this);
  }
};
struct S_sumMOD998 {
  ll val, len;
  S_sumMOD998(const ll _val = 0, const ll _len = 0) : val(_val), len(_len) {}
  static constexpr S_sumMOD998 e() noexcept { return S_sumMOD998(); };
  static constexpr S_sumMOD998 init() noexcept { return S_sumMOD998(0, 1); };
  S_sumMOD998& operator*=(const F_affineMOD998 add) {
    val = ((__int128)add.a * val + (__int128)add.b * len) % MOD998;
    return (*this);
  }
  S_sumMOD998& operator*=(const S_sumMOD998 add) {
    val += add.val, val -= MOD998 & -(val >= MOD998);
    len += add.len, len -= MOD998 & -(len >= MOD998);
    return (*this);
  }
  S_sumMOD998& operator&=(const S_sumMOD998 old) {
    val += old.val, val -= MOD998 & -(val >= MOD998);
    len += old.len, len -= MOD998 & -(len >= MOD998);
    return (*this);
  }
  friend S_sumMOD998 operator*(const S_sumMOD998 add, S_sumMOD998 s) {
    s *= add;
    return s;
  }
};
struct F_linerMOD998 {
  ll n, r;
  bool on;
  F_linerMOD998(const ll _n = 1, const ll _r = 0, const bool _on = false) : n(_n), r(_r), on(_on) {}
  static constexpr F_linerMOD998 id() noexcept { return F_linerMOD998(); };
  F_linerMOD998 operator*=(const F_linerMOD998 add) {
    if (add.on) {
      n = add.n, r = add.r, on = true;
    }
    return (*this);
  }
};
struct S_linerMOD998 {
  ll n, r, len;
  S_linerMOD998(const ll _n = 1, const ll _r = 0, const ll _len = 0) : n(_n), r(_r), len(_len) {}
  static constexpr S_linerMOD998 e() noexcept { return S_linerMOD998(); };
  static constexpr S_linerMOD998 init() noexcept { return S_linerMOD998(1, 0, 1); };
  S_linerMOD998& operator*=(const F_linerMOD998 add) {
    //  dbg::zout("  | S{", n, r, len, "} *=F{", add.n, add.r, add.on, "}");
    if (!add.on) return (*this);
    if (len == 1 || add.n == 0) {
      n = add.n;
      r = add.r;
      return (*this);
    } else if (add.n == 1) {
      n = 1;
      r = (len * add.r) % MOD998;
      return (*this);
    }
    n = modexp(add.n, len, MOD998);
    ll num = ((MOD998 + 1 - modexp(add.n, len, MOD998)) * add.r) % MOD998;
    ll den = MOD998 + 1 - add.n;
    //    dbg::zout("      | num/den=", num, den);
    r = (num * modinv(den, MOD998)) % MOD998;
    return (*this);
  }
  S_linerMOD998& operator*=(const S_linerMOD998 add) {
    r = (r + (__int128)n * add.r) % MOD998, n = ((__int128)n * add.n) % MOD998;
    len += add.len;
    return (*this);
  }
  S_linerMOD998& operator&=(const S_linerMOD998 old) {
    n = ((__int128)old.n * n) % MOD998, r = (old.r + (__int128)old.n * r) % MOD998;
    len += old.len;
    return (*this);
  }
  friend S_linerMOD998 operator*(const S_linerMOD998 add, S_linerMOD998 s) {
    s *= add;
    return s;
  }
  ll func(const ll x) { return ((__int128)n * x + r) % MOD998; };
};

using segtree_min = segtree<S_min>;
using segtree_max = segtree<S_max>;
using segtree_sum = segtree<S_sum>;
using segtree_sumMOD998 = segtree<S_sumMOD998>;
using segtree_linerMOD998 = segtree<S_linerMOD998>;
using lazy_segtree_min = lazy_segtree<S_min, F_affine>;
using lazy_segtree_max = lazy_segtree<S_max, F_affine>;
using lazy_segtree_sum = lazy_segtree<S_sum, F_affine>;
using lazy_segtree_sumMOD998 = lazy_segtree<S_sumMOD998, F_affineMOD998>;
using lazy_segtree_linerMOD998 = lazy_segtree<S_linerMOD998, F_linerMOD998>;
}  // namespace zz_segtree
using namespace zz_segtree;

/////////////////////////////////////////////////

int main() {
  // dbg::unprint = true;

  ll N;
  cin >> N;
  vl A(N);
  rep(i, N) cin >> A[i];

  vl ans(N, 0), ans2(N, 0);
  vl ans3(N, 0), ans4(N, 0);
  vl token(N, 0);
  rep(i, N) {
    if (token[i] == 1) continue;
    ll at = i;
    token[at] = 1;
    ll nxt_at = A[at] - 1;
    vl vec(1, at);
    while (token[nxt_at] == 0) {
      vec.push_back(nxt_at);
      at = nxt_at;
      token[at] = 1;
      nxt_at = A[at] - 1;
    }
    if (vec.size() == 1) continue;
    vec.push_back(i);
    ll M = vec.size() - 1;
    set<ll> SET, SET2;
    rep(j, M) {
      ll E = abs(vec[j] - vec[j + 1]);
      SET.emplace(E);
      ans[E]++;
    }
    each(ite, SET) {
      vl ds = prime::divisor(*ite, false);
      ds.push_back(1);

      //      dbg::zout("ds= ", *ite, ds);

      each(ite_ds, ds) SET2.emplace(*ite_ds);
    }
    each(ite, SET2) ans4[*ite]++;
    //   dbg::zout(i, vec);
    //   dbg::zout(i, SET);
    //   dbg::zout(i, ans);
    //   dbg::zout(i, ans2);
    //   dbg::zout(i, ans4, "\n");
  }
  cnt(i, 1, N - 1) {
    ll at = i;
    while (at < N) {
      ans3[i] += ans[at];
      at += i;
    }
  }
  // dbg::zout(1, ans);
  // dbg::zout(2, ans2);
  // dbg::zout(3, ans3);
  // dbg::zout(4, ans4);
  cnt(i, 1, N - 1) cout << max<ll>(0, ans3[i] - ans4[i]) << endl;
  return 0;
}