#669926 (C++17) No.1561 connect x connect

• 問題: No.1561 connect x connect
• ユーザー: chocorusk
• 提出日時: 2021-06-26 00:20:24
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 500 ms / 2,000 ms
• コード長: 63,539 bytes
• コンパイル時間: 14,691 ms
• コンパイル使用メモリ: 806,048 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-06-25 09:00:52
• 合計ジャッジ時間: 19,151 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,812 KB
testcase_02	AC	4 ms; 6,812 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	2 ms; 6,940 KB
testcase_06	AC	2 ms; 6,944 KB
testcase_07	AC	2 ms; 6,944 KB
testcase_08	AC	2 ms; 6,944 KB
testcase_09	AC	2 ms; 6,940 KB
testcase_10	AC	2 ms; 6,944 KB
testcase_11	AC	2 ms; 6,944 KB
testcase_12	AC	2 ms; 6,944 KB
testcase_13	AC	4 ms; 6,944 KB
testcase_14	AC	10 ms; 6,940 KB
testcase_15	AC	12 ms; 6,940 KB
testcase_16	AC	14 ms; 6,944 KB
testcase_17	AC	2 ms; 6,944 KB
testcase_18	AC	2 ms; 6,940 KB
testcase_19	AC	74 ms; 6,940 KB
testcase_20	AC	4 ms; 6,940 KB
testcase_21	AC	2 ms; 6,944 KB
testcase_22	AC	4 ms; 6,944 KB
testcase_23	AC	2 ms; 6,944 KB
testcase_24	AC	75 ms; 6,940 KB
testcase_25	AC	2 ms; 6,940 KB
testcase_26	AC	500 ms; 6,940 KB
testcase_27	AC	498 ms; 6,940 KB
testcase_28	AC	481 ms; 6,940 KB
testcase_29	AC	497 ms; 6,940 KB
testcase_30	AC	494 ms; 6,940 KB
testcase_31	AC	2 ms; 6,944 KB
testcase_32	AC	4 ms; 6,940 KB
testcase_33	AC	12 ms; 6,944 KB
testcase_34	AC	76 ms; 6,940 KB
testcase_35	AC	11 ms; 6,944 KB
testcase_36	AC	82 ms; 6,940 KB
testcase_37	AC	488 ms; 6,944 KB

ソースコード

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#include <atcoder/all>
using namespace std;

#pragma region Math Formal Power Series
enum Mode {
	FAST = 1,
	NAIVE = -1,
};
template <class T, Mode mode = FAST>
struct FormalPowerSeries : std::vector<T> {
	using std::vector<T>::vector;
	using std::vector<T>::size;
	using std::vector<T>::resize;
	using std::vector<T>::begin;
	using std::vector<T>::insert;
	using std::vector<T>::erase;
	using F = FormalPowerSeries;
	using S = std::vector<std::pair<int, T>>;

	F &operator+=(const F &g) {
		for(int i = 0; i < int(std::min((*this).size(), g.size())); i++) (*this)[i] += g[i];
		return *this;
	}

	F &operator+=(const T &t) {
		assert(int((*this).size()));
		(*this)[0] += t;
		return *this;
	}

	F &operator-=(const F &g) {
		for(int i = 0; i < int(std::min((*this).size(), g.size())); i++) (*this)[i] -= g[i];
		return *this;
	}

	F &operator-=(const T &t) {
		assert(int((*this).size()));
		(*this)[0] -= t;
		return *this;
	}

	F &operator*=(const T &t) {
		for(int i = 0; i < int((*this).size()); ++i) (*this)[i] *= t;
		return *this;
	}

	F &operator/=(const T &t) {
		T div = t.inv();
		for(int i = 0; i < int((*this).size()); ++i) (*this)[i] *= div;
		return *this;
	}

	F &operator>>=(const int sz) {
		assert(sz >= 0);
		int n = (*this).size();
		(*this).erase((*this).begin(), (*this).begin() + std::min(sz, n));
		(*this).resize(n);
		return *this;
	}

	F &operator<<=(const int sz) {
		assert(sz >= 0);
		int n = (*this).size();
		(*this).insert((*this).begin(), sz, T(0));
		(*this).resize(n);
		return *this;
	}

	F &operator%=(const F &g) { return *this -= *this / g * g; }

	F &operator=(const std::vector<T> &v) {
		int n = (*this).size();
		for(int i = 0; i < n; ++i) (*this)[i] = v[i];
		return *this;
	}

	F operator-() const {
		F ret = *this;
		return ret * -1;
	}

	F &operator*=(const F &g) {
		if(mode == FAST) {
			int n = (*this).size();
			auto tmp = atcoder::convolution(*this, g);
			for(int i = 0; i < n; ++i) (*this)[i] = tmp[i];
			return *this;
		} else {
			int n = (*this).size(), m = g.size();
			for(int i = n - 1; i >= 0; --i) {
				(*this)[i] *= g[0];
				for(int j = 1; j < std::min(i + 1, m); j++)
					(*this)[i] += (*this)[i - j] * g[j];
			}
			return *this;
		}
	}

	F &operator/=(const F &g) {
		if((*this).size() < g.size()) {
			(*this).assign((*this).size(), T(0));
			return *this;
		}
		if(mode == FAST) {
			int old = (*this).size();
			int n = (*this).size() - g.size() + 1;
			*this = ((*this).rev().pre(n) * g.rev().inv(n));
			(*this).rev_inplace();
			(*this).resize(old);
			return *this;
		} else {
			assert(g[0] != T(0));
			T ig0 = g[0].inv();
			int n = (*this).size(), m = g.size();
			for(int i = 0; i < n; ++i) {
				for(int j = 1; j < std::min(i + 1, m); ++j)
					(*this)[i] -= (*this)[i - j] * g[j];
				(*this)[i] *= ig0;
			}
			return *this;
		}
	}

	F &operator*=(S g) {
		int n = (*this).size();
		auto [d, c] = g.front();
		if(!d)
			g.erase(g.begin());
		else
			c = 0;
		for(int i = n - 1; i >= 0; --i) {
			(*this)[i] *= c;
			for(auto &[j, b] : g) {
				if(j > i) break;
				(*this)[i] += (*this)[i - j] * b;
			}
		}
		return *this;
	}

	F &operator/=(S g) {
		int n = (*this).size();
		auto [d, c] = g.front();
		assert(!d and c != 0);
		T ic = c.inv();
		g.erase(g.begin());
		for(int i = 0; i < n; ++i) {
			for(auto &[j, b] : g) {
				if(j > i) break;
				(*this)[i] -= (*this)[i - j] * b;
			}
			(*this)[i] *= ic;
		}
		return *this;
	}

	F operator+(const F &g) const { return F(*this) += g; }

	F operator+(const T &t) const { return F(*this) += t; }

	F operator-(const F &g) const { return F(*this) -= g; }

	F operator-(const T &t) const { return F(*this) -= t; }

	F operator*(const F &g) const { return F(*this) *= g; }

	F operator*(const T &t) const { return F(*this) *= t; }

	F operator/(const F &g) const { return F(*this) /= g; }

	F operator/(const T &t) const { return F(*this) /= t; }

	F operator%(const F &g) const { return F(*this) %= g; }

	F operator*=(const S &g) const { return F(*this) *= g; }

	F operator/=(const S &g) const { return F(*this) /= g; }

	F pre(int d) const { return F((*this).begin(), (*this).begin() + std::min((int)(*this).size(), d)); }

	F &shrink() {
		while(!(*this).empty() and (*this).back() == T(0)) (*this).pop_back();
		return *this;
	}

	F &rev_inplace() {
		reverse((*this).begin(), (*this).end());
		return *this;
	}
	F rev() const { return F(*this).rev_inplace(); }

	// *=(1 + cz^d)
	F &multiply(const int d, const T c) {
		int n = (*this).size();
		if(c == T(1))
			for(int i = n - d - 1; i >= 0; --i)
				(*this)[i + d] += (*this)[i];
		else if(c == T(-1))
			for(int i = n - d - 1; i >= 0; --i)
				(*this)[i + d] -= (*this)[i];
		else
			for(int i = n - d - 1; i >= 0; --i)
				(*this)[i + d] += (*this)[i] * c;
		return *this;
	}
	// /=(1 + cz^d)
	F &divide(const int d, const T c) {
		int n = (*this).size();
		if(c == T(1))
			for(int i = 0; i < n - d; ++i) (*this)[i + d] -= (*this)[i];
		else if(c == T(-1))
			for(int i = 0; i < n - d; ++i) (*this)[i + d] += (*this)[i];
		else
			for(int i = 0; i < n - d; ++i) (*this)[i + d] -= (*this)[i] * c;
		return *this;
	}

	//Ο(N)
	T eval(const T &t) const {
		int n = (*this).size();
		T res = 0, tmp = 1;
		for(int i = 0; i < n; ++i) res += (*this)[i] * tmp, tmp *= t;
		return res;
	}

	F inv(int deg = -1) const {
		int n = (*this).size();
		assert(mode == FAST and n and (*this)[0] != 0);
		if(deg == -1) deg = n;
		assert(deg > 0);
		F res{(*this)[0].inv()};
		while(int(res.size()) < deg) {
			int m = res.size();
			F f((*this).begin(), (*this).begin() + std::min(n, m * 2)), r(res);
			f.resize(m * 2), atcoder::internal::butterfly(f);
			r.resize(m * 2), atcoder::internal::butterfly(r);
			for(int i = 0; i < m * 2; ++i) f[i] *= r[i];
			atcoder::internal::butterfly_inv(f);
			f.erase(f.begin(), f.begin() + m);
			f.resize(m * 2), atcoder::internal::butterfly(f);
			for(int i = 0; i < m * 2; ++i) f[i] *= r[i];
			atcoder::internal::butterfly_inv(f);
			T iz = T(m * 2).inv();
			iz *= -iz;
			for(int i = 0; i < m; ++i) f[i] *= iz;
			res.insert(res.end(), f.begin(), f.begin() + m);
		}
		res.resize(deg);
		return res;
	}

	//Ο(N)
	F &diff_inplace() {
		int n = (*this).size();
		for(int i = 1; i < n; ++i) (*this)[i - 1] = (*this)[i] * i;
		(*this)[n - 1] = 0;
		return *this;
	}
	F diff() const { F(*this).diff_inplace(); }

	//Ο(N)
	F &integral_inplace() {
		int n = (*this).size(), mod = T::mod();
		std::vector<T> inv(n);
		{
			inv[1] = 1;
			for(int i = 2; i < n; ++i)
				inv[i] = T(mod) - inv[mod % i] * (mod / i);
		}
		for(int i = n - 2; i >= 0; --i) (*this)[i + 1] = (*this)[i] * inv[i + 1];
		(*this)[0] = 0;
		return *this;
	}
	F integral() const { return F(*this).integral_inplace(); }

	//Ο(NlogN)
	F &log_inplace() {
		int n = (*this).size();
		assert(n and (*this)[0] == 1);
		F f_inv = (*this).inv();
		(*this).diff_inplace();
		(*this) *= f_inv;
		(*this).integral_inplace();
		return *this;
	}
	F log() const { return F(*this).log_inplace(); }

	//Ο(NlogN)
	F &deriv_inplace() {
		int n = (*this).size();
		assert(n);
		for(int i = 2; i < n; ++i) (*this)[i] *= i;
		(*this).erase((*this).begin());
		(*this).push_back(0);
		return *this;
	}
	F deriv() const { return F(*this).deriv_inplace(); }

	//Ο(NlogN)
	F &exp_inplace() {
		int n = (*this).size();
		assert(n and (*this)[0] == 0);
		F g{1};
		(*this)[0] = 1;
		F h_drv((*this).deriv());
		for(int m = 1; m < n; m *= 2) {
			F f((*this).begin(), (*this).begin() + m);
			f.resize(2 * m), atcoder::internal::butterfly(f);
			auto mult_f = [&](F &p) {
				p.resize(2 * m);
				atcoder::internal::butterfly(p);
				for(int i = 0; i < 2 * m; ++i) p[i] *= f[i];
				atcoder::internal::butterfly_inv(p);
				p /= 2 * m;
			};
			if(m > 1) {
				F g_(g);
				g_.resize(2 * m), atcoder::internal::butterfly(g_);
				for(int i = 0; i < 2 * m; ++i) g_[i] *= g_[i] * f[i];
				atcoder::internal::butterfly_inv(g_);
				T iz = T(-2 * m).inv();
				g_ *= iz;
				g.insert(g.end(), g_.begin() + m / 2, g_.begin() + m);
			}
			F t((*this).begin(), (*this).begin() + m);
			t.deriv_inplace();
			{
				F r{h_drv.begin(), h_drv.begin() + m - 1};
				mult_f(r);
				for(int i = 0; i < m; ++i) t[i] -= r[i] + r[m + i];
			}
			t.insert(t.begin(), t.back());
			t.pop_back();
			t *= g;
			F v((*this).begin() + m, (*this).begin() + std::min(n, 2 * m));
			v.resize(m);
			t.insert(t.begin(), m - 1, 0);
			t.push_back(0);
			t.integral_inplace();
			for(int i = 0; i < m; ++i) v[i] -= t[m + i];
			mult_f(v);
			for(int i = 0; i < std::min(n - m, m); ++i)
				(*this)[m + i] = v[i];
		}
		return *this;
	}
	F exp() const { return F(*this).exp_inplace(); }

	//Ο(NlogN)
	F &pow_inplace(long long k) {
		int n = (*this).size(), l = 0;
		assert(k >= 0);
		if(!k) {
			for(int i = 0; i < n; ++i) (*this)[i] = !i;
			return *this;
		}
		while(l < n and (*this)[l] == 0) ++l;
		if(l > (n - 1) / k or l == n) return *this = F(n);
		T c = (*this)[l];
		(*this).erase((*this).begin(), (*this).begin() + l);
		(*this) /= c;
		(*this).log_inplace();
		(*this).resize(n - l * k);
		(*this) *= k;
		(*this).exp_inplace();
		(*this) *= c.pow(k);
		(*this).insert((*this).begin(), l * k, 0);
		return *this;
	}
	F pow(const long long k) const { return F(*this).pow_inplace(k); }

	//Ο(NlogN)
	F sqrt(int deg = -1) const {
		auto SQRT = [&](T t) {
			int mod = T::mod();
			if(t == 0 or t == 1) return t;
			int v = (mod - 1) / 2;
			if(t.pow(v) != 1) return T(-1);
			int q = mod - 1, m = 0;
			while(~q & 1) q >>= 1, m++;
			std::mt19937 mt;
			T z = mt();
			while(z.pow(v) != mod - 1) z = mt();
			T c = z.pow(q), u = t.pow(q), r = t.pow((q + 1) / 2);
			for(; m > 1; m--) {
				T tmp = u.pow(1 << (m - 2));
				if(tmp != 1) r = r * c, u = u * c * c;
				c = c * c;
			}
			return T(std::min(r.val(), mod - r.val()));
		};
		int n = (*this).size();
		if(deg == -1) deg = n;
		if((*this)[0] == 0) {
			for(int i = 1; i < n; i++) {
				if((*this)[i] != 0) {
					if(i & 1) return F(0);
					if(deg - i / 2 <= 0) break;
					auto ret = (*this);
					ret >>= i;
					ret.resize(n - i);
					ret = ret.sqrt(deg - i / 2);
					if(ret.empty()) return F(0);
					ret <<= (i / 2);
					ret.resize(deg);
					return ret;
				}
			}
			return F(deg);
		}
		auto sqr = SQRT((*this)[0]);
		if(sqr * sqr != (*this)[0]) return F(0);
		F ret{sqr};
		T ti = T(1) / T(2);
		for(int i = 1; i < deg; i <<= 1) {
			auto u = (*this);
			u.resize(i << 1);
			ret = (ret.inv(i << 1) * u + ret) * ti;
		}
		ret.resize(deg);
		return ret;
	}

	void sparse_pow(const int n, const int d, const T c, const int k);
	void sparse_pow_inv(const int n, const int d, const T c, const int k);
	void stirling_first(int n);
	void stirling_second(int n);
	std::vector<T> multipoint_evaluation(const std::vector<T> &p);
};
#pragma endregion

template <class F>
F Berlekamp_Massey(const F &a) {
	using T = typename F::value_type;
	int n = a.size();
	F c{-1}, c2{0};
	T r2 = 1;
	int i2 = -1;
	for(int i = 0; i < n; i++) {
		T r = 0;
		int d = c.size();
		for(int j = 0; j < d; j++) r += c[j] * a[i - j];
		if(r == 0) continue;
		T coef = -r / r2;
		int d2 = c2.size();
		if(d - i >= d2 - i2) {
			for(int j = 0; j < d2; j++)
				c[j + i - i2] += c2[j] * coef;
		} else {
			F tmp(c);
			c.resize(d2 + i - i2);
			for(int j = 0; j < d2; j++) c[j + i - i2] += c2[j] * coef;
			c2 = std::move(tmp);
			i2 = i, r2 = r;
		}
	}
	return {c.begin() + 1, c.end()};
}

//return generating function of a, s.t. F(x) = P(x) / Q(x)
template <class F>
std::pair<F, F> find_generating_function(F a) {
	auto q = Berlekamp_Massey(a);
	int d = q.size();
	a.resize(d);
	q.insert(q.begin(), 1);
	for(int i = 1; i < (int)q.size(); i++) q[i] *= -1;
	a *= q;
	return {a, q};
}

#pragma region Math Compute Kth term
//return [x^k] p(x) / q(x)
template <class T, Mode mode>
T compute_Kthterm(FormalPowerSeries<T, mode> p, FormalPowerSeries<T, mode> q, long long k) {
	int d = q.size();
	assert(q[0] == 1 and p.size() + 1 <= d);
	while(k) {
		auto q_minus = q;
		for(int i = 1; i < d; i += 2)
			q_minus[i] *= -1;
		p.resize(2 * d);
		q.resize(2 * d);
		p *= q_minus;
		q *= q_minus;
		for(int i = 0; i < d - 1; i++)
			p[i] = p[(i << 1) | (k & 1)];
		for(int i = 0; i < d; i++)
			q[i] = q[i << 1];
		p.resize(d - 1);
		q.resize(d);
		k >>= 1;
	}
	return p[0];
}

template <class T, Mode mode>
T compute_Kthterm(std::pair<FormalPowerSeries<T, mode>, FormalPowerSeries<T, mode>> f, long long k) { return compute_Kthterm(f.first, f.second, k); }
#pragma endregion

using mint = atcoder::modint1000000007;
using fps = FormalPowerSeries<mint, NAIVE>;
long long n;
int main() {
	int n; cin>>n;
    using ll=long long;
    ll m; cin>>m;
    if(n==1){
        cout<<(mint(m)*mint(m+1)/mint(2)).val()<<endl;
        return 0;
    }else if(n==2){
        fps a{3,13,40,108,275,681,1664,4040,9779,23637,57096,137876,332899,803729,1940416,4684624,11309731,27304157,65918120,159140476,384199155,927538873,239276978,406092917,51462904,509018828,69500660,648020259,365541286,379102943};
        printf("%d\n", compute_Kthterm(find_generating_function(a), m - 1).val());
    }else if(n==3){
        fps a{6,40,218,1126,5726,28992,146642,741556,3749816,18961450,95880894,484833212,451616850,396892232,686360042,981035162,852304262,13310737,963770471,287207712,160261393,773383718,96956388,687167308,497530903,444375838,604326428,109192343,567326764,44956786};
        printf("%d\n", compute_Kthterm(find_generating_function(a), m - 1).val());
    }else if(n==4){
        fps a{10,108,1126,11506,116166,1168586,11749134,118127408,187692415,941503421,64334502,171422003,349404639,414370691,229496053,914944379,534647146,212952522,902520681,724503478,619605102,166273790,619390876,836310385,686953731,577520663,729784801,284152723,990192910,985602944,184628568,143013864,120357458,135871979,693625981,923420525,935325709,232157437,179845336,642659777,928044617,599227641,429003717,808616660,796217953,104253038,790833226,173559765,354895468,283511888};
        // auto v=find_generating_function(a);
        // for(auto x:v.second) cout<<x.val()<<",";
        // cout<<endl;
        // cout<<a.size()<<" "<<v.second.size()<<endl;
        printf("%d\n", compute_Kthterm(find_generating_function(a), m - 1).val());
    }else if(n==5){
        fps a{15,275,5726,116166,2301877,45280509,889477656,470102989,131617800,543346538,672693081,528691884,433100319,259856352,631703746,121492784,65000963,67868821,431503520,556143263,898859209,822402657,746831347,942022314,42461886,245383965,159194955,442319965,719053964,735342087,986228635,385914410,746460380,499191314,294132890,429534325,53306515,69797919,520148741,67524590,131525006,212068789,48189163,744481802,784588217,472300215,20257573,506104402,129522484,887689193,43853833,543027098,470146768,95649760,578040016,125364572,32787914,139313990,713541877,395048004,58211160,741163082,279667841,863539083,628324240,632065512,233414550,425723447,668541542,395252599,948108328,415936460,936971286,807826611,208563368,385680591,915191638,982414083,119125504,245116288,652724547,553342192,353630600,164609785,388450582,428700037,12346034,723785521,759402482,991725165,966973769,273572834,930570812,280051753,519978288,374543182,92200418,226676644,296219848,527096603};
        // auto v=find_generating_function(a);
        // for(auto x:v.second) cout<<x.val()<<",";
        // cout<<endl;
        // cout<<a.size()<<" "<<v.second.size()<<endl;
        printf("%d\n", compute_Kthterm(find_generating_function(a), m - 1).val());
    }else if(n==6){
        fps a{21,681,28992,1168586,45280509,732082734,37461992,885687205,403247903,630794366,96311199,188560385,132214957,81864959,656832813,129969437,337127917,885747691,994734031,901081506,113735510,330166803,692897482,221245902,823578678,149151767,513212823,565413378,343413792,552163984,401017125,775469314,768705741,822998669,524634565,141276343,644398112,617812249,791340223,983870515,203398182,625614815,683890375,368195928,142285464,986226417,160965035,405204827,206471233,652493150,587867820,808610901,707659600,22802536,445444835,187616183,160982744,457176050,436730256,169883893,240716120,405440669,340484060,656210817,36771327,96126498,306426249,814430155,444930212,988328253,540530995,382743352,520556011,247236452,220449493,166029981,836928892,713012422,954252270,210134677,648105608,574260821,257748962,442563484,914128913,335893401,10612419,644215155,701674251,791425433,275022106,639393769,990275298,335101602,666947295,13086669,924423722,440358685,58917454,854634653,222563675,986452944,446560406,446339799,591900594,128960647,452436634,623814114,525257515,200495503,761757851,718952409,535847882,645061699,693963653,46678719,466133474,594295562,399559391,11097962,461778954,483386287,217580794,516089910,909297529,427249009,903830872,948864754,417535749,861690114,993338477,163694488,704688997,410415745,819049617,768562308,219587990,988235140,638477009,906083355,986424230,21490100,639637730,572881707,766595872,767939846,800732317,706345604,549051521,625193562,16831162,641408131,715352261,252575415,849525236,451254833,154836312,875072124,857138289,85504824,43664162,328113172,469628778,738455978,301383170,227452743,643952736,421179753,838409907,630538122,568667001,265423706,249151164,60716612,217355205,116129713,63635092,905389532,184685401,515736984,227392078,31713055,76862194,112672382,534885464,262104899,168571936,67257989,313819794,905116518,665071482,636607859,194818405,121405681,853051068,300594872,952805075,156961259,590791197,898252277};
        // auto v=find_generating_function(a);
        // for(auto x:v.second) cout<<x.val()<<",";
        // cout<<endl;
        // cout<<a.size()<<" "<<v.second.size()<<endl;
        printf("%d\n", compute_Kthterm(find_generating_function(a), m - 1).val());
    }else if(n==7){
        fps a{28,1664,146642,11749134,889477656,37461992,949940562,34890374,408395779,465431123,169444072,476095424,659247954,873440607,926228358,615656154,946323264,52968124,753942504,466886220,131497623,574943442,651491966,558045773,251030380,281770571,626734327,538734009,338782739,544266404,882070771,638524752,866251039,377115307,677270990,923683803,407681394,135644897,799433050,734586418,252356851,562319011,202766611,459305661,237631148,937873188,999735041,471421437,196454674,548587822,155433694,513218158,425727801,201766011,618282733,853358524,794224019,317787454,420202005,208101995,561508157,165138107,680690785,440574802,642204069,1519935,740668820,993620892,358321040,609591537,544950607,452208170,885834624,821590676,398458087,516061104,713420418,988022777,345184826,285034175,821685364,13669476,704448103,129864472,272789356,791468167,22642555,191074948,725893030,621310461,91319075,716141215,100651620,124026881,366140815,685675711,544588613,31892809,733368799,814661720,416829950,25354705,920576064,404858750,224503153,408647840,32879424,449601451,954308700,384324116,674296838,792515237,188224955,323348585,972509240,558237931,478379644,769454589,5532215,665030504,378063244,50177022,152536855,592606999,936002695,561844587,98320627,393845743,234288387,975460550,94761064,230083310,437478027,493404365,809166706,952865395,30537948,269093029,454344596,528546169,743583991,647074729,593751773,863574928,753557944,354148307,464934709,275033859,450276861,375178856,24286587,880771043,120621725,710396662,135056587,742687865,845401042,8181486,277891374,585736419,570298110,955283694,601817563,141857657,613931527,134904117,127307580,914760872,56527073,515151064,85256390,867641311,644658123,516456196,546485053,695768127,950249035,737354235,328196921,664437558,654797167,540686071,250077160,487287552,591837921,979485087,490297242,633678446,990298548,379642970,702481128,584942893,361720238,825880866,772590735,172182904,754431546,299502652,249050691,335001904,230296477,624204288,692367468,559310443,838878897,487986149,566227276,518043209,592538136,138670606,504405049,252553466,871876658,899807947,483430873,691627537,222857969,795092244,368293695,768052890,697322358,573816332,825591677,652492801,526261993,975704775,677628081,116620383,439967590,362128951,672319242,574102271,350904081,199464684,849463038,886655361,223485420,319695722,767450461,688429206,598751129,225406154,353550552,98188261,962586132,351427959,41167573,126283438,801928140,530774617,44264407,602460015,61008882,302058086,906154632,231505141,652491961,47839345,55293956,145231825,307920923,408202725,510473597,75219688,157343985,917480789,103605310,842950390,101027707,28793070,717261125,758732082,158282973,502041348,88400441,587778289,226310004,574669991,764559581,756363639,614962461,790643571,149324328,145554685,437398154,438739802,922467738,388741006,833892011,180024031,324080539,286487275,308749486,290106846,520867996,591917943,627868971,364622578,921885725,965742313,948877022,704039082,956113451,678857977,321401847,167938672,393856197,808025503,320963438,706550784,844136492,669955528,297253668,394528415,834378234,984963756,943035612,889279746,691625657,151511814,633374998,11156661,177860660,526965344,720117942,677315004,43154458,29163605,704506502,683525032,315857847,191280597,827302311,699421298,212010427,794556814,913280489,139164873,268649425,876508475,417530149,801828700,557926859,663339429,431411356,247878361,567938231,396918035,536975307,23869544,213323065,829981561,293484929,745338799,612848888,700199508,304928068,637237106,510637206,575567485,286763332,606725159,18008540,758299731,373138922,527449398,277338660,951314381,136928877,517354155,958264645,476381296,517661699,418951513,594925089,766767569,632423321,158924453,216993745,87677436,460735106,213378655,75798721,810498703,498131595,804233141,46616599,126236000,75726097,12494566,137140335,462013348,514605591,36371762,900304397,353370158,159178736,385565940,202256034,749707904,585244419,368607383,161372043,902321328,332777236,497271620,892689964,417308139,992400013,112355400,862835116,840275498,926482020,145476286,503687099,819367240,94465356,29534741,404125775,994606265,702779052,727169224,488931844,908250586,965893044,454596515,504943446,536580797,887270975,336238694,42825016,61715600,721194359,926269327,455233124,176379457,401022098,997694805,736660305,28764247,43601269,915483947,251386637,547146660,209214260,767872658,198009594,304348327,535645794,590354800,641872539,676928196,892980837,934433856,794932752,437963681,60438779,881980372,633986342,717718530,792975552,84059053,729878948,704864625,410844747,108887832,457337849,414985017,131963858,741566198,699925321,907788357,534135778,84813473,574894621,637795121,591882868,317003937,959093967,509688013,976315900,181502120,69921532,496704607,258795001,74876814,934998100,851342700,873185906,86019015,341788146,252606682,176203832,796840690,743454462,952296567,275524869,138772297,457478921,534369146};
        // auto v=find_generating_function(a);
        // for(auto x:v.second) cout<<x.val()<<",";
        // cout<<endl;
        // cout<<a.size()<<" "<<v.second.size()<<endl;
        // cout<<a[m-1].val()<<endl;
        printf("%d\n", compute_Kthterm(find_generating_function(a), m - 1).val());
    }else if(n==8){
        fps a{36,4040,741556,118127408,470102989,885687205,34890374,247777016,233426110,328755371,705627253,787442872,382905968,14599213,54410761,601006292,612557411,15449456,990194963,286282085,699722725,781620769,840139026,489073872,334785849,435236311,109774734,741619354,198733961,979223831,316303898,39151097,758722723,846456337,302710767,751509519,910422866,269441528,739223079,47041872,144990978,835832181,94144832,432122371,718847361,143249505,202420879,524474077,175432350,259981775,949834434,650788361,314338901,308488393,925015945,735629952,55340122,870087004,914406437,652461932,824517283,13384791,734924498,195917202,347913012,345009223,72962601,728865665,529666843,443583543,797807890,499559112,582526183,750449603,794171249,339435367,795879914,610395113,651525515,665256279,771083632,124044838,103256298,555278857,168723782,37135886,926137424,193565944,44104251,848927128,311714530,740363205,103826476,426742610,675142274,731839743,444416323,663478468,724122696,351972777,394976529,438819547,910482232,104665901,409225876,167205682,514913255,760105145,29299318,710711305,114816263,854763814,393789740,110116602,971095517,965304627,656067527,345333181,54369787,393350947,645767328,278297447,584309442,643959646,760481447,306899117,556007296,90782544,501999191,487093902,851119019,214855164,290938704,483935411,931413698,87706720,543982301,557974404,993894344,617966931,450284946,530064541,635450110,955879320,855098870,534537883,745899211,102957101,662330955,760521286,880202513,410332359,896841550,21942388,327590993,607470931,510274101,755158989,271684724,681115728,979634385,116288824,441075062,869557219,498624604,668265455,563569496,411144207,372553915,26571455,299681786,483501145,332251237,514296631,262088005,767350800,242709545,312245270,625558060,630739736,166453361,987400268,534085288,177342293,635886216,360697926,830064107,142999667,796390630,541632626,524331979,832128250,56784302,599770934,420185002,36118708,960687380,886180310,494123322,256629996,167297430,422622751,387880447,805197257,990906673,197392117,409215677,751867399,114891717,20016317,539423303,506437722,420323843,17970683,326175155,607163024,810675077,843118080,586603097,332437402,683685949,604167445,591515392,281318475,78155302,77262870,295568742,84378564,642943804,12418388,229594263,734305604,17384828,186823879,593406287,961690928,25278271,599757507,378599083,885999372,931931154,847818732,310703306,179718037,657210250,145528035,460498835,941558183,335135033,141616629,159440568,260876848,890714211,188331960,684788951,962770200,647749365,692000110,84789890,537064226,34450693,41361159,550194872,245249510,900342927,708273455,11582750,128969774,512056024,55621840,349004103,637116327,221258619,579454604,113893155,576214565,70474670,23918406,481813326,650352628,246808992,284149773,322921320,932867440,994253316,940618752,728504628,428989277,122474883,119546567,24132989,106306057,431011676,611024275,216092722,58878209,120907053,721629563,912245906,362994491,77928369,598179975,862251408,302060801,740845851,459478020,470575531,272055896,271404799,997912850,546477555,102801686,821058456,253389281,766070116,630671870,387593406,363890599,503970373,198459011,993364983,210948547,542855600,819226189,105570790,913838629,104902492,762607730,954174415,72362182,262189042,660554698,644882931,306650491,22189921,453123535,325669077,343206525,974951457,351413353,739439727,691749300,370158155,944047087,188614448,382554560,385741341,62378861,740868823,256532720,721260792,546722312,476298563,606762613,98776597,898445055,605244416,333859175,433695415,401161555,572855900,243667256,85343275,675159111,922771403,996753883,954048792,469148681,19943310,296231983,99393046,204271242,312577414,956614050,159362747,723539464,111719269,894138283,588450712,602782641,981925081,900433722,180543976,267328359,522848269,4196876,67000221,107779275,321728788,528597009,269434052,964941752,949825535,975030569,458728260,549511657,418171228,245570031,648210002,972434486,581872841,635344873,319802131,678265430,806155028,954458488,526854316,847377932,635338258,992797405,996032138,354562941,45336905,183006406,369367986,247817599,491651791,494803388,962480389,263666033,589248787,333002562,984917436,533517314,834849849,760791455,813814450,264438765,491534108,918145304,179243081,160538845,82373668,881806227,278695929,385349193,933393279,582444056,773641996,840937519,96345613,817752724,256578507,578658131,888553230,520544388,456331128,516837372,204008969,759828334,835082256,253914433,679107129,399776524,263641485,965389468,273920466,217978642,525012339,943300399,526528430,502684771,227319750,184383544,997961184,602742228,532755275,833719430,885093194,163222309,767604092,441111497,336002325,145020301,447897866,342728410,567522451,559761513,223634210,733274354,395895536,441758545,522228315,742539357,836415813,737295437,84803431,254857484,689895714,104233342,56504993,929273450,508576898,983431326,316933462,434800355,77235158,345405176,120253752,548205524,600098257,35022114,875707259,680477575,229617110,897981711,958283444,278645046,201461953,518254720,89544139,76537049,809062576,929661490,534619096,351906998,474321902,94774220,583374082,381426481,793949122,40598040,690138089,751409585,895948817,358453901,541996185,679215362,827412723,194647955,494116925,627452576,386736435,992534555,583458452,458954190,452395538,433411190,83035941,133921863,36174665,36124417,426067768,240516213,298321037,125731962,829618798,226783967,849360163,9358418,878892634,654427980,444939351,483762653,124363484,740949638,814981766,173769879,401679991,749523229,669826907,170072113,276845069,269247535,53714362,162616522,8844101,27290501,3600440,467904457,40008617,7204184,150738855,792362729,45598948,977261011,853230684,179122538,735619416,100129992,662288906,901642908,419357329,601897966,32519958,147937253,520035581,619074117,761871430,445631922,243303159,827711028,744937946,15911546,957399971,741820066,751442971,181021120,285585126,43235483,248795235,854000666,173641303,266839482,987409220,378563959,468878417,63384715,583634817,600378381,929835761,523740002,728955446,590492614,34458124,279343928,195735676,46664993,254933367,505006549,771021821,874348002,296227212,746790822,973757367,201451382,930317101,405949760,947854925,140353036,684244003,636049742,835378430,463831114,304603585,373625600,891807970,621955729,786099782,899819251,848424803,509286581,363251432,837152964,634098023,745841578,774669131,866733359,655971755,187393846,319922127,720057338,143719634,477088747,425291430,398255802,256131421,78883326,114100113,770420842,755327183,747258719,996552064,520685782,833372308,601862212,109744429,366033629,504910343,728140838,674391946,378179746,992539472,211011762,925730351,267475379,758877346,369571469,653353827,563034115,972310822,277104696,915590075,98810072,731606997,640278519,307568693,685441807,172167423,978621116,961852572,989826955,21291179,563398915,103195667,973253924,911079601,629605746,358705717,195136341,795674611,183783796,818543003,40310634,782810418,506472561,654359104,180610994,51656371,687758530,813242079,800205441,351202196,975494087,55601797,373634346,439431459,619119164,647304542,891479811,431853457,287487483,629742587,569968708,111438526,474687258,615835250,934504676,992813174,600110971,868747473,62311160,187294885,726603666,580421910,107504750,202518335,209401214,750362163,238391154,329709553,897244202,199259178,241103456,64575665,317473108,680196000,87902608,83745239,854416432,54536239,902020201,94740978,4164167,864704157,181992095,923657278,435521609,884744268,55567692,126570864,647074371,51553578,913812423,98567378,329986815,663376244,225267301,973160221,539136220,217559248,931911786,587428633,94744815,353928523,341411646,307460308,496935114,652278861,272604011,138888596,650279116,670561849,116115965,506649521,54437250,781668255,374349844,387395281,686586780,545916573,167122731,606102164,593079412,780490689,308961217,256330327,24468604,309417559,112329602,872817313,45580419,633389596,696124581,32022073,985630149,435259199,22149074,446732551,787947188,50464752,734799326,913174572,294271784,866788058,928220338,85287707,945950495,115564251,106618802,718345725,645319474,293372194,975736384,664216920,947025831,958418034,13767821,349045969,79327831,946042175,154207667,712307426,223878962,770796470,215613926,380195535,789269125,581405898,366770513,10514844,924391405,794660131,685109943,832803204,455727683,548316761,773390723,620488937,485658505,206841056,330838322,372915323,438743303,698869851,361619474,537311340,59971662,348382523,547779210,921054244,944718928,385330420,56048324,26672556,163338772,63970117,234730456,490340750,607318818,155083255,767954795,760013475,112335651,2445670,300031842,593601578,245901541,564165280,606924410,736706628,197828372,21437612,119678072,388447782,530223045,437299744,345656828,635554901,923943421,277703203,878518260,216643693,468586236,936395669,471648523,576855968,384612388,393578616,654487914,401809618,797419757,18972980,36053267,272741564,793909680,463720051,814488998,215499317,685632084,39929748,128191167,938819261,118772101,266535988,323013745,142341541,754989061,367966689,934159497,606931378,503523351,311158981,171538143,797721937,676232642,181824380,749320794,822148402,726776285,822947150,889225922,461263487,566280228,317498949,494935074,743000459,249271449,966002888,860962687,199029578,992221694,223813562,906255478,686196349,467214135,390333726,751265049,327306059,435516156,824736883,860365635,983874997,487483457,563212662,727702337,474580077,775028618,786209739,407503777,275702361,527165757,126644177,635334305,554042691,717149280,706258850,46655029,102608854,218903998,174673284,866142683,549528484,253966420,388354495,497574522,305842629,212783502,872491300,257578563,918367602,641462612,128894525,363618531,681090608,791960386,797396586,692149161,169768012,844522775,467580667,876013312,328574627,375957473,598772171,576235702,904597431,698268540,10628227,62409734,711372381,827063867,652076379,700144012,729471029,31482134,762266917,822481704,476976142,923668012,938137997,695655089,932739133,991985347,270454066,811843004,128791801,201699782,832612902,786327672,274424357,196115638,70008299,283746236,911245497,683421130,710918512,390057244,452845316,305841220,929948147,953952757,3499180,693272552,71834290,137023431,706219031,382504734,283033914,498784685,52290093,118686070,814465437,197871750,538681159,733137306,485604993,478447223,463915383,930474859,750062980,680691702,699836704,2325473,986441503,159527686,187709790,953498896,983846637,539255322,429012692,9270892,932027573,390901172,1039252,628665667,988020983,268875115,855920090,47873766,379482777,163732116,195705314,930109155,255751038,954375653,760682808,553231933,945149662,267235843,976507802,940467889,323409974,474060097,626627329,49676119,284598402,170448764,644604219,422849719,643756491,585267376,333322243,340967979,142640089,233659613,495739228,90966215,971221658,567992293,236444469,950311139,77430926,879245591,312953269,474292574,210268848,732371189,7154556,625301412,120195180,213859177,994903600,618779903,798486765,728965317,708936948,401212159,424619135,79784376,910529762,718783911,767712276,105578010,947040387,133354032,885939256,382243340,810631059,281930107,986654887,668646080,467249913,689036696,462431317,476469531,495816517,46083623,744296256,172169218,54219993,12056425,384285926,746849867,802165037,965117713,2630913,201118046,48795589,509721353,980727862,672319045,498147048,358340044,474937788,576200275,641830418,465576380,528031158,980570103,688178429,892777466,292523611,530002815,867454715,165559084,521918900,819844832,13159153,661208657,464726027,791377095,509146497,734695374,445520106,550292017,852822296,255697729,882279307,152726015,250472601,343775149,590767861,534169162,740934609,968136115,55190993,237394863,80090323,922630467,105843208,399998421,994688142,668343657,595201846,210743495,980663232,357327505,290987433,25339916,671790221,995943475,983697318,933471409,225950871,755501332,980351226,831636703,421859456,537372270,734485019,898893990,858775433,529401590,578347356,42605441,338631766,616969141,55689081,822221916,27983059,696392226,670630003,926493453,166075000,40393885,74615778,864408852,487256911,107383230,861899142,715943603,432075793,579684350,7373165,774719822,550647236,156538467,941512864,678434695,36504801,610751616,637410719,403690415,755404172,730967088,482998454,633763187,425479705,826533912,81162304,396798543,570572820,293761501,766590176,110894898,180648223,734094838,647780492,140290528,589786172,280183998,641813681,984422348,799624380,786334357,810329474,802257499,742037558,196190431,811017727,754995732,623547567,459853708,371816355,423756225,547736616,727215836,764202465,93624313,683127725,261795325,326103302,25044445,559713458,738805421,882691130,13444529,11327418,391529317,769704799,887138831,898878747,505181331,756770886,656290913,331709987,597258270,53245283,151770191,772973427,796914761,306963276,917922797,887974290,995141004,380311918,435048326,125733715,678455135,728560278,737824088,341797054,287902027,14621395,236203274,780751232,917926844,64551905,66582819,681915040,327440044,255384086,426044317,974969164,77529967,891522596,528591656,108629211,383773838,24470684,327327455,222813688,642962586,360350859,438721715,317125845,646965,263343705,138736333,647697401,287797303,220330413,966691061,188770759,6724123,338606547,110561606,174278222,920597145,871096963,439172452,922990692,591222580,611344934,97957695,196288978,909829744,168584472,950300007,448321155,407258243,768721944,30903495,669358698,637015996,555813577,557571586,69664776,983143029,289578764,235207115,410045523,903871682,504205720,217687012,587026637,902660814,186467564,463461624,925752054,796723556,457161445,51191718,563249778,833645972,411391764,538256033,111574414,675299673,54526118,338206086,776595029,331318392,932625151,844658729,392585074,540136626,506378696,176322800,111797221,533040686,164897101,392211614,718752599,627601436,496397113,838922277,426767009,406895494,92231323,185297197,620691296,497594209,700452007,213238181,424196442,387250417,817502637,335354825,800708599,493493390,352978819,366043115,453167038,716733072,226602613,108425179,575171338,12300908,462865587,704880926,676001984,719134633,326955375,116718415,879220488,349369131,600088954,515124870,917498676,825874430,446335761,910612659,447836420,700444901,866609318,109581506,902654856,230991387,639396616,221802980,388171180,271807603,405634653,738714649,298645606,726181576,42755106,486882306,334896906,472314412,871712752,147346877,716595863,634158022,808479923,262500736,868655469,958568880,960314699,82156314,963543831,720546122,421216333,322348696,426401390,561507415,909923250,726398493,484189930,786972420,421217225,700322225,917619086,600353017,3641869,801144737,196609801,308562513,807651579,443750007,994404106,617225135,933854597,499109687,705743841,41670187,335728526,178344301};
        // auto v=find_generating_function(a);
        // for(auto x:v.second) cout<<x.val()<<",";
        // cout<<endl;
        // cout<<a.size()<<" "<<v.second.size()<<endl;
        printf("%d\n", compute_Kthterm(find_generating_function(a), m - 1).val());
    }else{
        fps a{45,9779,3749816,187692415,131617800,403247903,408395779,233426110,197302784,177620321,206888828,835061252,770003207,167817536,517820843,580617827,469175694,251779825,370582103,72645164,713328911,277616510,902795788,659852725,220506451,987735057,337008278,326694483,929531709,623473947,796684890,777051644,795130911,868689620,888962474,15266105,133906102,896971307,432781360,609904712,139195228,582320632,810000435,144947710,694533822,353828777,974567746,545012102,655590198,684583110,709008352,516538184,177659042,730381723,46966182,70580724,546296538,649380101,839329069,521579662,795443379,918648017,416884199,467381920,180180330,922394205,388926319,338398209,519862997,15436054,832899909,25205988,638023458,397967187,958525485,625245409,761065828,308642848,984865575,166574801,351074508,483949359,826042702,587151802,332893090,23588721,198575871,217064634,935342647,875830166,870762060,431430866,714037905,451514552,118685251,876908840,648215587,848279668,60298648,631459253,423970402,946540283,520092027,98956341,792001638,336970096,931916670,592163792,698538791,255778677,599081543,736931826,498542055,487642144,167722474,425497074,479036070,196741185,39983686,490171826,41410688,950392180,499418290,916512858,995578975,364239372,287759310,305160181,776807436,795631950,394372202,993536736,574952319,609892554,374430406,859025147,436507546,532241817,70196027,667557733,86629981,53437441,215255354,775586987,386301783,329730035,202594580,163573385,90440286,830055244,592282175,146234819,713607860,431108208,391672172,89707230,227887893,635772628,670074546,823064293,429723599,720075550,708101376,728992627,35839866,649628048,777233024,769395244,273231976,452388241,103609465,50984607,571111271,37433616,645071594,241717405,852257157,792730997,762093846,260970344,710690387,581362111,325183396,887018246,894572200,248056865,450822007,28780679,485097554,610718927,844021940,806875641,356112859,159635847,788536148,115844061,32006334,343606685,949709181,501111333,368083991,85114366,231716730,758617505,42613424,792424028,406591750,7556235,372313392,875852936,303229657,493990389,413068577,970321428,914931582,883280547,348694252,48829705,693879473,956820845,494398843,524838672,55642290,291803820,838072276,937627886,352806075,872719356,645619108,203657091,833772501,188791198,15808272,336497713,294256664,801099446,152749995,41154832,192492036,312034558,714016971,939095632,362217612,344871905,183574935,889188174,138994256,960429161,296389559,883734447,484177868,83759713,357767259,405799384,404997964,179592455,903922102,309177362,762328559,846181321,186860329,535482051,303516149,218656364,107450950,239712834,878534309,957325925,369018716,743188094,890784475,179418699,403243176,82350077,760467414,628649939,536068242,546840675,460160401,131727617,556807821,103868149,100658424,320228785,310512098,723638547,644759206,54096166,438468025,280923557,715718353,545633130,123399383,171267284,991718619,983352761,402614189,319762846,922715169,183148106,404824713,482568353,237420087,669034731,275370689,906758281,912995718,736734514,669078916,551700747,844999682,490707946,397056376,72201274,440950741,308110319,99342341,252577468,439457763,862615164,97430404,650977533,227567872,732837766,486412310,424158571,314727501,706889056,657623511,936876993,355562470,9669720,793140369,959968300,899351234,219020216,880286167,595856391,493610283,799709671,824990610,720595839,329639104,976749337,936889221,809494863,315709609,237042146,110330913,567862810,101728268,746956576,529866255,586725298,648040801,779748452,153236583,914584631,749408847,513718701,14088744,993137657,564190068,564615128,218058108,134675641,474742395,687879968,690548088,277156362,833518401,580665444,577772528,19376544,299323127,895099027,299338547,839803398,687138570,578794727,71021961,41918341,510329763,609712540,451003507,709704951,186996194,578245109,487769767,658075788,864769755,506366568,233278984,86797707,695583509,153704084,307322932,831266923,199868472,103620682,993020713,659107946,396528525,448813397,73914984,907386095,831778457,594736347,150616395,988883526,366215643,167086401,868932945,313717943,593312471,235565012,521329248,311252446,123949902,964499849,144982401,326364967,391588166,501164095,279706676,683502822,592927881,202357005,297878695,111559939,437962853,837545570,371947446,187758155,101943565,305769633,487510260,916387514,682044268,61059324,657929288,460684128,163896142,161536407,538311886,723564214,36418739,327436336,989827281,124248645,832708688,882308790,710452531,77716353,875129876,836074411,531835865,56875321,833407105,423331035,393581722,167353704,46338145,795984501,429448793,921170554,895713357,399606530,448677100,376663936,565811400,301582936,103096130,89229646,456280484,935984940,257863967,62176804,520077003,989724020,230216016,198426323,232816551,723398169,947598119,145563483,543560195,769283254,687695853,412141785,458246892,322562821,870174788,792046447,992281653,261650102,321433331,28258915,361339155,916537223,304030644,26483722,311683688,962388783,635976431,109322303,111089464,562711339,932659823,884184806,961770497,482763443,787907009,283606372,844167426,96801505,102993913,616787769,332259272,90020691,33473958,108789187,901500422,168357636,853210301,871337077,376008840,609311701,33409148,458480523,530786778,390698056,481382022,680007463,849208790,270019810,368593263,287960378,683678741,840373286,472091096,256821798,909688373,636672904,857109891,992260814,638259714,682582093,715207690,600484323,181860536,177868141,849248564,743213709,255749170,601589780,577202203,715681221,735331176,522995960,337047396,380280967,562020808,449068543,963757501,321956499,151307217,161277903,285233282,762020021,339297753,69679348,52568303,535629098,658030018,319086680,600634301,532594728,293331051,603165887,881090116,441710021,197876329,311209998,65489057,438038471,846586492,841740111,900892505,272268279,272662986,89882804,789135775,548746487,93712454,214835785,687205843,809953436,716639879,931867150,5763196,404820388,529438877,222826259,393767310,372063277,755012934,553961581,34305285,137826363,970617902,758748623,22630688,297099624,233382191,919549105,715661682,204181124,621028315,733111353,820512193,577134999,902996456,829943695,846032894,905693877,542196551,252622955,523732069,530997965,533006837,460888302,533952669,844001205,812367056,483211338,158530789,288773918,681553155,968699783,254686618,449601998,599196037,225007854,290070160,539848030,608861062,188322344,747926660,538066172,847178687,798739308,292443380,645523492,583709863,519984309,947227788,785996221,849492107,217296632,379082083,328454321,948218307,458921548,733036260,335345610,773876458,744463437,69765238,106787889,312188870,578318834,7590839,644251670,957688430,335704885,472634567,890314526,887231598,869685716,675313178,908538033,362098899,320019526,244292819,322269049,505039770,483852205,866472202,694039567,823738103,892325140,758360001,346368562,815348254,412182503,471602176,990001493,666290216,161636116,879511684,412410210,446019037,337121630,658855385,784637957,536675583,404218240,960104489,897138435,48992282,548012990,560174715,792156454,160189169,705905872,573054279,928960434,598430005,723118328,3133966,709956394,400173006,843883821,846982537,379029168,361068204,661888589,887835679,493479920,976133608,354917572,765784969,49078976,364396665,502948009,205972104,807960031,802286021,744327814,245246294,420470862,538828146,696329703,411129575,588274570,6230560,547505555,473360733,576825268,869928171,485124875,32250130,382711654,49947367,690021132,761491956,113839876,634613886,973389949,360297061,350465803,385111971,501526753,394165342,117902532,47188185,669058037,586179392,803534253,9867730,117081149,270343570,869732012,535560128,74135321,913166862,745264069,367865464,623137053,135895289,799585395,704614475,888437551,472048245,210649737,887519734,367380507,467654308,310951744,120246371,1570185,489874614,177001364,639465634,752300677,618186089,125694494,282846280,736316609,953882934,653497932,841032400,979929908,640731760,744566282,956866912,308789171,978715397,648405630,702106874,252210450,37223998,173800106,569247455,870763443,145425498,15568087,948078131,543632996,464071584,555186162,273468192,844935944,319095366,541561522,462755462,976898547,38432185,745007341,431518992,996017081,641720868,979768983,850953140,572191500,305562385,828023713,101969831,319513329,411569368,498489858,687104004,861506575,386766011,47630047,485950686,906252626,435904945,523398217,237981274,184197706,269135307,723734629,996762583,961708129,184077468,987996423,232884778,412092659,38185479,920544354,863648751,226193943,388570440,67028234,139276129,987378193,100903448,903580344,405505214,867338867,333622878,921218665,511487222,463201346,414182967,124574190,125984615,331268678,712901251,926814813,792501262,571854656,980486453,67546855,150063837,986275190,522883996,773384884,81195741,381162217,512867735,787522767,774407258,380624609,500979859,425339121,963880441,911568272,792258594,350130673,602869571,264295247,559699881,354311181,316717483,974583423,385148768,775793636,276045306,192338240,677282938,975826894,376504882,438875821,650005503,18308145,573861618,505201938,646594656,659950897,130894025,249286645,298317355,654311532,836465450,865286055,895177950,246676014,195480007,816931196,479506395,881134448,708030910,402627578,94318479,239737460,50326524,124781860,692461839,182412976,588599601,905280444,671991486,149716817,47905658,64714287,716724851,557647216,28241812,713896117,846376494,206401418,428739231,942397989,324941900,306688147,258918808,206428157,459115203,714606128,901629112,466484868,310408763,294905148,749311051,394101771,403806550,498739596,248404900,190125924,522025988,356210447,962389205,814535861,3980315,250331408,790031419,402340345,314834487,602818980,373056826,513025448,514106359,330630795,280415656,110664532,260357566,438075255,589257527,858090853,422891205,620257075,790506377,952563016,765975974,960893637,543352842,365161673,624020379,800469365,251809505,622790780,765922253,402911760,997555042,559439272,29544238,878217449,228591540,899811201,871109199,546784719,253989180,599758115,684560325,694533607,280703340,236096123,66961640,589317182,148043719,775804319,268637104,330635805,56702421,125110763,721113904,467948371,559561215,304843404,297100892,617590242,296473496,369817637,718004636,526124218,325406214,131642557,869709758,216629105,687991036,573256824,311737341,758758392,234589476,806451920,213768729,631008009,285161193,822185858,233315562,217016673,677480896,804760339,303459984,221413383,399022533,365958714,40799195,381705662,789465567,637528335,343565435,451970239,746068672,166867880,819274545,76504657,397541090,634573222,532288800,461447953,593079116,206340568,73124197,802335966,905865702,467513529,84938694,290540136,695515463,3667894,705686513,717484972,407798786,866250512,73759857,988625790,225509686,921183249,230949763,381533094,278804584,32480390,574582357,123789423,768169179,487732014,297765428,731832401,432860256,598148966,289492130,97013575,442023507,762069525,931825284,458140597,189544522,921471521,275855481,956391146,193634695,84677511,113885808,830941679,431684736,119795183,940323412,300483044,11521577,885580158,695593645,494983307,139383566,821276667,477452984,683243183,361935517,273621685,4025495,476432519,678629225,920228510,134283532,278793091,224178916,869681152,174441945,438098978,983179206,95895202,212167016,740312752,803874003,175587643,682522859,614355470,789583548,847033912,169737232,530620005,88772531,124677418,888667520,371396196,533931066,718748122,595057220,818722081,914450670,942041351,945793215,348969831,626292931,303397117,228838068,28916732,335304964,558461571,648732065,362862478,645644152,836900145,226072036,2526315,607200856,425579578,179811243,154007534,607302124,644236317,755830590,814364819,673316613,798276161,280639294,493837697,855032350,45181309,777088305,745591284,708716410,549107662,822401712,509694537,125152560,82670992,21672029,486308262,786883337,423502353,712553576,411344741,338677375,263290618,867769039,160383231,747625085,158201606,951443405,636334678,370222790,47943413,484867605,423903456,195175357,135570999,484368556,553009495,600618819,998008532,125481234,313440080,920261882,141597502,241150505,304599832,625027133,525327906,403705483,358303341,111176418,565802335,647347973,84084619,413409784,98657398,549857135,645338751,115503605,27438390,361281133,63172597,827084012,331296037,321019196,410360524,940056259,627749532,909583587,88552551,542413906,383291309,559639076,304848868,722521732,404559230,974891848,856618041,727192121,440882716,357385880,625575814,986372630,598036230,475047518,300390055,9429001,183656168,489248286,603599132,790100302,112821278,47100936,350806696,596073570,738678593,827711871,956260832,515497445,239015995,141398665,978710488,932138573,211644990,69622607,146322047,960086591,50754321,258647929,623274856,429936369,639417107,639838853,463415690,813254090,772158634,68864657,505224573,513238126,837886281,424691906,304708274,744472833,487313664,527962524,959121263,715211506,413909675,908374831,523434901,623521800,445933852,320082836,950943023,805095570,663591178,529212626,576553605,178217863,410938914,233628375,674716904,927857657,624900204,812851139,923751809,613484033,598986239,555815480,298430584,375503657,216250066,107640919,599468144,372254845,146275233,348445243,3736569,473913953,774580513,872930812,971064286,113593433,755600996,59421536,345733677,714514283,393472941,284259833,66346458,60599227,898108187,885301206,338900845,823960070,752754990,871763193,13437676,995457575,827388895,138774794,88257954,210382348,237031440,661262362,540978456,892491154,779545857,322170979,313090904,426594062,917483947,934592310,990532567,577509125,842813129,999017290,549290278,728719753,321942881,929766892,730300036,200992823,699813638,685221289,27876708,677732675,269423082,37263799,680630119,334849060,494381127,899855481,655871084,478790164,337285210,668973815,829719210,154932013,945447776,354565234,188909927,26478796,427248628,100374712,484166982,638445032,389803105,439559792,625484914,637565828,232886118,158083027,9949126,795003657,777100116,322723750,94449894,336166349,767710961,72289165,822399581,822536667,631926299,488957747,563805211,967059926,200175103,438942931,621375447,582250168,95903294,240626066,704361330,5324047,358290542,824270340,594650047,481626519,109910171,836534097,139527562,727522407,282454976,293768652,950465194,743463555,95510746,355298665,151822403,679831206,351265218,588321975,262821348,454551691,611140415,609356076,819432484,658052975,441877002,521076890,701933873,181693643,894728820,188780265,663526654,936240898,276957933,71383932,176921631,636364472,950228477,755325106,270309800,283362253,65964328,945450826,883072592,283017531,163753840,629962122,924289905,269083764,350448019,241173353,503068730,374915411,690044045,476763018,529093196,83953111,807773787,190737225,592880772,128861259,920158793,976439829,149582721,725610800,563408585,795135701,297679143,722991874,120759125,234535659,350691246,185524439,465467495,945535836,407852843,240477927,127597923,405118131,764817821,825937669,99817944,657122324,214895061,444406129,292779824,30228726,855635791,766735167,374009867,947636630,759009572,497279182,812952233,518490715,54973593,273418097,677091602,173154463,863054859,784083709,593826878,95367716,495334794,366868771,792941672,743593740,904401877,814070823,701065352,324710570,64654012,513389133,982548520,11880340,834731320,353228176,72087133,924358982,627408410,610588579,378726663,767884208,205003391,758826430,593451980,495758781,159964914,715021740,300528669,453133479,218060640,69091112,675955729,723034590,374621865,30140947,460969417,786469431,388218887,175188962,505882353,597715,251923588,251882614,353426206,685115098,312159880,946592998,922736517,927074543,615884436,408627210,256719336,870141144,565754624,631816224,222574334,883046824,600474474,91024645,164387222,763626804,852905123,519473868,882853863,150040998,11874414,662434710,771194542,838481126,6826400,881104435,787042180,353504332,531218757,688576547,284766726,140283682,189681965,750797790,429995098,776590864,941914150,410950057,645663694,416021640,539155117,183107105,416501344,702413494,193941495,423036901,525462974,24483854,765084490,189714430,567472865,915980143,997919226,211919296,326446038,32628157,378998438,758546382,288779948,609505738,813183941,408284865,452003623,287525075,401804286,206290442,988161846,801839541,151830173,867397631,175108306,749806210,468794025,866149312,580861558,389737290,90689201,26122572,565363134,687468122,316515229,354771115,337815087,952429677,77238090,119422174,808070498,395928287,612912436,700711841,360089653,576425102,858444172,605766814,168797547,734732670,47718291,948073181,863642130,293978641,489042817,492878447,575332275,522359574,128094954,998575426,899056055,199745229,458014044,231345160,747509530,134332777,816829024,434559916,215320668,570748336,724511740,642894594,817001870,591815773,585728926,805160548,129156321,323741974,587816788,556190290,730033127,940945130,887592268,784127142,140325067,991252458,989815227,938912136,767203151,769211906,202660242,3055075,109812762,289061334,958975266,787469482,830547222,591670516,317997510,555825299,818351833,950932500,96948709,464666134,701717711,261711252,392990098,514778582,788492897,98204685,27871872,306441468,298261796,314990655,901922269,183708264,320315377,772270443,969207679,56213435,754566013,295204016,638042144,512461160,534080859,211216029,312938917,379434759,761712809,612549102,542408218,726420690,77809134,890283180,94223298,834986201,38105880,151359341,566086534,474024469,286206611,744092671,47982563,661790627,938995785,148669249,516050489,443371998,678975241,826165715,412155760,184396253,734233660,351284019,82746783,33911815,560327111,230572941,203338581,690715251,474233370,433708986,639500658,912061533,800463037,81575315,387105819,882343083,447429233,113528188,401916086,48943566,134221255,375153153,760159170,933211559,55535115,590504659,194075282,789301318,277423469,726863779,663247935,873395201,373333894,364551293,31189403,700469039,382353124,106684797,800481782,486224065,249420093,653078726,765153868,672800677,623092799,629288643,189744878,757525515,191241171,461997646,435723807,549129851,566998528,559887888,694540512,941307096,43905753,351086193,543098355,786673852,709316017,418907659,836838235,723477872,745843184,20899820,197443435,203672720,440290960,818296490,907084951,321106522,558770812,929358907,103126773,521597452,711751350,766378770,239547475,530480277,858949148,167341127,252508304,783766411,466089320,981866531,874123083,816384550,136994750,424897754,352365350,36184650,686827494,365942618,81989354,996836147,675761897,426457006,149112749,150461697,91588068,697763290,798065578,484958320,82345405,721191672,997093278,622107166,840026595,484170731,435289435,151924098,106451739,424752730,850991093,528912644,765869832,293486324,178913033,653855718,315141172,123307812,219951280,782068749,730790151,747291805,315550437,281904038,269510985,11604656,355598967,954185655,206947522,247199460,531740343,8487173,600140063,276160085,37421442,948766249,357431290,508882772,337705496,76973222,75016299,470478358,405880706,215490223,827104360,810763285,320607346,775921294,729321380,132812567,687269250,237671297,373232616,391519047,557453515,781430515,901179777,444729517,988673845,934408481,63515249,614046276,708463384,119642099,33832271,460420491,560017622,675566303,451515382,6009417,226052165,995813318,873941637,402946018,271921200,885619520,990968532,7123844,860998915,394017606,385362714,774026156,742870953,125653087,993602638,423050929,684242398,831643948,741000088,104521790,222652741,442215667,265606030,367579220,278578791,584945825,186640895,787539893,30589523,777312420,553437568,273942379,230804298,26737923,552583023,699396817,702381534,15711967,907718519,389379840,919233450,953856752,160243941,296643903,706537775,853346153,588591760,350456458,491133452,377268420,54418475,478077484,895811078,199072461,968190752,170299545,693649095,913310445,581697208,929543224,382439455,206172480,655055966,619165808,963120919,745124580,658802881,58852187,583855207,765802264,120963810,93567785,446043926,691474684,395775310,840639135,716120665,895228641,565400286,571984858,220519460,949770865,845623935,172382728,651641262,357048752,486596823,484113506,572200045,286010307,753527984,377405210,757488568,252229182,331455699,721414118,353099659,816913836,733223872,27461696,345655361,85928885,644299864,959162007,686255083,81381932,583532829,510770716,798372546,950184006,23000546,638597879,429324938,146042226,883204564,630068696,634681872,105233711,418446521,748137520,7839895,153777847,344724659,789768536,280206850,872474830,555866184,228690837,21630532,660105335,83589512,904715465,397062558,712620209,119208550,887025471,163888957,130339175,278018361,863978614,837630855,488681814,822341213,263572553,447882376,443677797,40281901,824963043,411662626,18020790,295380616,596869131,443477524,804459553,412633425,483984550,279892595,168323269,169245581,983854744,365181174,933025175,572832389,347030618,658069208,73400598,311850604,227341851,274491678,193063963,978375367,57449580,406009998,152978526,155295104,784339300,856384838,817737758,178178115,392729556,621136701,357830622,231996214,336924830,822065725,134743211,571038937,429634669,563224768,374970898,213658715,637666108,960502963,338376856,474566094,211684682,420994072,596206068,617221644,406034841,728151289,158230593,619279152,864296956,293353134,819153381,539861947,717329834,943592876,975140988,32687149,145151991,486513262,979284747,221490818,238144030,637945316,46613023,29417549,336161294,993895967,670089056,309459538,194011435,246077155,973939777,654970118,129829720,355999522,270284377,922082631,653672454,51493625,339497447,606351224,54403782,874254924,471915963,746169071,279251945,943730488,873498487,739024601,813821549,19556733,525174823,422769853,53369113,357810377,400647360,418624966,805722847,143662897,585477650,333130409,616623805,109332098,917991563,176310280,105887207,213463600,77766012,557503969,191824434,250281347,651531308,690085543,152675208,774649752,715426904,549413230,978334200,402930282,300496880,902529646,261127194,528906510,603204366,203946908,773390664,550383729,887913052,772806173,748202001,628980687,859780258,289996436,638466493,330158240,218133293,290564887,21814474,324298574,648621695,537494532,228993579,778087511,46312595,695846188,280115110,796484069,982003446,915570265,626360483,119834323,697738357,608622185,469955860,223291520,502143210,378401508,258807905,430014220,26880696,992159718,183587196,146409631,39789667,775645764,241705434,644838289,678415699,874357583,696278544,664210844,151798601,575057261,951650692,204379942,619518954,867015679,660870316,714084026,869837428,314800840,492662365,190068584,70066389,285152014,604847119,434264188,625946074,880381528,92470643,309751816,97334533,88773691,894757720,927928543,40747524,688949433,308829769,985477635,87533654,987726360,271014632,84228972,171170615,702695416,304324358,531084551,936844265,44182037,968698791,677741285,664515586,793313543,778490896,367971936,486293578,914945094,678586375,323199402,632154597,36923516,853316206,775598268,771325563,909369585,262962944,828455040,59423448,938615060,664956807,357440371,157526925,655309285,944383137,824369434,724127142,251052200,856405470,405750689,861692338,637002381,923198636,525833100,609140985,314155325,518869748,804879034,207149937,568393922,123181499,128249421,267124667,844072987,885036966,117283047,205256387,748859852,595406708,888957473,37391886,180089288,785661819,353920982,883091158,439923553,631558185,403806423,680012857,677237399,301582405,967026177,632920337,226992386,566353732,42048805,881338860,805369400,771756319,293490092,596151883,872316049,734316535,474548337,121579771,631742222,639841721,270062697,998555365,625663632,259869949,63730578,582128531,809614444,580520143,978928612,732850005,924093532,684170076,637988054,49038283,911253174,615786221,797039061,944057989,608373458,6145896,55330462,791437282,470209858,445373045,996347791,117993191,968314278,751189688,947444932,583897423,356760685,728987612,292844571,680069710,237328838,549837298,890752718,668699839,86452005,258616628,16469469,640761084,804905022,929002362,898603177,379228002,216130956,101892259,812757604,192791547,567603460,214308982,270761340,377263549,387851387,857882534,483084272,866867639,355006535,916089872,104278907,522643980,506564503,290235790,245650147,270785139,666413758,841921608,752284377,141660263,847852968,528572540,463281584,129436508,548888820,741831695,721375966,141996541,110184974,549986578,252484174,465506794,193101472,133242816,16321542,963512483,644804936,795029002,23922812,40317830,98158449,55654090,585799072,258582502,900638923,95460164,183488623,799339417,733381252,152699901,559259386,988332445,299556113};
        // auto v=find_generating_function(a);
        // for(auto x:v.second) cout<<x.val()<<",";
        // cout<<endl;
        // cout<<a.size()<<" "<<v.second.size()<<endl;
        printf("%d\n", compute_Kthterm(find_generating_function(a), m - 1).val());
    }
	return 0;
}