結果

問題 No.3182 recurrence relation’s intersection sum
コンテスト
ユーザー ecottea
提出日時 2025-12-25 16:48:58
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 21,008 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,726 ms
コンパイル使用メモリ 333,764 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-25 16:49:07
合計ジャッジ時間 8,458 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifndef HIDDEN_IN_VS // 折りたたみ用

// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS

// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;

// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>;	using pll = pair<ll, ll>;	using pil = pair<int, ll>;	using pli = pair<ll, int>;
using vi = vector<int>;		using vvi = vector<vi>;		using vvvi = vector<vvi>;	using vvvvi = vector<vvvi>;
using vl = vector<ll>;		using vvl = vector<vl>;		using vvvl = vector<vvl>;	using vvvvl = vector<vvvl>;
using vb = vector<bool>;	using vvb = vector<vb>;		using vvvb = vector<vvb>;
using vc = vector<char>;	using vvc = vector<vc>;		using vvvc = vector<vvc>;
using vd = vector<double>;	using vvd = vector<vd>;		using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;

// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;

// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;

// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定

// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline int getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod

// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }

#endif // 折りたたみ用


#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;

#ifdef _MSC_VER
#include "localACL.hpp"
#endif

using mint = modint998244353;
//using mint = static_modint<(int)1e9+7>;
//using mint = modint; // mint::set_mod(m);

using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif


#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
int mute_dump = 0;
int frac_print = 0;
#if __has_include(<atcoder/all>)
namespace atcoder {
	inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
	inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
#endif
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); rep(i,9)cout<<MLE[i]; exit(0); } } // RE の代わりに MLE を出す
#endif


//【畳込み（素朴）】O(n m)
template <class T>
vector<T> naive_convolution(const vector<T>& a, const vector<T>& b) {
	int n = sz(a), m = sz(b);
	if (n == 0 || m == 0) return vector<T>();

	// c[k] = Σ_(i+j=k) a[i] b[j]
	vector<T> c(n + m - 1);
	if (n < m) {
		rep(i, n) rep(j, m) c[i + j] += a[i] * b[j];
	}
	else {
		rep(j, m) rep(i, n) c[i + j] += a[i] * b[j];
	}

	return c;
}


//【畳込み（法が任意，mint）】O((n + m) log(n + m))（手元ではオーバーフローでバグるので注意）
vm convolution_arbitrary_mod(const vm& a, const vm& b) {
	int n = sz(a), m = sz(b);
	if (n == 0 || m == 0) return vm();

	if (min(n, m) <= 80) {
		vm c(n + m - 1);

		if (n < m) {
			rep(i, n) rep(j, m) c[i + j] += a[i] * b[j];
		}
		else {
			rep(j, m) rep(i, n) c[i + j] += a[i] * b[j];
		}

		return c;
	}

	constexpr int MOD = mint::mod();

	constexpr int MOD1 = 998244353;
	constexpr int MOD2 = 897581057;
	constexpr int MOD3 = 880803841;

	constexpr __int128 MOD23 = 790592842614439937;
	constexpr __int128 MOD13 = 879257460378959873;
	constexpr __int128 MOD12 = 896005221510021121;

	constexpr __int128 MOD123 = __int128(MOD1) * MOD2 * MOD3; // 789204840662082423367925761

	constexpr int MOD23_inv = 41593599;
	constexpr int MOD13_inv = 635786105;
	constexpr int MOD12_inv = 220201354;

	using mint1 = static_modint<MOD1>;
	using mint2 = static_modint<MOD2>;
	using mint3 = static_modint<MOD3>;

	vector<mint1> a1(n), b1(m);
	vector<mint2> a2(n), b2(m);
	vector<mint3> a3(n), b3(m);

	rep(i, n) {
		a1[i] = a[i].val();
		a2[i] = a[i].val();
		a3[i] = a[i].val();
	}
	rep(j, m) {
		b1[j] = b[j].val();
		b2[j] = b[j].val();
		b3[j] = b[j].val();
	}

	auto c1 = convolution(a1, b1);
	auto c2 = convolution(a2, b2);
	auto c3 = convolution(a3, b3);

	vm res(n + m - 1);

	rep(k, n + m - 1) {
		__int128 val1 = c1[k].val() * MOD23 * MOD23_inv;
		__int128 val2 = c2[k].val() * MOD13 * MOD13_inv;
		__int128 val3 = c3[k].val() * MOD12 * MOD12_inv;

		res[k] = (int)(((val1 + val2 + val3) % MOD123) % MOD);
	}

	return res;
}


//【形式的冪級数】
struct MFPS {
	using SMFPS = vector<pim>;

	int n; // 係数の個数（次数 + 1）
	vm c; // 係数列
	inline static vm(*CONV)(const vm&, const vm&) = convolution; // 畳込み用の関数

	// コンストラクタ（0，定数，係数列で初期化）
	MFPS() : n(0) {}
	MFPS(mint c0) : n(1), c({ c0 }) {}
	MFPS(int c0) : n(1), c({ mint(c0) }) {}
	MFPS(mint c0, int d) : n(d), c(n) { if (n > 0) c[0] = c0; }
	MFPS(int c0, int d) : n(d), c(n) { if (n > 0) c[0] = c0; }
	MFPS(const vm& c_) : n(sz(c_)), c(c_) {}
	MFPS(const vi& c_) : n(sz(c_)), c(n) { rep(i, n) c[i] = c_[i]; }

	// 代入
	MFPS(const MFPS& f) = default;
	MFPS& operator=(const MFPS& f) = default;
	MFPS& operator=(const mint& c0) { n = 1; c = { c0 }; return *this; }

	void push_back(mint cn) { c.emplace_back(cn); ++n; }
	void pop_back() { c.pop_back(); --n; }
	[[nodiscard]] mint back() { return c.back(); }

	// 比較
	[[nodiscard]] bool operator==(const MFPS& g) const { return c == g.c; }
	[[nodiscard]] bool operator!=(const MFPS& g) const { return c != g.c; }

	// アクセス
	inline mint const& operator[](int i) const { return c[i]; }
	inline mint& operator[](int i) { return c[i]; }

	// 次数
	[[nodiscard]] int deg() const { return n - 1; }
	[[nodiscard]] int size() const { return n; }

	static void set_conv(vm(*CONV_)(const vm&, const vm&)) {
		CONV = CONV_;
	}

	// 加算
	MFPS& operator+=(const MFPS& g) {
		if (n >= g.n) rep(i, g.n) c[i] += g.c[i];
		else {
			rep(i, n) c[i] += g.c[i];
			repi(i, n, g.n - 1)	c.push_back(g.c[i]);
			n = g.n;
		}
		return *this;
	}
	[[nodiscard]] MFPS operator+(const MFPS& g) const { return MFPS(*this) += g; }

	// 定数加算
	MFPS& operator+=(const mint& sc) {
		if (n == 0) { n = 1; c = { sc }; }
		else { c[0] += sc; }
		return *this;
	}
	[[nodiscard]] MFPS operator+(const mint& sc) const { return MFPS(*this) += sc; }
	[[nodiscard]] friend MFPS operator+(const mint& sc, const MFPS& f) { return f + sc; }
	MFPS& operator+=(const int& sc) { *this += mint(sc); return *this; }
	[[nodiscard]] MFPS operator+(const int& sc) const { return MFPS(*this) += sc; }
	[[nodiscard]] friend MFPS operator+(const int& sc, const MFPS& f) { return f + sc; }

	// 減算
	MFPS& operator-=(const MFPS& g) {
		if (n >= g.n) rep(i, g.n) c[i] -= g.c[i];
		else {
			rep(i, n) c[i] -= g.c[i];
			repi(i, n, g.n - 1) c.push_back(-g.c[i]);
			n = g.n;
		}
		return *this;
	}
	[[nodiscard]] MFPS operator-(const MFPS& g) const { return MFPS(*this) -= g; }

	// 定数減算
	MFPS& operator-=(const mint& sc) { *this += -sc; return *this; }
	[[nodiscard]] MFPS operator-(const mint& sc) const { return MFPS(*this) -= sc; }
	[[nodiscard]] friend MFPS operator-(const mint& sc, const MFPS& f) { return -(f - sc); }
	MFPS& operator-=(const int& sc) { *this += -sc; return *this; }
	[[nodiscard]] MFPS operator-(const int& sc) const { return MFPS(*this) -= sc; }
	[[nodiscard]] friend MFPS operator-(const int& sc, const MFPS& f) { return -(f - sc); }

	// 加法逆元
	[[nodiscard]] MFPS operator-() const { return MFPS(*this) *= -1; }

	// 定数倍
	MFPS& operator*=(const mint& sc) { rep(i, n) c[i] *= sc; return *this; }
	[[nodiscard]] MFPS operator*(const mint& sc) const { return MFPS(*this) *= sc; }
	[[nodiscard]] friend MFPS operator*(const mint& sc, const MFPS& f) { return f * sc; }
	MFPS& operator*=(const int& sc) { *this *= mint(sc); return *this; }
	[[nodiscard]] MFPS operator*(const int& sc) const { return MFPS(*this) *= sc; }
	[[nodiscard]] friend MFPS operator*(const int& sc, const MFPS& f) { return f * sc; }

	// 右からの定数除算
	MFPS& operator/=(const mint& sc) { *this *= sc.inv(); return *this; }
	[[nodiscard]] MFPS operator/(const mint& sc) const { return MFPS(*this) /= sc; }
	MFPS& operator/=(const int& sc) { *this /= mint(sc); return *this; }
	[[nodiscard]] MFPS operator/(const int& sc) const { return MFPS(*this) /= sc; }

	// 積
	MFPS& operator*=(const MFPS& g) { c = CONV(c, g.c); n = sz(c); return *this; }
	[[nodiscard]] MFPS operator*(const MFPS& g) const { return MFPS(*this) *= g; }

	// 除算
	[[nodiscard]] MFPS inv(int d) const {
		Assert(!c.empty());
		Assert(c[0] != 0);

		MFPS g(c[0].inv());
		for (int k = 1; k < d; k <<= 1) {
			int len = max(min(2 * k, d), 1);
			MFPS tmp(0, len);
			rep(i, min(len, n)) tmp[i] = -c[i];	// -f
			tmp *= g;							// -f h
			tmp.resize(len);
			tmp[0] += 2;						// 2 - f h
			g *= tmp;							// (2 - f h) h
			g.resize(len);
		}

		return g;
	}
	MFPS& operator/=(const MFPS& g) { return *this *= g.inv(max(n, g.n)); }
	[[nodiscard]] MFPS operator/(const MFPS& g) const { return MFPS(*this) /= g; }

	// 余り付き除算
	[[nodiscard]] MFPS quotient(const MFPS& g) const {
		if (n < g.n) return MFPS();
		return ((this->rev() / g.rev()).resize(n - g.n + 1)).rev();
	}
	[[nodiscard]] MFPS reminder(const MFPS& g) const {
		return (*this - this->quotient(g) * g).resize();
	}
	[[nodiscard]] pair<MFPS, MFPS> quotient_remainder(const MFPS& g) const {
		pair<MFPS, MFPS> res;
		res.first = this->quotient(g);
		res.second = (*this - res.first * g).resize();
		return res;
	}

	// スパース積
	MFPS& operator*=(const SMFPS& g) {
		// g の定数項だけ例外処理
		auto it0 = g.begin();
		mint g0 = 0;
		if (it0->first == 0) {
			g0 = it0->second;
			it0++;
		}

		// 後ろからインライン配る DP
		repir(i, n - 1, 0) {
			// 上位項に係数倍して配っていく．
			for (auto it = it0; it != g.end(); it++) {
				auto [j, gj] = *it;

				if (i + j >= n) break;

				c[i + j] += c[i] * gj;
			}

			// 定数項は最後に配るか消去しないといけない．
			c[i] *= g0;
		}

		return *this;
	}
	[[nodiscard]] MFPS operator*(const SMFPS& g) const { return MFPS(*this) *= g; }

	// スパース商
	MFPS& operator/=(const SMFPS& g) {
		// g の定数項だけ例外処理
		auto it0 = g.begin();
		Assert(it0->first == 0 && it0->second != 0);
		mint g0_inv = it0->second.inv();
		it0++;

		// 前からインライン配る DP（後ろに累積効果あり）
		rep(i, n) {

			// 定数項は最初に配らないといけない．
			c[i] *= g0_inv;

			// 上位項に係数倍して配っていく．
			for (auto it = it0; it != g.end(); it++) {
				auto [j, gj] = *it;

				if (i + j >= n) break;

				c[i + j] -= c[i] * gj;
			}
		}

		return *this;
	}
	[[nodiscard]] MFPS operator/(const SMFPS& g) const { return MFPS(*this) /= g; }

	// 係数反転
	[[nodiscard]] MFPS rev() const { MFPS h = *this; reverse(all(h.c)); return h; }

	// 単項式
	[[nodiscard]] static MFPS monomial(int d, mint coef = 1) {
		MFPS mono(0, d + 1);
		mono[d] = coef;
		return mono;
	}

	// 不要な高次項の除去
	MFPS& resize() {
		// 最高次の係数が非 0 になるまで削る．
		while (n > 0 && c[n - 1] == 0) {
			c.pop_back();
			n--;
		}
		return *this;
	}

