QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#29775#619. 多项式求逆Qingyu0 656ms435584kbC++2315.3kb2022-04-22 17:40:162022-04-28 15:46:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-28 15:46:16]
  • 评测
  • 测评结果:0
  • 用时:656ms
  • 内存:435584kb
  • [2022-04-22 17:40:16]
  • 提交

answer

#include <bits/stdc++.h>

typedef long long ll;

#define NTT_MODE +1
#define MTT_MODE -1

constexpr int MODE = MTT_MODE;
int mod;
int64_t n;
const int inv2 = (mod + 1) / 2;
const int N = 5e6 + 50;
const int g = 3;
inline int lc(int o) { return o << 1; }
inline int rc(int o) { return o << 1 | 1; }

inline int inc(int x, int y) { x += y - mod; return x + (x >> 31 & mod); }
inline int dec(int x, int y) { x -= y; return x + (x >> 31 & mod); }  
inline int mul(int x, int y) { return 1ll * x * y % mod; }


template <int T>
struct fast_io
{
	char p[T], q[T], * p1, * p2, * q1, * q2;
	fast_io()
	{
		p1 = p2 = p;
		q1 = q, q2 = q + T;
	}
	inline char gc()
	{
		return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
	}
	inline void pc(char c)
	{
		if (q1 == q2) 
		{
			fwrite(q, 1, T, stdout);
			q1 = q;
		}
		*q1++ = c;
	}
	~fast_io()
	{
		fwrite(q, 1, q1 - q, stdout);
	}
};
fast_io<2000000> io;

inline int64_t read()
{
	int64_t r = 0, neg = 1;
	char ch;
	do
	{
		ch = io.gc();
		if (ch == '-') neg = -1;
	} while (ch < 48 || ch > 57);
	do r = r * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
	return r * neg;
}

inline void read(char *s)
{
	char ch;
	do ch = io.gc(); while (!isalpha(ch));
	do *s++ = ch, ch = io.gc(); while (isalpha(ch));
	*s++ = 0;
}

inline void putint(int x)
{
	if (x < 0)
	{
		io.pc('-');
		putint(-x);
		return;
	}
	if (x / 10) putint(x / 10);
	io.pc(48 + x % 10);
}

inline void output(int x, char ch = ' ')
{
	putint(x);
	io.pc(ch);
}


struct Math
{
	int fact[N], factinv[N], inv_e[N], pri[N], mu[N], tot;
	bool isnt_pri[N];
	inline int fastpow(int x, ll p)
	{
		int res = 1; 
		while (p)
		{
			if (p & 1) res = mul(res, x);
			x = mul(x, x);
			p >>= 1;
		}
		return res;
	}
	inline int inv(int x)
	{
		x %= mod;
		if (x < N) return inv_e[x];
		return fastpow(x, mod - 2);
	}
	inline void init()
	{
		fact[0] = factinv[0] = inv_e[0] = 1;
		for (int i = 1; i < N; ++i) fact[i] = mul(i, fact[i - 1]);
		factinv[N - 1] = fastpow(fact[N - 1], mod - 2);
		for (int i = N - 2; i >= 1; --i) factinv[i] = mul(i + 1, factinv[i + 1]);
		for (int i = 1; i < N; ++i) inv_e[i] = mul(fact[i - 1], factinv[i]);
		isnt_pri[1] = true; mu[1] = 1;
		for (int i = 2; i < N; ++i)
		{
			if (isnt_pri[i] == false)
			{
				pri[++tot] = i;
				mu[i] = -1;
			}
			for (int j = 1; j <= tot && i * pri[j] < N; ++j)
			{
				isnt_pri[i * pri[j]] = true;
				if (i % pri[j] == 0)
				{
					mu[i * pri[j]] = 0;
					break;
				}
				else mu[i * pri[j]] = -mu[i];
			}
		}

	}
	
} mt;
struct Poly
{
	std::vector<int> v;
	Poly() { }
	Poly(std::vector<int> v) : v(v) {}
	Poly(std::initializer_list<int> v) : v(v) {}