	// x^d 以上の項を除去する．
	MFPS& resize(int d) {
		n = d;
		c.resize(d);
		return *this;
	}

	// 不定元への代入
	[[nodiscard]] mint assign(const mint& x) const {
		mint val = 0;
		repir(i, n - 1, 0) val = val * x + c[i];
		return val;
	}

	// 係数のシフト
	MFPS& operator>>=(int d) {
		n += d;
		c.insert(c.begin(), d, 0);
		return *this;
	}
	MFPS& operator<<=(int d) {
		n -= d;
		if (n <= 0) { c.clear(); n = 0; }
		else c.erase(c.begin(), c.begin() + d);
		return *this;
	}
	[[nodiscard]] MFPS operator>>(int d) const { return MFPS(*this) >>= d; }
	[[nodiscard]] MFPS operator<<(int d) const { return MFPS(*this) <<= d; }

#ifdef _MSC_VER
	friend ostream& operator<<(ostream& os, const MFPS& f) {
		if (f.n == 0) os << 0;
		else {
			rep(i, f.n) {
				os << f[i] << "z^" << i;
				if (i < f.n - 1) os << " + ";
			}
		}
		return os;
	}
#endif
};


//【線形漸化式の発見】O(n^2)
vm berlekamp_massey(const vm& a) {
	vm S(a), C{ 1 }, B{ 1 };
	int N = sz(a), m = 1; mint b = 1;

	rep(n, N) {
		mint d = 0;
		rep(i, sz(C)) d += C[i] * S[n - i];

		if (d == 0) {
			m++;
		}
		else if (2 * (sz(C) - 1) <= n) {
			vm T(C);

			mint coef = d * b.inv();
			C.resize(max(sz(C), sz(B) + m));
			rep(j, sz(B)) C[j + m] -= coef * B[j];

			B = T;
			b = d;
			m = 1;
		}
		else {
			mint coef = d * b.inv();
			C.resize(max(sz(C), sz(B) + m));
			rep(j, sz(B)) C[j + m] -= coef * B[j];

			m++;
		}
	}

	return C;
}


//【展開係数】O(n log n log N)
mint bostan_mori(MFPS f, MFPS g, ll N) {
	Assert(g.n >= 1 && g[0] != 0);

	// f(z) = 0 のときは 0 を返す．
	if (f.n == 0) return 0;

	while (N > 0) {
		// f2(z) = f(z) g(-z), g2(z) = g(z) g(-z) を求める．
		MFPS f2, g2 = g;
		rep(i, g2.n) if (i & 1) g2[i] *= -1;
		f2 = f * g2;
		g2 *= g;

		// f3(z) = E(z) or O(z), g3(z) = e(z) を求める．
		f.c.clear(); g.c.clear();
		if (N & 1) rep(i, min<ll>(f2.n / 2, N / 2 + 1)) f.c.push_back(f2[2 * i + 1]);
		else rep(i, min<ll>((f2.n + 1) / 2, N / 2 + 1)) f.c.push_back(f2[2 * i]);
		f.n = sz(f.c);
		rep(i, min<ll>((g2.n + 1) / 2, N / 2 + 1)) g.c.push_back(g2[2 * i]);
		g.n = sz(g.c);

		// N を半分にして次のステップに進む．
		N /= 2;
	}

	// N = 0 になったら定数項を返す．
	return f[0] / g[0];
}


pair<MFPS, MFPS> get_GF(const vm& seq) {
	auto coefs = berlekamp_massey(seq);
	frac_print = 1; dump("coefs:", coefs); dump("sz(coefs):", sz(coefs)); frac_print = 0;
	
	MFPS Dnm(coefs);
	MFPS Num = (Dnm * MFPS(seq)).resize(sz(coefs));

	return { Num, Dnm };
}


int main() {
//	input_from_file("input.txt");
//	output_to_file("output.txt");

	//【方法】
	// 愚直を書いて集めたデータをもとに線形漸化式を復元し，第 N 項を高速に求める．

	//【使い方】
	// 1. vm seq[0..N) を用意する．
	// 2. [num, dnm] = get_GF(seq) で有理型母関数を復元する．
	// 3. bostan_mori(num, dnm, n) で勝手に seq[n] を求めてくれる．
	
	if (mint::mod() != 998244353) {
		MFPS::set_conv(naive_convolution);
		//MFPS::set_conv(convolution_arbitrary_mod); // 手元ではオーバーフローでバグる
	}

	int k; ll l, r;
	cin >> k >> l >> r;

	int N = 210;

	vm a(N + 1);
	a[0] = 1;

	repi(n, 0, N - 1) {
		a[n + 1] = k * a[n] + mint(n).pow(k) + mint(k).pow(n);
	}

	vm seq(N + 2);
	rep(i, N + 1) seq[i + 1] = seq[i] + a[i];
		
	dump("seq:", seq);

	auto [num, dnm] = get_GF(seq);

	mint res = bostan_mori(num, dnm, r + 1) - bostan_mori(num, dnm, l);

	cout << res << "\n";
}
/*
100 0 12345678901234567
seq: 0 1 102 10303 883540121 972147886 933405588 66674558 943472602 333447312 37291070 588505100 418588594 995388092 844679238 490969518 563989240 590379147 28162903 581047378 908220994 259682207 10034211 629294393 938666201 927289066 239315155 946180536 193403548 331362972 685051697 65795359 417922335 51268935 827172212 13061551 930617708 207117024 438690813 106379603 991010770 3028785 552743829 475712335 637606004 26212527 792816447 805748339 526300020 853217187 772229448 774600293 10481166 103882803 67738885 35797648 805559855 302248691 404817767 711880805 198588376 673312569 494028236 918967126 721844466 616341909 350213217 207040064 265316391 153112430 359180168 65035580 535145600 892882504 414522672 184859282 357572026 304713628 782365606 17314365 524886002 865663911 641270064 815585279 74541737 902680008 691264700 397498182 762119720 563608296 126954715 52432209 995127907 665026229 975839616 607420572 729534881 739885654 127876145 486463901 179987990 59186148 558177533 389126928 357318980 229715944 752055773 772073189 591461878 966088993 614007752 658435650 825416556 62331656 655592834 902905310 286108572 180974774 38905145 393245686 153354256 627751781 330321994 119650161 292007353 206692183 865848085 806756394 710286449 820044432 4083427 940336377 579686221 338689687 658070191 189054502 691543966 132472023 770430941 697869203 662868291 149068212 59901822 104049025 842055645 784785667 222229239 422904190 897148057 220931133 864458459 478582232 360841515 248461708 449909311 885101053 124491511 471412423 102858739 508565486 717362906 718720435 250148860 347553899 952224597 275804143 816231654 752191188 91515124 865341627 458807399 234423080 700685914 560311970 263675027 427488728 254083161 461708763 346376444 203777131 970043298 968624391 387336416 509755806 353143548 820837059 218139081 586524946 328439922 308730232 215737213 816611408 795680183 554512551 143444093 391843441 120266754 981933763 638791939 603620451 348356600 952233174 77288721 650946798 406430735 815555722 93147039 353765505 433584168 295213228 465840732 533194106
coefs: 1 -302 -7824/28079 9220/17971 -903/18292 24711/20821 21369/9805 9871/2780 -30329/17742 18821/1853 22813/16817 9703/24524 -14486/2675 8828/2235 22382/24925 -17441/19554 16851/5507 -15591/20341 -1639/26940 21166/14977 28387/14393 -6487/13002 -8927/9248 2596/16779 29399/4391 -14885/9777 27763/8377 -4360/6433 -2717/18570 -24688/23893 -3268/161 -25453/12105 25237/24111 4459/8717 21072/17981 -17969/3279 -29164/5965 18328/20939 13123/20985 -7923/7340 15496/14843 -5184/1531 -21940/23943 13037/21170 25631/12570 -27519/12151 489/13685 7869/10963 9358/20455 10993/24260 -29309/24851 30491/25745 -19305/2468 -5034/20261 15509/13515 2797/352 -14761/18986 27749/1759 -14963/19050 -8688/24839 -24102/9091 26898/6739 17197/11528 -16469/27209 15017/14656 26181/7066 3921/18494 -20151/17873 -9395/6261 -9989/27541 -1324/21773 -4601/7177 -4790/1283 -2909/20858 -15527/6667 -22777/16288 12429/8455 -30336/3779 -5833/26725 -20139/7156 21542/28369 -20289/17062 -15584/24811 -29/1289 28136/17117 -15922/13645 -4640/4403 5759/24200 -31175/23904 22033/1853 5173/10429 -4741/7245 -8352/3497 -19462/21927 16799/19922 9117/16709 -26555/21579 -23846/16527 4961/19010 -27879/7750 -18422/21903 1837/27342 10085/3177 19119/22505 10000
sz(coefs): 105
676403742
*/
0