	inline int deg() const { return v.size() - 1; }
	inline void redeg(int k) { v.resize(k + 1); }
	inline Poly slice(int k) const
	{
		if (k < v.size())
			return std::vector<int>(v.begin(), v.begin() + k + 1);
		std::vector<int> a(v);
		a.resize(k + 1);
		return a;
	}
	inline Poly clone() const { return slice(deg()); }
	inline void reverse() { std::reverse(v.begin(), v.end()); }
	inline void shrink()
	{
		int c = deg();
		while (c >= 0 && v[c] == 0) --c;
		v.resize(c + 1);
	}

	inline int& operator[](int k)
	{
		if (v.size() <= k) v.resize(k + 1);
		return v[k];
	}
	inline int operator[](int k) const
	{
		return v.size() <= k ? 0 : v[k];
	}
	inline void print() const
	{
		for (auto x : v) output(x);
		io.pc('\n');
	}

	inline Poly inv() const;
	inline Poly derivative() const;
	inline Poly integration() const;
	inline Poly ln() const;
	inline Poly exp() const;
	inline Poly reverse() const;
	inline Poly sqrt() const;
	inline std::vector<int> evaluation(const std::vector<int> &vals) const;
	inline void interpolation(const std::vector<std::pair<int, int> > &points);

	Poly(std::vector<std::pair<int, int> > points) { interpolation(points); }
};  
struct NTT
{
	int len, k;
	int omega[N], omegaInv[N], rev[N];
	inline void init(int n)
	{
		int last_len = len;
		len = 1, k = 0;
		while (len <= n) len <<= 1, ++k;
		if (last_len == len) return;
		for (int i = 0; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
		omega[0] = omegaInv[0] = 1;
		const int primitive = mt.fastpow(g, (mod - 1) / len);
		for (int i = 1; i < len; ++i) omega[i] = omegaInv[len - i] = mul(omega[i - 1], primitive);
	}
	inline void operator() (Poly &a, const int *w)
	{
		if (a.v.size() < len) a.v.resize(len);
		int *b = a.v.data();
		for (int i = 0; i < len; ++i) if (i < rev[i]) std::swap(b[i], b[rev[i]]);
		for (int h = 1; h < len; h <<= 1)
			for (int t = len / (h << 1), j = 0; j < len; j += (h << 1))
			{
				const int *wn = w;
				for (int i = j; i < j + h; ++i)
				{
					const int _1 = b[i], _2 = mul(b[i + h], *wn);
					b[i] = inc(_1, _2);
					b[i + h] = dec(_1, _2);
					wn += t;
				}
			}
		if (w == omegaInv)
		{
			const int factor = mod - (mod - 1) / len;
			for (int i = 0; i < len; ++i) b[i] = mul(b[i], factor);
		}
	}
	inline void operator() (Poly &a, int op)
	{
		if (op == 1) operator()(a, omega);
		if (op == -1) operator()(a, omegaInv);
	}
} ntt;

struct Complex
{
	long double x, y;
	Complex (long double x = 0.0, long double y = 0.0) : x(x), y(y) {}
	inline Complex conj() { return Complex(x, -y); }
};

inline Complex operator+ (Complex a, Complex b) { return Complex(a.x + b.x, a.y + b.y); }
inline Complex operator- (Complex a, Complex b) { return Complex(a.x - b.x, a.y - b.y); }
inline Complex operator* (Complex a, Complex b) { return Complex(a.x * b.x - a.y * b.y, a.y * b.x + a.x * b.y); }
inline Complex operator* (Complex a, long double b) { return Complex(a.x * b, a.y * b); }
inline Complex operator/ (Complex a, long double b) { return Complex(a.x / b, a.y / b); }

static const long double pi = acosl(-1.0L);
struct FFT
{
	int rev[N], len, k;
	Complex omega[N], omegaInv[N];
	inline void init(int n)
	{
		int last_len = len;
		k = 0, len = 1;
		while (len <= n) ++k, len <<= 1;
		if (len == last_len) return;
		for (int i = 1; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
		omega[0] = omegaInv[0] = 1;
		Complex t(cosl(2.0L * pi / len), sinl(2.0L * pi / len));
		for (int i = 1; i < len; ++i) 
		    if (i & 32) omega[i] = omegaInv[len - i] = omega[i - 1] * t;
		    else omega[i] = omegaInv[len - i] = Complex(cosl(2.0L * pi * i / len), sinl(2.0L * pi * i / len));
	}
	
	inline void operator() (std::vector<Complex> &A, const Complex *w)
	{
		if (A.size() < len) A.resize(len);
		for (int i = 0; i < len; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
		for (int h = 1; h < len; h <<= 1)
			for (int t = len / (h * 2), j = 0; j < len; j += h * 2)
			{
				const Complex *wn = w;
				for (int i = j; i < j + h; ++i)
				{
					const Complex _1 = A[i], _2 = A[i + h] * *wn;
					A[i] = _1 + _2, A[i + h] = _1 - _2;
					wn += t;
				}
			}
		if (w == omegaInv)
		{
			for (int i = 0; i < len; ++i) A[i] = A[i] / len;
		}
	}
	inline void operator() (std::vector<Complex> &A, int op)
	{
		if (op == 1) operator() (A, omega);
		if (op == -1) operator() (A, omegaInv);
	}
} fft;

inline Poly operator+(const Poly &P, const Poly &Q)
{
	Poly R;
	int deg = std::max(P.deg(), Q.deg());
	for (int i = 0; i <= deg; ++i) R[i] = inc(P[i], Q[i]);
	return R;
}

inline Poly operator+(const Poly &P, const int q)
{
	Poly R = P.clone();
	R[0] = inc(R[0], q);
	return R;
}

inline Poly operator-(const Poly &P, const Poly &Q)
{
	Poly R;
	int deg = std::max(P.deg(), Q.deg());
	for (int i = 0; i <= deg; ++i) R[i] = dec(P[i], Q[i]);
	return R;
}

inline Poly operator-(const Poly &P, const int q)
{
	Poly R = P.clone();
	R[0] = dec(R[0], q);
	return R;
}


inline Poly operator*(const Poly &_P, const Poly &_Q)
{
	if (MODE == NTT_MODE)
	{
	Poly P = _P.clone(), Q = _Q.clone();
	int deg = P.deg() + Q.deg();
	Poly R;
	if (P.deg() + Q.deg() <= 63)
	{
		R.redeg(P.deg() + Q.deg());
		int *r = R.v.data();
		const int *p = P.v.data(), *q = Q.v.data();

		for (int i = 0; i <= P.deg(); ++i)
			for (int j = 0; j <= Q.deg(); ++j)
				r[i + j] = inc(r[i + j], mul(p[i], q[j]));
		return R.slice(deg);
	}
	else
	{
		ntt.init(P.deg() + Q.deg() );
		ntt(P, 1); ntt(Q, 1);
		R.v.resize(ntt.len);
		int *r = R.v.data();
		const int *p = P.v.data(), *q = Q.v.data();
		for (int i = 0; i < ntt.len; ++i) r[i] = mul(p[i], q[i]);
		ntt(R, -1);
		return R.slice(deg);
	}
	}
	else
	{
	const int M = 1 << 15;
	int n = _P.deg(), m = _Q.deg();
	fft.init(n + m);
	std::vector<Complex> P1, Q1, F1, F2;
	P1.resize(n + 1); Q1.resize(m + 1);
	for (int i = 0; i <= n; ++i) {
		P1[i] = Complex(_P[i] % mod, 0);
	}
	for (int i = 0; i <= m; ++i) {
		Q1[i] = Complex(_Q[i] % mod, 0);
	}
	P1.resize(fft.len);
	Q1.resize(fft.len);
	//for (int i = 0; i <= n; ++i) P1[i] = Complex(_P[i] & 32767, _P[i] >> 15);
	//for (int i = 0; i <= m; ++i) Q1[i] = Complex(_Q[i] & 32767, _Q[i] >> 15);
	fft(P1, 1);
   
	fft(Q1, 1);
	//P1.push_back(P1[0]), Q1.push_back(Q1[0]);
	//F1.resize(fft.len), F2.resize(fft.len);
	F1.resize(fft.len + 1);
	for (int i = 0; i <= fft.len; ++i) {
		F1[i] = P1[i] * Q1[i];
	}
	fft(F1, -1);
	Poly result;
	for (int i = 0; i <= n + m; ++i)
		result[i] = ((long long)(F1[i].x + 0.5)) % mod;
	return result;
	}
}

inline Poly PolyInv(const Poly &A)
{
	Poly Ax, R;
	
	int n = A.deg();
	if (n == 0) return Poly({ mt.inv(A[0]) });
	if (MODE == NTT_MODE)
	{
	R = PolyInv(A.slice(A.deg() >> 1));
	ntt.init(A.deg() << 1);
	Ax = A.clone();
	ntt(Ax, 1); ntt(R, 1);
	for (int i = 0; i < ntt.len; ++i) Ax[i] = dec(mul(Ax[i], R[i]), 1);
	for (int i = 0; i < ntt.len; ++i) R[i] = mul(R[i], dec(1, Ax[i]));
	ntt(R, -1);
	R.redeg(n);
	return R;
	}
	else
	{
	R = PolyInv(A.slice(n >> 1));
	R.redeg(n);
	Ax = A * R - 1;
	Ax.redeg(n);
	return (R - R * Ax).slice(n);
	}
}

inline Poly Poly::inv() const
{
	return PolyInv(*this).slice(deg());
}

inline Poly Poly::derivative() const
{
	Poly R;
	for (int i = 0; i < deg(); ++i) R[i] = mul(i + 1, operator[](i + 1));
	return R;
}

inline Poly Poly::integration() const
{
	Poly R;
	for (int i = 1; i <= deg(); ++i) R[i] = mul(mt.inv(i), operator[](i - 1));
	return R;
}

inline Poly Poly::ln() const
{
	return (derivative() * inv()).integration().slice(deg());
}

inline Poly PolyExp(const Poly &A)
{
	Poly Ax, Ay, R;
	int n = A.deg();
	if (n == 0) return Poly({1});
	R = PolyExp(A.slice(n >> 1)).slice(n);
	Ax = R.ln();
	Ay = A.slice(n);
	return R * (Ay + 1 - Ax);
}

inline Poly Poly::exp() const
{
	return PolyExp(*this).slice(deg());
}

inline std::pair<Poly, Poly> PolyDiv(const Poly &F, const Poly &G)
{
	Poly Fx, Gx, GrInv, Px, P, Q;
	int n = F.deg(), m = G.deg(); 
	Fx = F.clone(), Gx = G.clone();
	Fx.reverse(); Gx.reverse(); Fx.redeg(n - m + 1);
	Gx.redeg(std::max(m, n - m)); GrInv = Gx.inv(); 
	P = Fx * GrInv;

	P.redeg(n - m); P.reverse(); Gx = G.clone();
	Q = Gx * P; Q.redeg(m - 1);
	for (int i = 0; i <= m - 1; ++i) Q[i] = dec(F[i], Q[i]);
	return std::make_pair(Q, P);
}

inline Poly PolySqrt(const Poly &A)
{
	int n = A.deg();
	if (n == 0)
	{
		assert(A[0] == 0 || A[0] == 1);
		return Poly({A[0]});
	}
	Poly R = PolySqrt(A.slice(n >> 1));
	R.redeg(n);
       	Poly H = R.inv(), K = (R * R).slice(n);
	for (int i = 0; i <= H.deg(); ++i) H[i] = mul(H[i], inv2);
	return (A + K) * H;
}

inline Poly Poly::sqrt() const
{
	return PolySqrt(*this).slice(deg());
}

inline Poly operator%(const Poly &P, const Poly &Q) { return PolyDiv(P, Q).first; }
inline Poly operator/(const Poly &P, const Poly &Q) { return PolyDiv(P, Q).second; }

inline Poly Mul_T(const Poly &a, const Poly &b)
{
	Poly R, A = a.clone(), B = b.clone();
	if (A.deg() <= 100)
	{
		for (int i = a.deg(); i >= 0; --i)
			for (int j = std::max(0, i - (a.deg() - b.deg())); j <= std::min(i, b.deg()); ++j)
				R[i - j] = inc(R[i - j], mul(a[i], b[j]));
		return R;
	}
	else
	{
		B.reverse();
		ntt.init(A.deg());
		ntt(A, 1); ntt(B, 1);
		for (int i = 0; i < ntt.len; ++i) A[i] = mul(A[i], B[i]);
		ntt(A, -1);
		int c = 0;
		for (int i = b.deg(); i <= a.deg(); ++i) R[c++] = A[i];
		return R;
	}
}


inline std::vector<int> Poly::evaluation(const std::vector<int> &vals) const
{
	std::vector<Poly> T, F;
	int m = vals.size();
	int t = std::max(deg(), (int)vals.size()) + 1;
	ntt.init(t);
	T.resize(t * 4); F.resize(t * 4);
	std::function<void(int, int, int)> solve = [&](int o, int l, int r)
	{
		assert(o < T.size());
	//	T[0].redeg(-1);
	//	if (l == r) T[o] = Poly({1, dec(0, vals[l])});
	//	else
		if (l == r) {


		}
		else
		{
			const int mid = l + r >> 1;
			solve(lc(o), l, mid); solve(rc(o), mid + 1, r);
	//		T[o] = T[lc(o)] * T[rc(o)];
		}
	};
	std::function<void(int, int, int, std::vector<int>&)> solve2 = [&](int o, int l, int r, std::vector<int> &ans)
	{
		assert(o < T.size());
		if (l >= m) return;
		if (l == r) ans.push_back(F[o][0]);
		else
		{
			const int mid = l + r >> 1;
			F[lc(o)] = Mul_T(F[o], T[rc(o)]);
			F[rc(o)] = Mul_T(F[o], T[lc(o)]);
			solve2(lc(o), l, mid, ans); solve2(rc(o), mid + 1, r, ans);
		}
	};
	puts("solving");
	solve(1, 0, t);
	puts("solved");
	Poly Q = T[1].inv();
	Q.redeg(t); 
	Q.reverse();
	Poly R = Q * *this;
	for (int i = t; i <= R.deg(); ++i) F[1][i - t] = R[i];
	F[1].redeg(t);
	std::vector<int> ans;
	puts("solving 2");
	solve2(1, 0, t, ans);
	puts("solved 2");
	return ans;
}

inline void Poly::interpolation(const std::vector<std::pair<int, int> > &points)
{
	int n = points.size();
	std::vector<Poly> T(n << 2);
	std::vector<int> vals;
	for (auto v : points) vals.push_back(v.first);
	std::function<void(int, int, int)> solve = [&](int o, int l, int r)
	{
		if (l == r) T[o] = Poly({ dec(0, vals[l]), 1 });
		else
		{
			const int mid = l + r >> 1;
			solve(lc(o), l, mid); solve(rc(o), mid + 1, r);
			T[o] = T[lc(o)] * T[rc(o)];
		}
	};
	solve(1, 0, n - 1);
	Poly g = T[1], dg = g.derivative();
	std::vector<int> ys = dg.evaluation(vals);
	std::function<Poly(int, int, int)> solve2 = [&](int o, int l, int r)
	{
		if (l == r) return Poly({ mul(points[l].second, mt.inv(ys[l])) });
		const int mid = l + r >> 1;
		return solve2(lc(o), l, mid) * T[rc(o)] + solve2(rc(o), mid + 1, r) * T[lc(o)];
	};
	*this = solve2(1, 0, n - 1);
}
void debug() {
	int n, m;
	std::cin >> n;
	mod = 998244353;
	mt.init();
	Poly P;
	for (int i = 0; i < n; ++i)
		std::cin >> P[i];
	Poly R = P.inv();
	R.print();
}
int main()
{
	debug();
	return 0;
	std::cin >> mod >> n;
	mt.init();
	time_t aa = clock();
	// calc prod (x^2 - i^2)
	std::vector<Poly> P(mod);
	for (int i = 0; i < mod; ++i) {
		P[i].redeg(2);
		P[i][0] = dec(0, mul(i, i));
		P[i][1] = 0;
		P[i][2] = 1;
	}
	auto mult = [&](auto &self, int l, int r, auto &P) -> Poly {
		if (l == r)
			return P[l];
		const int mid = l + r >> 1;
		return self(self, l, mid, P) * self(self, mid + 1, r, P);
	};
	auto full = mult(mult, 0, mod - 1, P);
	auto part = mult(mult, 0, n % mod, P); 
	std::cout << full.deg() << '\n';
	// full ^ (n / mod) * part
	std::vector<int> vals(mod);
	for (int i = 0; i < mod; ++i)
		vals[i] = i;	
	auto full_v = full.evaluation(vals);
	auto part_v = part.evaluation(vals);
	printf("%.6fs\n", (clock() - aa) * 1.0 / CLOCKS_PER_SEC);
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 185ms
memory: 400464kb

input:

100
321704272 732147873 495950455 607498198 139258053 834073875 837326587 9642661 903437916 207412353 359180940 720085797 719290810 723076036 984279000 503225771 350175866 162829281 512559053 225874248 808881115 775602122 556705696 16814894 894905093 985867138 253650922 979472539 59109787 205995179 ...

output:

315099809 7542893 498853541 685241806 436311918 718836447 534584310 208403205 502856595 206401014 592222414 845417461 826374091 89670070 113514950 504958694 283628439 445293134 116024745 277748256 901837167 475035333 582527567 369640675 762922223 379008876 860457882 701017831 655384562 990360010 573...

result:

wrong answer 1st numbers differ - expected: '890391751', found: '315099809'

Test #2:

score: 0
Wrong Answer
time: 213ms
memory: 402312kb

input:

5000
895174753 48640370 621768187 544696442 266653647 800854366 993400253 180889611 259138834 922465819 237366500 134204023 882884556 962623362 906378209 783980105 385064692 526608265 306798389 492937123 600567928 363960265 499995507 901802313 322681104 915889147 191761221 168327309 250045818 379937...

output:

296292571 275789026 503144443 239636955 255449568 174314374 424128457 546394837 529791552 659292935 263758943 378404013 143939485 577946225 522550816 569181576 771261787 739233273 372668576 849900934 816362661 271107866 307157554 283197037 812152855 940403057 532988424 31213823 951839756 937372210 4...

result:

wrong answer 1st numbers differ - expected: '682334353', found: '296292571'

Test #3:

score: 0
Wrong Answer
time: 269ms
memory: 409512kb

input:

30000
433849057 26933151 94119735 348782922 994201565 286266085 253836562 391505281 561460922 76317536 151770395 626212470 835627785 278418333 560388198 586773695 43090005 450934659 716357773 746228248 47588293 745422420 131896260 923566007 275614901 981279191 966289868 111837778 850083076 346727100...

output:

175940175 208774251 86735184 555312985 308856463 560007527 187181080 863825730 174326281 970247080 842783467 373612342 81551532 531272067 368060253 820314397 117642098 499093620 191268957 377995108 865370483 681567167 114410356 758331748 529038207 812056123 845378248 105612810 932101373 958149974 43...

result:

wrong answer 1st numbers differ - expected: '357845866', found: '175940175'

Test #4:

score: 0
Wrong Answer
time: 656ms
memory: 435584kb

input:

100000
299085935 896290047 664961463 798136437 284888760 805376081 754380153 982440654 523416648 618138054 639229548 946675552 216492659 801950754 591895463 409803161 734598818 262678735 505505080 132772037 241184558 549895828 778274609 60046418 766879997 555641192 925835147 535599922 727361907 2850...

output:

567555989 98986070 242538223 658913270 350553178 749268574 912764737 417630162 683330751 115059472 434294360 12849835 891289573 283809230 146123867 488376782 680924192 278765930 335575084 780285231 302748634 483959340 408058306 188772293 939811940 837457120 67607926 81834142 246465852 957976520 3244...

result:

wrong answer 1st numbers differ - expected: '152663231', found: '567555989'

Test #5:

score: 0
Time Limit Exceeded

input:

1000000
737044976 941398691 939287417 273413335 175365852 377721127 3862986 176449650 791765055 129385383 433663518 447033570 279210233 157228851 130509370 963480863 130226624 349605390 600289609 890766355 577960206 537162643 776878360 951933771 688851169 624945579 212339598 106077966 426859950 6284...

output:


result: