test/factorial_mod.test.cpp

test/factorial_mod.test.cpp · GitHub で見る

依存ライブラリ

コード

#define PROBLEM "https://judge.yosupo.jp/problem/factorial"
#include "../math/factorial_mod.hpp"
#include "../components/fast_io.hpp"
int main() {
	FastInput in;
	FastOutput out;
	int t = 0; in.read(t);
	while (t--) { std::uint64_t n = 0; in.read(n); out.println(factorial_mod(n).val()); }
}

#line 1 "test/factorial_mod.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/factorial"
#line 1 "math/factorial_mod.hpp"



#line 1 "math/mint.hpp"


#include <cassert>
#include <istream>
#include <ostream>
#include <type_traits>

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC push_options
#pragma GCC optimize("O3")
#endif

namespace mint_detail {
template <class I>
constexpr bool mint_integral = std::is_integral_v<I>
#if defined(__SIZEOF_INT128__)
							   || std::is_same_v<I, __int128> || std::is_same_v<I, unsigned __int128>
#endif
	;
struct [[gnu::warn_unused]] Mint {
	using mint = Mint;
	unsigned v = 0;
	[[nodiscard]] static constexpr unsigned mod() { return 998244353; }
	[[nodiscard, gnu::always_inline]] static unsigned reduce(unsigned long long x) {
		return (x + (unsigned long long)(unsigned(x) * 998244351u) * mod()) >> 32;
	}
	[[gnu::always_inline]] Mint() = default;
	template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
	Mint(I x) {
		long long r = x % (long long)mod();
		if (r < 0) r += mod();
		v = reduce((unsigned long long)r * 932051910);
	}
	[[nodiscard, gnu::always_inline]] static Mint raw(unsigned x) {
		Mint a;
		a.v = reduce((unsigned long long)x * 932051910);
		return a;
	}
	[[nodiscard, gnu::always_inline]] static Mint word(unsigned x) {
		Mint a;
		a.v = x;
		return a;
	}
	[[nodiscard, gnu::always_inline]] unsigned val() const {
		unsigned r = reduce(v);
		return r < mod() ? r : r - mod();
	}
	friend std::istream &operator>>(std::istream &is, Mint &x) {
		long long value;
		if (is >> value) x = Mint(value);
		return is;
	}
	friend std::ostream &operator<<(std::ostream &os, const Mint &x) {
		return os << x.val();
	}
	[[gnu::always_inline]] Mint &operator+=(Mint b) {
		v += b.v;
		if (v >= 2 * mod()) v -= 2 * mod();
		return *this;
	}
	[[gnu::always_inline]] Mint &operator-=(Mint b) {
		v -= b.v;
		if (v >> 31) v += 2 * mod();
		return *this;
	}
	[[gnu::always_inline]] Mint &operator*=(Mint b) {
		v = reduce((unsigned long long)v * b.v);
		return *this;
	}
	Mint &operator/=(Mint b) { return *this *= b.inv(); }
	Mint &operator++() { return *this += Mint(1); }
	Mint &operator--() { return *this -= Mint(1); }
	Mint operator++(int) {
		Mint a = *this;
		++*this;
		return a;
	}
	Mint operator--(int) {
		Mint a = *this;
		--*this;
		return a;
	}
	[[nodiscard, gnu::always_inline]] Mint operator+() const { return *this; }
	[[nodiscard, gnu::always_inline]] Mint operator-() const { return word(v ? 2 * mod() - v : 0); }
	[[nodiscard, gnu::always_inline]] Mint operator+(Mint b) const { return Mint(*this) += b; }
	[[nodiscard, gnu::always_inline]] Mint operator-(Mint b) const { return Mint(*this) -= b; }
	[[nodiscard, gnu::always_inline]] Mint operator*(Mint b) const { return Mint(*this) *= b; }
	[[nodiscard]] Mint operator/(Mint b) const { return Mint(*this) /= b; }
	[[nodiscard, gnu::always_inline]] bool operator==(Mint b) const { return (v < mod() ? v : v - mod()) == (b.v < mod() ? b.v : b.v - mod()); }
	[[nodiscard, gnu::always_inline]] bool operator!=(Mint b) const { return !(*this == b); }
	template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
	[[nodiscard]] friend Mint operator+(I a, Mint b) { return Mint(a) + b; }
	template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
	[[nodiscard]] friend Mint operator-(I a, Mint b) { return Mint(a) - b; }
	template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
	[[nodiscard]] friend Mint operator*(I a, Mint b) { return Mint(a) * b; }
	template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
	[[nodiscard]] friend Mint operator/(I a, Mint b) { return Mint(a) / b; }
	template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
	[[nodiscard]] friend bool operator==(I a, Mint b) { return Mint(a) == b; }
	template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
	[[nodiscard]] friend bool operator!=(I a, Mint b) { return Mint(a) != b; }
	[[nodiscard]] Mint pow(long long n) const {
		assert(n >= 0);
		if (!n) return Mint(1);
		Mint r(1), a = *this;
		for (; n > 1; n >>= 1, a *= a)
			if (n & 1) r *= a;
		return r * a;
	}
	[[nodiscard, gnu::noinline]] Mint inv() const {
		assert(*this != Mint(0));
		Mint a2 = *this * *this, a3 = a2 * *this;
		Mint a7 = a3 * a3 * *this;
		Mint a31 = a7;
		for (int i = 0; i < 2; ++i) a31 *= a31;
		a31 *= a3;
		Mint r = a7;
		for (int i = 0; i < 3; ++i) r *= r;
		r *= a3;
		r *= r;
		for (int j = 0; j < 4; ++j) {
			for (int i = 0; i < 5; ++i) r *= r;
			r *= a31;
		}
		for (int i = 0; i < 3; ++i) r *= r;
		return r * a7;
	}
};
} // namespace mint_detail

using mint = mint_detail::Mint;
using fps_mint = mint;

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC pop_options
#endif


#line 1 "components/factorial_mod_table.hpp"



#include <array>
#include <cstdint>

namespace factorial_mod_detail {
inline constexpr std::array<std::uint32_t, 15233> table{
	1, 243625084, 528205456, 341219264, 546362027, 98950871, 46230887, 423047129,
	495787634, 662918350, 113102141, 931460682, 15003321, 235601319, 949044875, 430087279,
	467742124, 807217731, 581228663, 559108243, 869952368, 210043556, 465245516, 204202130,
	475498580, 437847947, 884796299, 173883376, 245478042, 969113544, 142178528, 678392387,
	703158536, 514654487, 90429227, 459329089, 737436383, 53379807, 374093935, 341107611,
	536059566, 147203101, 79438082, 458592572, 544898166, 369469567, 888069409, 96714152,
	849331177, 510489692, 463510046, 50458010, 687908976, 31298676, 977568321, 447435751,
	65052350, 196788860, 486849080, 322469372, 678464950, 81413827, 24148676, 731958021,
	183632821, 328899398, 870028797, 284783383, 228776347, 586866941, 444054173, 825759367,
	878738547, 584119321, 553232098, 218092167, 862840200, 912299201, 604888160, 959613167,
	786787592, 356877080, 309631702, 216294608, 897129532, 677332637, 321954096, 699956635,
	674997200, 866795075, 237432792, 883474934, 447236833, 228603430, 409173915, 517061818,
	708945888, 513024398, 235032651, 304939224, 113731762, 5092228, 107955797, 26826683,
	227064249, 171586640, 878099190, 324544958, 556024972, 988422886, 815584328, 327532708,
	623860151, 938609554, 360967626, 383750736, 12133366, 584097113, 36570965, 856303910,
	702604736, 741567089, 617414714, 620385655, 716305767, 749872372, 571928403, 920082732,
	442444797, 817772208, 889101396, 132454342, 892570137, 59756692, 768770556, 981597121,
	712447430, 914606128, 152268493, 209981529, 974909403, 893187081, 935013418, 794573411,
	339076928, 662717789, 422911781, 894602879, 133860181, 478503705, 119644390, 456097555,
	27748068, 123302292, 300452614, 650809734, 803922622, 956709393, 387416674, 908644573,
	916211838, 585902324, 100440371, 164214258, 105949390, 600915046, 38642456, 453226822,
	180607711, 818695902, 579424583, 124024159, 579637742, 898654224, 289686434, 257562664,
	827641482, 635330107, 195408727, 379535380, 236966102, 286681291, 197744845, 975923660,
	949681114, 276997357, 121293362, 799378329, 568149818, 936648941, 328494035, 239286924,
	982515753, 334875692, 170627891, 925332578, 900916002, 259568889, 391510611, 853926547,
	615501037, 225154155, 971105993, 398536162, 678666073, 98461774, 537572117, 52101934,
	303461550, 880773661, 104951530, 316906313, 337455140, 911674995, 738168035, 316739249,
	752208133, 200561749, 256740311, 737802457, 788118526, 137140289, 83986713, 495063243,
	466748179, 912606777, 937541971, 483085948, 243676582, 709823484, 421489303, 50799066,
	149019363, 841802949, 804860229, 717974930, 462646504, 437066208, 788243310, 571351766,
	669060208, 188423848, 844934388, 303091738, 932671254, 4953312, 258606865, 602861043,
	410784037, 25761779, 896636701, 405657057, 168583446, 796348638, 225022942, 332863536,
	789885751, 314513587, 953457844, 671461479, 435910155, 918701898, 267200293, 721609017,
	179310406, 769128766, 255608793, 188808733, 972880908, 943254645, 878738951, 679682039,
	915736046, 51089375, 398992183, 184942203, 878307651, 748261234, 646723039, 9686825,
	204365183, 160609105, 726479740, 832878947, 790783914, 280877154, 964619116, 186233757,
	189957301, 402416320, 730575060, 906735307, 392294341, 547334218, 597972608, 83314700,
	682039060, 759923825, 116520143, 714499660, 74260872, 233334287, 916164443, 565126725,
	934038903, 785858611, 525248952, 359543753, 751078622, 455854634, 269616777, 889774385,
	809578487, 834793580, 387403229, 641245525, 451398891, 715094312, 38425540, 78766454,
	728735046, 131433091, 462454195, 922995104, 626421075, 373328360, 591976106, 341772476,
	932484694, 302102405, 488389634, 201240369, 161172202, 989316045, 690806277, 592951571,
	774755699, 829136608, 448185818, 697189586, 438926241, 125404314, 54364373, 30258631,
	251635112, 247431130, 175852919, 402003295, 599059573, 829576695, 533046726, 107948055,
	649374308, 931219846, 421531371, 205575280, 592663015, 420234449, 905112488, 185819496,
	44781332, 866238894, 682801838, 368622285, 496474926, 431661802, 710946675, 433048457,
	602288735, 967369165, 422695404, 65557051, 464453871, 456202043, 499544286, 147450402,
	419565259, 770711368, 688830050, 739306112, 348756405, 130548126, 973854845, 181577184,
	492352484, 25645867, 838937129, 660854323, 913432121, 325771521, 118371992, 344066607,
	485598879, 158066545, 921749747, 729816245, 902650117, 912110389, 943839037, 837746121,
	958678776, 805940482, 501439008, 572850911, 538523645, 307521870, 1031426, 377696095,
	212939377, 715203760, 781658061, 660267437, 29226485, 241629517, 478997130, 911020972,
	943233257, 5427071, 814949348, 575291217, 696830426, 993855426, 791864427, 774187651,
	92861143, 366051815, 911750594, 339961653, 310200674, 849042834, 629247257, 270579781,
	148504501, 119228630, 933491620, 908895050, 528881369, 180609992, 144047477, 8259044,
	647938718, 624634810, 188639901, 370992540, 897030508, 86528221, 185924435, 383307542,
	352124178, 498358669, 375025726, 192879782, 187934073, 772051613, 103297796, 947658324,
	231289271, 77425481, 715675089, 94574029, 316493098, 113829594, 281631088, 256317644,
	569334038, 128056798, 64015523, 88566954, 311107247, 492287123, 773559161, 398819078,
	739662367, 677256131, 919504367, 551509219, 174071185, 80002865, 973523831, 30580777,
	927469492, 159124713, 537463147, 695460234, 504942808, 612639631, 136343616, 780938585,
	617183434, 275840005, 149515814, 94374713, 919427085, 490420977, 639503906, 170933549,
	343841688, 458357407, 329570587, 598731282, 744176129, 826787025, 738987813, 367612279,
	581235, 465513378, 426538819, 220629293, 522793090, 425438933, 461739775, 764128125,
	432351202, 240529637, 327253888, 567916923, 31984945, 986705822, 499492777, 223736792,
	905453998, 40636533, 374806244, 213093417, 807779660, 986276943, 604430505, 524161562,
	700916755, 779644074, 248340106, 932376508, 872639853, 651840203, 66773522, 912246715,
	401991695, 21573541, 893261033, 180273808, 308167280, 770744747, 221255024, 630691240,
	170721982, 12289136, 908400416, 547618285, 208742774, 646981343, 263570034, 741124287,
	990967985, 824675299, 227169982, 699781190, 567600326, 442849579, 786635920, 356953960,
	8283809, 917894686, 664998448, 906326119, 844495026, 220225442, 294061526, 77631508,
	499996296, 149626341, 523490012, 829396275, 812704163, 269521962, 522844678, 401217721,
	875807278, 543636640, 910802698, 17105360, 327164642, 498115968, 803799881, 60791747,
	229698610, 524600619, 773068829, 250750237, 374762899, 159883335, 417614554, 641521439,
	931632987, 958823780, 9770730, 744960501, 280212809, 221142180, 695364179, 497038747,
	371066241, 822655767, 764906947, 222841355, 488908235, 507009553, 325641250, 296212285,
	330722936, 501001765, 93111721, 132352588, 915670388, 176207352, 635905431, 811935377,
	280178923, 660932508, 574635970, 110251535, 884417125, 616395716, 473915181, 260819185,
	603566523, 374809294, 197973832, 143724009, 616601558, 324417348, 993667551, 78447328,
	288278983, 172516485, 155393141, 813773997, 542143258, 705859374, 903160750, 367340006,
	391470976, 914545761, 213800075, 833823305, 287242280, 633243762, 417014900, 88187536,
	937228106, 917578195, 612152172, 629836938, 789831356, 812781597, 215240443, 933020372,
	157944106, 937868131, 408933819, 130947713, 100567078, 216680184, 729655597, 838558281,
	32135002, 472179700, 79149960, 750566710, 850669873, 270592075, 745022074, 301785843,
	826756015, 805053534, 410270659, 335589537, 864903918, 953370634, 607981166, 311703564,
	281967469, 112857526, 148294237, 91844270, 133982682, 258170607, 778425494, 893993611,
	278928878, 246080279, 258591652, 602171126, 10198774, 272925881, 782457089, 703100039,
	348516222, 434619720, 297454918, 352378698, 127969094, 128748026, 855175085, 624894972,
	178606531, 867812998, 115237123, 963590936, 625435385, 924457243, 140224351, 164945856,
	538703379, 228886303, 685222222, 856102526, 592826392, 401559011, 603355747, 389330037,
	522053153, 606939096, 373182333, 404580314, 498519475, 308215739, 928051510, 362894770,
	285838022, 754829199, 78177152, 397948151, 972830355, 685913880, 244800867, 486166243,
	175494307, 747983820, 667146036, 912772790, 3618971, 232020145, 771092127, 673984233,
	192143077, 374968828, 373322910, 624502845, 728050402, 590025563, 565315878, 138488617,
	16217485, 918163315, 769502652, 187232186, 718076687, 907022376, 351390835, 769420506,
	57939490, 635922778, 471016631, 776000855, 317439530, 370600746, 939367192, 95558764,
	310769109, 360723261, 609340556, 305406286, 558589348, 495251743, 786853662, 557461945,
	396086022, 258364604, 308849774, 121244150, 663504801, 74532052, 769641179, 546507613,
	430912024, 620368186, 322204117, 427701524, 898622193, 765731220, 454166300, 143786252,
	734307230, 449131386, 700921199, 698282831, 292803940, 127716475, 778368174, 494725500,
	970167731, 349752894, 806247425, 440401786, 228546241, 786321502, 62635577, 315047625,
	950863667, 421129101, 684672309, 238269118, 66879051, 184533589, 461592645, 159795599,
	302127847, 792609335, 399379489, 769071869, 813831077, 992220833, 80285636, 359076776,
	115876888, 346321135, 200719315, 564479320, 74061490, 525368674, 326998958, 460723847,
	960178710, 123429415, 383091985, 167426232, 611022973, 501130809, 457447372, 612755082,
	341761124, 112701220, 816974304, 340295928, 290816856, 760694907, 396826553, 772487100,
	607169580, 797785138, 957094500, 354151844, 731243794, 254577438, 797361390, 92661684,
	467661809, 60559689, 904552563, 472304980, 621874008, 790878259, 39983621, 153055093,
	211863227, 481620103, 48476308, 258899122, 116126476, 712647452, 135945273, 567691200,
	189655177, 818733845, 102421390, 391771547, 945606106, 529311718, 288913256, 411558978,
	918097328, 409096872, 907671001, 542106171, 731143132, 832116892, 287210596, 190287897,
	100428331, 558728324, 991466883, 768600363, 465678684, 601941523, 375423015, 807287652,
	664502958, 542072754, 945888278, 480363896, 689623004, 241195463, 913568943, 514251914,
	653951044, 744807137, 706690037, 122488057, 864730741, 412570335, 597476188, 967008629,
	598427325, 589613197, 412070212, 744011810, 274881082, 70126874, 195912800, 102313981,
	927114521, 401584033, 819119182, 309787702, 907969397, 181141310, 472223894, 8125816,
	415194799, 701702633, 712067596, 520094575, 723871843, 669435606, 636445182, 46159636,
	854930026, 647687968, 844628452, 937328909, 376562134, 690536073, 701059355, 874383700,
	38321157, 998232077, 759436250, 227826156, 133770966, 785251056, 810340458, 646944118,
	25316168, 4685131, 156899266, 292051040, 920558635, 590877695, 417837994, 371695603,
	375608821, 357303560, 240399410, 940796579, 987319416, 429269822, 322806135, 450583268,
	580961247, 330160622, 877177782, 403406913, 422127998, 477887017, 463698215, 745843115,
	557298612, 607938035, 40289307, 436118489, 198204448, 841282318, 278788861, 673991099,
	130638887, 28605478, 140965511, 657743140, 748850920, 741885157, 984130125, 584056024,
	497769749, 593952245, 354725151, 699539717, 67129116, 225058624, 292745739, 513836153,
	659203899, 465732937, 841104429, 610061703, 799589378, 657749316, 448800221, 784774703,
	114695383, 811910078, 151523511, 942701712, 735150771, 618760717, 83536983, 149537082,
	111073434, 424515142, 156264966, 855795279, 532497986, 39969997, 111344593, 662186664,
	77784134, 208957375, 846350750, 140110097, 690311611, 247679444, 756489413, 875498764,
	206658287, 58091263, 841342977, 646683022, 903874679, 651225967, 484854016, 478507334,
	629192790, 197294826, 552841429, 152884933, 981942654, 1376976, 849662380, 491029652,
	877316308, 269376984, 348232296, 233227811, 413944840, 631119264, 159632223, 281256786,
	339438380, 583770703, 262327689, 626753302, 109313458, 544093164, 74478182, 743561861,
	875687162, 373088204, 554083298, 618138980, 201298529, 393694716, 651305385, 406466542,
	348348875, 374021484, 333216299, 892571102, 983353135, 630696551, 912479726, 894749903,
	319948514, 346359280, 616409510, 665310129, 465656361, 134665771, 147074008, 813316949,
	713806860, 837936802, 761983524, 42010748, 598649218, 4656424, 944632682, 510514461,
	423507708, 962031312, 471000939, 888241925, 293544188, 872849075, 162036706, 311858634,
	526342541, 840294835, 682352384, 767114771, 499273586, 704843657, 875724477, 953495234,
	712335026, 462530682, 390466978, 424912422, 226476125, 981884849, 321643711, 154896363,
	671850855, 560313463, 569197468, 795695441, 970261184, 956816271, 52891009, 488427315,
	10981391, 122540173, 522012918, 412626242, 615409544, 614603932, 646050697, 557296155,
	414726935, 502445554, 58112309, 732017162, 851781371, 813847129, 451242194, 409459343,
	985476928, 915201531, 107807479, 21481660, 63863246, 879017923, 658570354, 751665552,
	844082152, 951299486, 445987946, 347160901, 111491453, 637820721, 821976130, 731954180,
	263771493, 674016113, 60225655, 780033295, 167558403, 328153618, 470856493, 930231266,
	412454739, 242229143, 722301478, 470305782, 647963886, 117787333, 408489450, 927673549,
	620560379, 933923539, 507906119, 390722107, 586813612, 176146066, 573380061, 502711246,
	351143550, 42868800, 378533647, 336866344, 345023079, 962918887, 334853826, 261082865,
	644684827, 706232852, 466830131, 477091916, 113776988, 681483696, 491973264, 319456102,
	868784407, 687459337, 289770035, 752104385, 513382766, 211151974, 62752825, 686572879,
	979197552, 781074043, 144439991, 144317696, 550937198, 593473990, 347634028, 362012993,
	834684152, 721549545, 662023087, 563155503, 873944671, 753332401, 703011083, 296103010,
	95861639, 763817282, 57843667, 2689052, 784641293, 396024103, 872613775, 105627011,
	186057224, 420736970, 765080471, 196579481, 302298355, 992356646, 990333434, 387130351,
	777962800, 872806553, 772666833, 336967329, 269671755, 310116415, 19461146, 752335251,
	996072584, 30787409, 650783654, 227402012, 919607302, 932669122, 366768998, 894710491,
	12334393, 74584246, 61487702, 42118080, 677347200, 274387569, 312877557, 821478935,
	619190001, 737021004, 392012555, 742271793, 684637028, 787776578, 413637309, 551628605,
	423811725, 884531483, 330691156, 767634132, 751934004, 744638046, 78708368, 738488154,
	24770542, 580952713, 955862660, 909798910, 199533336, 298942608, 447439123, 89850948,
	594327956, 295100110, 947404471, 233005199, 44906977, 22866857, 361183350, 490078329,
	765280770, 122553328, 220788169, 991416194, 828291353, 869823644, 954231390, 215460273,
	944982486, 93280976, 63855419, 729472732, 895544026, 545343632, 989723490, 574553694,
	513490122, 189532846, 941591732, 481242880, 428477713, 996636526, 848695287, 935971401,
	172090142, 628658401, 615094076, 609217675, 639144619, 262400261, 283605747, 109521751,
	468949120, 818351100, 810669674, 631506071, 179419457, 113102288, 134063209, 457269145,
	693347403, 543992507, 323902000, 612334691, 547801615, 750894450, 391326143, 137088039,
	867194196, 21195719, 372020387, 285493283, 784837983, 86605283, 633045533, 726791870,
	356450444, 725704688, 960599741, 785102334, 434557850, 642778019, 433873053, 453220224,
	866447292, 844108998, 727961047, 936840302, 263362024, 951939789, 192958528, 827765501,
	508907207, 525363123, 273461437, 317432082, 961193153, 400611340, 657134492, 854298011,
	937135640, 274836720, 43616849, 189876175, 164164827, 360834533, 152954629, 346105635,
	878687853, 748556828, 689185626, 977685607, 901078593, 115819709, 295827426, 401892975,
	560788103, 775925767, 668483855, 851516244, 668619863, 621381279, 404047612, 279938769,
	925917344, 918602017, 128333013, 952226390, 223870418, 423936043, 679857689, 649307308,
	308335177, 215257587, 594127458, 103209555, 242200119, 435451016, 451660213, 274030196,
	986446088, 46053316, 880807451, 14563195, 54433427, 2035286, 447505218, 172300503,
	703539315, 492387932, 471610601, 907562932, 390468437, 732717118, 335172233, 648366926,
	866452791, 233521657, 624361408, 903599497, 757076271, 12305407, 671457929, 96739843,
	252044620, 824889181, 56760375, 844623287, 366104389, 164308700, 435844134, 815124008,
	75980605, 142710785, 664785447, 466529428, 752345258, 643616824, 912733630, 294990295,
	119916775, 96058567, 605844958, 87464857, 820053377, 827437913, 396780145, 423924110,
	803505139, 888331506, 466430835, 763848709, 527720889, 43741551, 891363200, 55565494,
	298069903, 316108408, 791582917, 891831356, 967616733, 698888683, 206764036, 216249034,
	728755858, 125517905, 769526723, 460937300, 122547520, 524442924, 24985407, 12108056,
	43651994, 47808670, 69726091, 720709072, 256593734, 414556554, 530631342, 155898162,
	724198866, 1122809, 136153085, 168706520, 694358136, 107139905, 674569166, 540697916,
	148641017, 65411287, 602034881, 993437701, 213171341, 170048025, 205402091, 792050964,
	918530965, 632402284, 522341598, 304540876, 103374949, 437480168, 958515831, 930622824,
	730387621, 221884653, 88364437, 43006478, 145057366, 608441194, 285450288, 308284260,
	644062734, 803555899, 846306503, 793397384, 494014590, 79086432, 596218169, 222488570,
	856452172, 95530323, 439212499, 300385170, 714148874, 792240040, 419470854, 72619546,
	935137964, 785709816, 281875154, 303811363, 918624300, 230027427, 572734194, 788541012,
	74265901, 400088242, 750716817, 277528734, 398990170, 296486934, 284985662, 8347630,
	894440763, 348689205, 850382041, 224412060, 964348614, 142104729, 813399043, 334754284,
	626807500, 662141896, 965463752, 514549671, 422594135, 452915927, 449723860, 409792939,
	592214416, 455078978, 995814890, 324204444, 585080818, 719088061, 199956015, 24580986,
	980602375, 313559934, 547087371, 193019501, 916143652, 588153696, 677618133, 553139247,
	690125029, 769244568, 753003200, 437246316, 276366160, 877331202, 118845165, 107860939,
	42825068, 519457906, 782585827, 174501633, 494475777, 307391132, 708278006, 317440181,
	197782741, 721274866, 652751129, 738210999, 507452151, 852068769, 248111564, 826894105,
	348086475, 991275692, 961714575, 519475019, 897436095, 734188090, 12248008, 329859790,
	275705798, 316895705, 484541128, 53258441, 474985350, 98927735, 866960399, 821050123,
	162321900, 127717501, 847639834, 529531197, 340706211, 43990829, 791033374, 502881315,
	140481055, 873194662, 416084461, 536664545, 760287323, 340428304, 746737908, 657414293,
	207340584, 458545574, 655806870, 182061984, 585373260, 830037484, 653333688, 31012909,
	422242372, 314982727, 847617791, 979682572, 467592055, 16904857, 503821275, 657847893,
	151258454, 914660539, 973713240, 471626586, 849695887, 182122899, 338684741, 254272130,
	280214507, 783171752, 934032810, 499523504, 815133566, 186540008, 436123853, 889983095,
	461547160, 866314690, 897396694, 906647532, 602521887, 965029341, 199927630, 152919687,
	606821780, 382613508, 874175873, 524299604, 380711249, 889646290, 347994081, 264536043,
	320321845, 63525776, 865962652, 391645976, 780539736, 405227650, 942321748, 750249897,
	595481991, 182103486, 4585558, 992641918, 249755872, 196777177, 871700445, 171840810,
	361026143, 265788013, 259055678, 862218839, 352261217, 794675548, 562822752, 927510982,
	420021980, 927286342, 143339187, 521490710, 729228078, 161305321, 197775909, 56132796,
	882876292, 637114477, 641625179, 703072101, 719558940, 539605925, 942966673, 453119437,
	662416910, 84301772, 978795002, 202612419, 341986844, 130512429, 360092999, 822023467,
	842563318, 553219037, 580346389, 87066123, 437621061, 554846075, 757703063, 366867030,
	654973429, 272992372, 247487480, 164933970, 761227004, 455289781, 774715137, 697518955,
	257705870, 739773775, 288083235, 361625442, 876636105, 648741020, 411691019, 310618740,
	889098725, 915710494, 676045379, 5258957, 7995738, 123621478, 335288222, 432339983,
	158156446, 521771209, 343806594, 330934015, 469902602, 996530838, 983214031, 795219732,
	439588381, 524524956, 610613405, 991636587, 156056749, 995398201, 282359036, 855553756,
	292795459, 411292078, 789325672, 536005759, 49424092, 375655097, 838253519, 787285992,
	750096383, 726199709, 922228441, 933604842, 302897934, 382551805, 290903315, 176529167,
	984763947, 702377101, 977656688, 424659867, 99476475, 137310651, 374782789, 740193967,
	404286793, 364541530, 356052272, 562757253, 523094438, 266844503, 664552607, 502996118,
	917068833, 583690777, 830680426, 231190225, 961541194, 895442165, 671287667, 324025278,
	959108892, 683262082, 357086222, 492462167, 921300784, 743063019, 472476520, 338934433,
	811332379, 377347533, 734876313, 424338076, 484789357, 363159891, 672447986, 722165259,
	988299928, 523260970, 412750782, 577436976, 645242297, 861374204, 44046510, 367674233,
	782439665, 86388565, 196662458, 31801680, 513323035, 71854340, 988042979, 828994414,
	677376428, 473967692, 550058474, 154517511, 602232504, 685523234, 235213736, 975881188,
	944504775, 174052897, 17321115, 963002352, 532639223, 341962577, 285943877, 745618347,
	653510680, 716050154, 549904639, 214091265, 544430857, 562700918, 450809250, 250271815,
	298167161, 775370737, 784404996, 269783404, 490992985, 149985542, 784034639, 479633849,
	152682741, 290416315, 195143877, 231862605, 115596063, 212102913, 850724820, 248595352,
	141501910, 270182678, 623138523, 134142483, 254151107, 587822700, 496421380, 896641582,
	394279790, 60024790, 222893548, 523652337, 469294979, 108076330, 490579552, 523048053,
	155584237, 730034432, 397695425, 781279094, 662906004, 489192054, 827791429, 389268713,
	406973696, 817106905, 647884322, 649822775, 751715821, 496840369, 206804430, 631847028,
	149720256, 518100993, 919332335, 915609301, 931375399, 732048468, 469285422, 834100685,
	182402931, 358201814, 727054170, 755004237, 396158620, 879552737, 308774032, 336899158,
	71954352, 963445869, 628550715, 160730351, 796737079, 199340712, 166711703, 375638763,
	204046908, 965780049, 310096145, 655738813, 664898691, 450713902, 109979850, 274505988,
	666430555, 683598840, 416494353, 604506015, 691411824, 816164628, 824465093, 350670223,
	397926875, 390334111, 507325187, 343917949, 219896740, 888993329, 974990490, 267370965,
	580966229, 323328138, 188042742, 369194521, 908472174, 65636217, 382211715, 362540109,
	454849911, 606529420, 75012938, 806805855, 734445407, 846503246, 80083668, 536140831,
	884747116, 551788123, 677501683, 406061710, 665996481, 824267354, 321750121, 50863780,
	902159079, 830484571, 945764732, 203563603, 323009782, 403669486, 229900601, 83752910,
	616367471, 375885628, 761540473, 770685004, 579262532, 104864476, 51473216, 94042061,
	505113763, 774581882, 151746659, 289723795, 465217539, 248174018, 75865290, 360236227,
	918981127, 284650227, 422592485, 833170547, 519752410, 112280479, 921606343, 698795486,
	721528800, 754736581, 844825006, 703144601, 779994151, 361509989, 318605410, 363031368,
	310328833, 415049650, 151564471, 648579824, 950942580, 205617419, 933220892, 792606106,
	787141545, 566258468, 401425294, 800143085, 216453029, 889239173, 860717597, 371595840,
	724405658, 881944284, 625655221, 563686022, 158155717, 449653401, 469773074, 644918943,
	125217894, 93150026, 108676300, 11326751, 783347600, 69549409, 382820763, 539059213,
	383796145, 590905278, 434192913, 863493594, 376311210, 952551889, 272949862, 773850523,
	628326749, 510166426, 103114700, 862415663, 799737181, 168117955, 302673848, 815112180,
	256700166, 196380075, 966847235, 856988969, 374289278, 973101231, 778122561, 72977454,
	580209494, 297086557, 314028756, 873660129, 356915292, 823173079, 555992493, 542984572,
	487819118, 618081792, 200250724, 812416890, 513930944, 617957209, 44022732, 936822831,
	515394963, 750421967, 86584155, 322766027, 752918690, 839601544, 627813679, 947232995,
	642491144, 552356158, 79556805, 520478730, 420412247, 352455129, 223966173, 613427542,
	475537940, 702355652, 550317017, 5881824, 143054753, 297368298, 580514536, 292595087,
	181867555, 748261269, 319921534, 844390395, 35627502, 641170496, 653513293, 262375979,
	887474143, 621837546, 677362959, 820755766, 506509709, 161724897, 216466548, 526774195,
	524937737, 574017384, 571184327, 408558725, 71699113, 415721490, 6983657, 7512601,
	682500199, 42500133, 634292120, 842173106, 996938052, 445095120, 780763253, 978580344,
	222137750, 135824334, 855605959, 721961224, 318918058, 77999095, 175166337, 326164320,
	889385471, 562884556, 195979659, 928888810, 957319539, 194178116, 398605805, 25838744,
	445244561, 985972880, 808921752, 649042459, 995880581, 72890914, 765172997, 935416578,
	975593590, 238030945, 487694467, 525459986, 669913624, 501323996, 791306678, 313715662,
	79921588, 366211499, 375268352, 506874138, 552352985, 815189510, 364666962, 422467639,
	760822334, 151299111, 906229867, 692638113, 297603182, 81694614, 340270980, 878548838,
	253457448, 127113531, 894789605, 795934227, 520288359, 688069606, 72904240, 711214390,
	843192324, 838725932, 724677192, 795155327, 266075682, 411230915, 932746735, 907268272,
	405659726, 237509276, 867109374, 180787703, 952970308, 577854619, 920682517, 905084695,
	218762563, 233436947, 701448010, 709591695, 965129117, 402712082, 704781499, 722416515,
	260707689, 202652233, 331124375, 46052752, 92414023, 559973271, 954195191, 150344816,
	915348399, 680554625, 177046700, 862181177, 478128490, 547107561, 8546092, 616978221,
	740044210, 845926218, 599501850, 36824285, 69481921, 804311750, 49553318, 364693909,
	882001331, 985996187, 17444404, 82982240, 903489808, 399490186, 200502889, 488408960,
	654653354, 697045077, 199504845, 456182342, 728157390, 180605322, 599965352, 153006799,
	868883709, 56807388, 969248708, 788099983, 20397752, 257577987, 711112054, 948196111,
	229885020, 851737469, 885688226, 369765673, 193639307, 91334425, 884644357, 885740893,
	472133266, 223067216, 146559541, 61590457, 347123457, 578101441, 103239267, 602824102,
	230551611, 14945847, 781395016, 764242107, 755393457, 508779604, 499796265, 159269248,
	231363697, 924835184, 791345825, 708162783, 993753877, 87587003, 703189091, 174067978,
	616689587, 553252994, 105856207, 45209813, 537089921, 387656412, 587962387, 678999334,
	706419123, 110604114, 337241625, 487271909, 662238182, 677312037, 241275720, 310800251,
	939003921, 263923728, 104954514, 862114109, 608394270, 769809743, 185578305, 51611429,
	818360267, 693252421, 764082776, 196900007, 245923379, 389520847, 526059799, 745388745,
	565960348, 224654083, 32441462, 215540996, 121057693, 766951578, 271606518, 691405042,
	744332005, 427531040, 110565084, 455055616, 108338295, 213384947, 908722157, 700487706,
	904184966, 279335310, 220861318, 623329258, 165588728, 553767674, 391979640, 316998368,
	26752122, 283455035, 956177539, 995116351, 878234973, 106009869, 843535620, 238498203,
	133298693, 254438961, 664714384, 253508449, 95400877, 743284259, 17622774, 307397217,
	724821332, 188676266, 223526996, 279609399, 674567907, 289433410, 80680517, 232374007,
	859220865, 736292171, 263152576, 595753429, 320057189, 818201553, 482200330, 179628249,
	19628724, 557625580, 41464354, 662945318, 181103024, 586222358, 393651124, 740977090,
	186139683, 834765422, 902419094, 198162696, 228687961, 412766172, 656438541, 611075003,
	556565743, 101694610, 935614278, 420518041, 39444001, 592560053, 697799963, 783490444,
	765071679, 681665141, 662508839, 222983206, 614762721, 817515215, 521475976, 41282097,
	750064038, 913463658, 18100394, 315353660, 874772975, 24000931, 159921436, 702583764,
	247651638, 104170730, 222048594, 239373631, 21445650, 95197474, 406055701, 406480318,
	790534089, 814157670, 884065796, 129570184, 889647991, 65945743, 523991826, 609707250,
	451157944, 310904590, 470179380, 12400145, 989182660, 622145605, 6162630, 96245068,
	153639960, 500962928, 386348328, 322611065, 244982313, 910992750, 875926210, 903759558,
	929341123, 707055290, 799123794, 699422451, 447290246, 466854667, 429819949, 559717769,
	150962568, 349002198, 843391119, 173985956, 628969877, 791781069, 400058446, 871435519,
	503724944, 497814990, 49989880, 365273912, 8288542, 732294656, 981663698, 515119249,
	369767167, 433463053, 901814230, 30224207, 838598932, 787424376, 968269465, 118702191,
	768266737, 306599492, 205425898, 270575768, 870016126, 963314707, 301752668, 97705251,
	142738628, 658123912, 285312398, 369085, 947216470, 408983847, 753752975, 33719953,
	142218056, 52324077, 385912017, 271327304, 724357217, 388821346, 832836958, 405168908,
	756102438, 313156605, 24289243, 43832598, 438723484, 677753008, 585838946, 747544451,
	910573117, 398188148, 585811046, 942215845, 541345490, 419749696, 931219824, 661586780,
	220480441, 686415270, 630771555, 524346828, 783431100, 207081660, 219244061, 332147301,
	274579400, 492214342, 433594109, 222111800, 120104347, 488872464, 237292056, 633684142,
	761450460, 48487205, 98282548, 733240079, 782628749, 949166315, 355180885, 957045145,
	151387843, 4271840, 162141758, 208410296, 277354695, 904802490, 710091839, 401467565,
	428852289, 95353395, 754035515, 806131342, 471045235, 983690616, 730865475, 277749039,
	212671109, 407776258, 743364390, 907169276, 712678391, 220778702, 829668873, 213049760,
	111765377, 748170392, 897118914, 938349924, 57104048, 501675446, 34870999, 196318458,
	815271666, 9354482, 648873818, 733650713, 435783657, 808541585, 199587864, 724239642,
	978868405, 347332010, 986999738, 907486429, 699677206, 748957484, 39952650, 103690210,
	406331931, 744698256, 85972765, 992263248, 476691454, 805106271, 530803543, 467838314,
	960787671, 256728455, 673426847, 542590978, 385906193, 813204974, 336852383, 422408035,
	154251304, 493644799, 865442253, 280683426, 287126599, 269785738, 963584581, 850110627,
	195537577, 871261936, 131579629, 610029331, 943974362, 934009038, 716234507, 45834567,
	642676789, 93164350, 525795437, 758976355, 659394715, 56330481, 840569805, 441224202,
	551420263, 190903982, 887476013, 428504513, 447452006, 136508594, 188843273, 872217830,
	570372925, 82945487, 828793926, 992742444, 823133127, 925395430, 393053079, 973112472,
	346093736, 607357628, 629595178, 941900795, 554051534, 493937901, 129252738, 347031858,
	976277122, 874589675, 350406387, 94744906, 248771545, 604368604, 337748282, 393232398,
	322990467, 381965317, 86488176, 823454939, 42045044, 803931241, 591570789, 470192920,
	442985463, 340890553, 791547233, 579118712, 549745792, 449049656, 686357319, 454814540,
	310948307, 646705830, 250543158, 510191037, 727259945, 973131441, 592045939, 731492671,
	928799971, 900506146, 120183266, 656045965, 814347511, 608744368, 684897615, 288541808,
	72645524, 941297980, 738692382, 436570802, 106540205, 969405997, 587762498, 517406186,
	817581666, 764617875, 215938669, 79601728, 181405446, 429914728, 409977573, 874876236,
	834561554, 516093111, 764079765, 724024692, 481031267, 391049135, 486188971, 159047586,
	797627351, 139937454, 901990817, 512284731, 147458830, 267053847, 936316104, 454440240,
	790123833, 302030110, 931492289, 844385949, 572407261, 151828166, 376991864, 891060164,
	100113334, 239972547, 209291842, 837410026, 969874128, 52717041, 59045084, 557950667,
	152035181, 103991348, 270038209, 650851602, 717889542, 221632176, 487974398, 172752464,
	877639265, 246076905, 207337081, 951955905, 92032605, 370242901, 728323849, 671511911,
	91480443, 241712203, 27609077, 523077431, 237105194, 209685094, 524141871, 961350398,
	541537097, 845701805, 609874843, 527196078, 689102463, 257107553, 573197392, 62257486,
	652999397, 705209072, 156567932, 564578619, 772740964, 893614747, 871139633, 305914518,
	434482347, 819095939, 197988193, 99825323, 589466929, 307601842, 288303034, 349166630,
	165115489, 161422537, 495946876, 468171468, 905461932, 380742507, 325557870, 857419274,
	300960222, 665642480, 51252806, 578986040, 475133031, 807984411, 712062892, 923570991,
	996552400, 164340113, 622677683, 223615529, 578533417, 186367797, 95540665, 539329531,
	270085755, 814897424, 337063650, 300467478, 441829214, 968934407, 921153667, 444247721,
	822264510, 718684639, 97254994, 281165407, 944634612, 829296132, 53994033, 539963181,
	481153328, 102808911, 307934215, 248578536, 142168318, 15923039, 124343692, 724286954,
	921511222, 414048651, 708247890, 343046893, 792263746, 772202753, 26706344, 476695726,
	236088097, 873588258, 636684488, 435456512, 3108862, 131041410, 305736043, 145320432,
	38239697, 470412968, 271142352, 595087374, 172687800, 45544787, 612985540, 751347399,
	686884498, 44600191, 191972830, 457312440, 509617205, 132661293, 403334731, 819614250,
	498392735, 977404288, 111393415, 320600742, 854543114, 781316135, 566015481, 924897451,
	323505794, 772014909, 181691371, 760218466, 331338844, 600668065, 241362210, 556942462,
	740063275, 263132830, 89679648, 55811282, 509556418, 534509302, 119864981, 205360587,
	897572220, 667631357, 915300055, 296526195, 947043567, 727515835, 550843726, 819883657,
	454561842, 987247222, 204321092, 980303918, 37083800, 14673681, 416514799, 420688313,
	900787550, 329284223, 217919576, 792885950, 861410045, 527182209, 522901437, 49161983,
	615916241, 232233550, 346904271, 484879117, 411023859, 918834202, 281157473, 172915228,
	277507290, 297620567, 22402260, 515405710, 61672981, 530779388, 507860604, 844814193,
	11300795, 631522002, 354999179, 542065142, 450394265, 940925560, 151877512, 944080301,
	157634146, 788358701, 594340785, 473466671, 249546977, 271927485, 500448228, 166951093,
	693942892, 888832436, 803893179, 796729193, 109413961, 141400507, 495981531, 541710753,
	892066519, 460066491, 473138153, 160567147, 202831857, 201838487, 631188730, 58457568,
	910319830, 747799957, 976306038, 200230930, 323034864, 118886288, 145480203, 802525644,
	616420589, 269526961, 425714188, 188488101, 610371666, 211183092, 359394974, 938249741,
	336710592, 550611255, 3881585, 551564477, 203903004, 8340284, 542141709, 420299492,
	46056764, 340339080, 541981764, 75070224, 545108883, 325827629, 194127756, 959517466,
	437059732, 503806073, 460158999, 449586569, 325297204, 140170348, 716450437, 207725557,
	697140618, 858801662, 868495084, 808018747, 668626245, 706545925, 381860004, 50810778,
	652709050, 150251126, 821234333, 379144314, 657370599, 405415029, 767805257, 936195907,
	592483685, 267413031, 738990981, 10657667, 71486673, 323752691, 123332130, 472493928,
	883509210, 18789606, 599030780, 272446341, 268068381, 150020275, 823514605, 88212768,
	896871487, 938740562, 836918889, 16476145, 10762136, 276093857, 227406996, 242768142,
	448030554, 624237043, 872399791, 60549376, 137334228, 888380738, 979771182, 598250629,
	896388868, 944873390, 431139158, 498812753, 947184690, 824953474, 37535695, 362719808,
	869178289, 901478175, 494503178, 596179921, 654924067, 367378118, 262308601, 960304784,
	106444279, 125231888, 73478110, 784251167, 631179523, 186743862, 290084525, 141772468,
	471875292, 446508860, 423178685, 21780781, 74449184, 535177139, 831354502, 111911961,
	115102765, 490009298, 127030441, 956119133, 568249655, 561322837, 435900432, 914222075,
	212323653, 201918560, 133195893, 566693804, 280256887, 163238523, 430577392, 26856921,
	191484323, 203375456, 212475547, 314095658, 458699793, 216193482, 151617115, 915281467,
	388362387, 184874087, 443805105, 646306852, 856617829, 172552263, 561406464, 831418192,
	62322499, 703786681, 791022274, 202964680, 908348349, 652724204, 196844018, 723575835,
	816676386, 126631107, 199878857, 958140387, 589227679, 43906384, 42848089, 878025574,
	434613622, 890769240, 538689427, 934854588, 52419735, 535985489, 695891681, 703923455,
	223870218, 655428005, 512556990, 930596209, 59678946, 13592971, 599986362, 392600985,
	426026852, 399406502, 41441089, 432192883, 855739171, 193076801, 856643233, 987258896,
	657795624, 158620535, 8974759, 40769550, 939845153, 166295390, 135750762, 195932974,
	378184205, 797254314, 717632402, 190679972, 350625160, 176947776, 259373337, 430437371,
	341688238, 713315495, 606958448, 336550557, 371048359, 581546804, 187809339, 843004122,
	194359325, 172990864, 582067742, 30910849, 410965466, 235976191, 462152529, 805745008,
	928755337, 487132311, 953459716, 554755543, 522980367, 602976185, 643918101, 24972261,
	415197585, 281984419, 467250872, 979754128, 24394321, 170612194, 263835085, 971508909,
	246865369, 692606461, 382959778, 586762488, 828328707, 743911967, 118795399, 205685817,
	965735328, 541863093, 490628324, 609777725, 933981879, 811446078, 226446747, 736007036,
	84426594, 448512368, 31994183, 23922088, 991104256, 618060963, 976683405, 656644539,
	598860936, 39807255, 259371931, 379816572, 416358801, 407771785, 620821548, 976102039,
	457942088, 456039770, 815780324, 43009625, 400139986, 465365823, 184549293, 240929046,
	653751428, 588576607, 881850680, 581174072, 681843633, 778695952, 298648183, 442775692,
	490305276, 369612257, 956050820, 367797220, 602534414, 99767045, 426330237, 764365750,
	942602959, 756504580, 730907101, 472892550, 906208145, 419669797, 271417737, 871600847,
	782700419, 550849335, 100640123, 418384622, 790837948, 946157138, 206494086, 921185765,
	475099103, 217345127, 419136812, 498219238, 287092800, 113599154, 900087270, 18967186,
	211851006, 411496050, 578918029, 813462024, 553115726, 389638862, 441646909, 870482432,
	642401460, 985994603, 216760712, 887634119, 925785233, 464573314, 767841585, 221508235,
	626914820, 56605659, 684607795, 290689154, 459282539, 904627427, 42769163, 446976305,
	77868208, 183002284, 433374764, 881417190, 763033286, 391026059, 749832011, 730208847,
	728069621, 85441629, 622699868, 89237983, 168805264, 950885420, 868054356, 214878204,
	464952529, 560533146, 652263126, 562919535, 138651040, 973461246, 499182308, 161016596,
	235007207, 547608042, 911951046, 741180163, 844627808, 498338484, 389357566, 512182399,
	549976420, 289782312, 422231307, 833167459, 635101363, 584406610, 645013517, 223025598,
	443794351, 576537988, 664758697, 422434089, 535297277, 845751653, 482374298, 234439534,
	705774928, 109254078, 872247555, 342694365, 194290821, 21160225, 775982645, 603143284,
	188114407, 793438608, 88655486, 447736081, 790474183, 682488710, 674000904, 330489717,
	635299526, 484518428, 24792911, 809927810, 698927199, 384930282, 25390346, 807941283,
	860393444, 914242677, 871477598, 797598622, 200238733, 864557831, 928722200, 505402086,
	704085554, 713945395, 638869713, 560567327, 613432193, 670986424, 114686917, 217030219,
	160283190, 767986680, 261634146, 614415706, 282195736, 592477773, 252040270, 566614020,
	809044086, 993111745, 93856194, 368397071, 945221365, 318085114, 626772101, 863550103,
	188289621, 519915560, 365974685, 721840882, 811231599, 830170751, 702880429, 991195706,
	670938184, 694838895, 94239358, 227971794, 815180234, 468621225, 299279211, 14176181,
	219417627, 479539504, 261548914, 616552730, 519413033, 640105697, 269856406, 65545333,
	799176916, 877233666, 287897541, 493555801, 901217393, 271845261, 655656103, 324879602,
	455444281, 683068150, 556093865, 989968298, 472434688, 297775270, 906379653, 341779323,
	58985566, 403918893, 164508973, 851764516, 334448807, 428083747, 982390394, 514707330,
	240338165, 150093049, 535970930, 709269142, 445777064, 917468531, 305382509, 971273808,
	402328281, 177188180, 392997392, 163071540, 779284450, 474939943, 100692972, 685733997,
	446658692, 872215739, 315945261, 39209222, 621115430, 259336893, 354572862, 412012843,
	182103192, 266366740, 627258206, 7961730, 561524304, 781412612, 852271305, 477654739,
	362830558, 908237009, 380306966, 897663519, 634639337, 507590125, 849361650, 503854764,
	921913660, 977525676, 132040649, 523995019, 242900792, 833330204, 567117104, 476566708,
	588935266, 45245908, 120679556, 680071660, 929162894, 799479485, 922305338, 384980492,
	674272214, 826312288, 792131236, 748247258, 352889834, 300850375, 675208207, 904271901,
	211546463, 167454293, 396227302, 280105938, 348044017, 268289295, 401108588, 160489635,
	428301920, 803754030, 466230959, 66508282, 661777727, 260040168, 658410754, 679085583,
	463522140, 649647870, 406156783, 978794845, 354539182, 128780225, 833765363, 532006815,
	520916749, 2940843, 195759823, 46303349, 661592052, 12576312, 2051047, 367838659,
	373427487, 467665042, 724833950, 377245050, 628496385, 250370315, 744003883, 382287743,
	127424638, 737864883, 864371146, 5721666, 971179624, 971327636, 761143644, 613343227,
	330865061, 205295368, 831082694, 271339714, 74904314, 943210806, 323106554, 140880627,
	296779896, 581171198, 850455308, 283642448, 110120585, 270478970, 718306233, 181034329,
	508561145, 762840007, 262723048, 492855243, 600840778, 540478998, 709532476, 610501372,
	166780239, 700877294, 970860427, 165008672, 466957508, 545921825, 867409930, 51431620,
	967778118, 22884000, 607810843, 437746064, 684643913, 682016426, 635068402, 656202898,
	19634060, 420428987, 495138810, 877386301, 138222472, 179889020, 186306546, 854165214,
	874069376, 119455586, 563489476, 875074003, 355736705, 477002487, 213268346, 298261911,
	95873539, 511733821, 628561071, 756537346, 258256156, 852165714, 99365029, 884346438,
	263560659, 80563348, 74552531, 282293431, 956790939, 724847696, 905613085, 661507401,
	708947606, 862667624, 324068273, 692207307, 519449754, 511989137, 945534274, 860860428,
	144858022, 898590239, 120726705, 98222426, 490627466, 827481953, 316526164, 421265933,
	532272305, 582007204, 386104671, 149238413, 391776252, 58408374, 455116899, 965564580,
	412588906, 156593002, 442102252, 96148649, 444673558, 288622040, 359235716, 620643412,
	980167862, 285279902, 27537286, 650038364, 91188487, 881167162, 117381294, 846641412,
	240169929, 599449686, 136277536, 736036300, 635979274, 771683164, 254052679, 65078895,
	7015847, 897306336, 622619159, 301031021, 313637220, 716081831, 664937509, 199684439,
	617886469, 580902326, 758837441, 537592128, 840706542, 751646261, 833077554, 390417847,
	370183454, 535639725, 539936183, 520695945, 164796826, 882469967, 31234412, 926186316,
	239127881, 647402926, 210792623, 180936077, 488508155, 81952229, 360696581, 78316422,
	45567119, 228489115, 860925244, 955589810, 801953175, 227287957, 763267081, 261734720,
	806917182, 962342705, 932717558, 890248284, 854004853, 42120699, 458211648, 666288188,
	866949818, 194139843, 196816866, 722351799, 258399220, 683703080, 958006894, 651965743,
	372032039, 304366379, 814575321, 935425080, 661280295, 737248877, 194722350, 983920212,
	374428494, 538283469, 622294370, 294128887, 750771629, 815081113, 409929796, 717971452,
	750718587, 780476327, 948563048, 316369158, 680863162, 270733533, 179608920, 862141691,
	25583689, 483394261, 425699643, 109927527, 865683996, 911624624, 187736327, 220475207,
	349671925, 251935461, 596545876, 103144579, 842636300, 891308646, 247926132, 423604552,
	351370758, 853121617, 197354482, 412713563, 240795241, 725028722, 311489980, 265792493,
	833832489, 3671040, 828185763, 755493498, 819345704, 602697724, 221321239, 355712238,
	835388325, 330940463, 753784854, 559084105, 248847588, 203361692, 770272735, 350512322,
	226534317, 395313045, 984182381, 24952620, 378247072, 816916115, 738415739, 328264420,
	232690098, 725268142, 130261337, 851014709, 140734178, 856473972, 691595145, 448932982,
	556066822, 452296366, 687063765, 143679627, 563899735, 137077426, 521807662, 252390029,
	42002598, 372572946, 483206090, 250851260, 928162394, 233058481, 619807626, 610273737,
	213407277, 296684653, 470175218, 258317312, 786103900, 558819702, 883999748, 630563085,
	17055285, 626734845, 301823323, 576934609, 374186005, 58641218, 14036545, 75233923,
	8968793, 832443355, 432453666, 983398296, 533281416, 24073940, 113353521, 951370795,
	985022727, 916590741, 471935802, 336862469, 99464272, 795192628, 322260115, 466750740,
	32001665, 826181006, 494155645, 293843815, 28153708, 17305738, 192275669, 621718641,
	214528454, 392841060, 180526800, 399806130, 64683019, 740979482, 828434634, 6716310,
	406150799, 672333531, 349258582, 530802564, 657649831, 319679965, 22459738, 190746842,
	122907290, 607908122, 88275069, 119253127, 839874130, 23823786, 84598383, 964946117,
	265156702, 427109631, 163242321, 126876824, 513722056, 629329156, 133798325, 43164647,
	793349516, 230360733, 415923005, 716726304, 490157566, 14683597, 783407788, 248406310,
	215436293, 7568890, 148955620, 442833616, 227965498, 480816107, 741353042, 332078935,
	609331634, 654530791, 211492530, 452090193, 623592752, 626936139, 95822294, 199982752,
	808544732, 578726500, 650129053, 517749841, 993148329, 106298335, 287766583, 321819823,
	87133548, 341542817, 27691064, 218313461, 821609466, 717223118, 426414172, 435601290,
	486797136, 510676681, 727359890, 23495176, 444016154, 48266150, 460587487, 827488981,
	248246624, 208441269, 970098259, 663131224, 823224183, 735192719, 620144183, 785003548,
	508110902, 93248864, 93506544, 579604050, 234695417, 398461128, 642746109, 499858476,
	448572380, 961938203, 499657451, 598319614, 841453696, 374905064, 63510495, 593054910,
	5806127, 774790996, 370071902, 833406204, 642920148, 745721239, 639075581, 800338168,
	502875867, 822509244, 75178923, 802771160, 831150981, 674806482, 679037128, 334939912,
	116251117, 139428132, 943198854, 28349599, 694426274, 179761228, 227746861, 777061899,
	183097664, 608778777, 512159566, 42551946, 199896233, 206031775, 497480108, 181895683,
	170263297, 330536359, 191367350, 799544004, 188646792, 88606444, 277527977, 640118598,
	536117329, 176317543, 85516496, 275032025, 33882414, 107058020, 365086979, 978321411,
	505909157, 890881250, 236747845, 757687652, 608465138, 198750812, 422260539, 866786046,
	170926160, 406578157, 74784318, 394090221, 856306029, 281121306, 154905708, 904488896,
	22045737, 279812905, 420134544, 712103335, 378829809, 105758918, 317797568, 47657458,
	381772251, 72858600, 671062524, 971950548, 940613438, 813244222, 302882691, 381564921,
	534180710, 700167271, 74674103, 169637629, 219749994, 238102526, 837907457, 94514951,
	37038194, 838151577, 190007985, 105628633, 172212842, 930152689, 583830303, 479332688,
	319683475, 216414051, 621291145, 945659685, 406706502, 191073605, 884621592, 951421341,
	374439881, 532501376, 507507247, 504783307, 477984136, 955219931, 503307194, 469822245,
	543083638, 766090575, 137480459, 912376673, 375951014, 302049545, 508743144, 478616981,
	94285547, 414131717, 933825818, 206478853, 248641082, 139306759, 33955519, 843290344,
	470414326, 800231040, 615429080, 168758062, 568464509, 744677736, 309933684, 342525373,
	880631489, 790748626, 820349664, 871904541, 901681945, 414558293, 230699449, 667355931,
	655319099, 574243242, 696190507, 247718773, 962164750, 74203100, 150997025, 747025231,
	452052533, 144131901, 817028099, 468554450, 799841315, 252038002, 567460588, 491616353,
	956881064, 168637619, 507609255, 664956056, 92446815, 955030397, 559923226, 602472060,
	739811514, 428308329, 470979565, 630670829, 379024246, 162288078, 407463299, 74600295,
	257355706, 366338071, 451269724, 491228255, 125888409, 264898033, 870053159, 32092261,
	675382782, 480065768, 78874581, 251627635, 466084520, 941713919, 578675381, 860385147,
	18720342, 158012251, 985311042, 196674965, 824393055, 377359437, 55607756, 284826136,
	587926712, 722096479, 751245944, 209654550, 756830039, 889383133, 93037780, 819425472,
	828633363, 224635205, 942293626, 641329282, 102220754, 720066435, 162254254, 227529396,
	179133902, 303294479, 196596130, 789224212, 725955592, 952135579, 701664564, 28613280,
	439071602, 408318665, 493668513, 692092654, 700755318, 123558124, 302522047, 422496475,
	694266603, 919537448, 350809351, 409061631, 739140540, 503266887, 438446447, 724176670,
	841234268, 146075994, 184589067, 440205662, 575746938, 43672014, 230554732, 300061101,
	338843576, 201760327, 60490073, 620647915, 393119202, 870775824, 293432962, 405118001,
	274128072, 409701187, 184351501, 466393514, 60184073, 350100567, 328348869, 991595198,
	281485671, 465062725, 636372552, 746374624, 989633941, 754027656, 515830868, 655348363,
	742134016, 597284246, 860067717, 101352934, 912630536, 387910492, 328962508, 136127462,
	813341519, 572823905, 952156224, 548578511, 446344267, 894783669, 233563094, 775903857,
	649797215, 207904773, 302540301, 338474698, 878444587, 123132562, 273247382, 933206918,
	616512705, 736367000, 646366870, 340000038, 446040152, 491330614, 59734891, 736745869,
	276227912, 941886104, 472837654, 858573606, 945608977, 444520908, 728461580, 716161578,
	222785194, 67616213, 480800481, 93170664, 471128495, 12449412, 920546449, 689917697,
	684038023, 10787218, 223360954, 247211863, 584538195, 290096974, 505718910, 314176311,
	382494725, 338169976, 237883269, 385483264, 384111935, 234571577, 664965257, 907355753,
	255437324, 705197266, 195866561, 821932796, 723592860, 674609636, 699078244, 946364517,
	471654428, 168153948, 635297879, 798387525, 907137578, 829489134, 510559338, 482281672,
	951202945, 808890312, 150790587, 309807007, 51083368, 945315096, 479548665, 525140495,
	961907947, 156035651, 420764539, 732430623, 51398457, 569967788, 29748584, 334062331,
	902781816, 810466718, 109830152, 491941682, 583564439, 912558696, 256658411, 562451562,
	442140830, 890607451, 160084954, 775870467, 257997366, 124926329, 177503702, 673170222,
	806394894, 378302730, 748928941, 279401657, 826694043, 248616753, 530418052, 706731561,
	702296161, 886733768, 901574661, 726795099, 896325332, 439638149, 559510295, 459905918,
	923189316, 832963210, 207385663, 564764159, 963771369, 555451367, 619973600, 161372779,
	548575377, 318592989, 895741474, 946413376, 890279997, 646476699, 455210876, 345181331,
	250954010, 745034790, 165821419, 316754989, 476207818, 559514929, 936509454, 654744923,
	388901073, 112356477, 680863028, 653460444, 768509840, 605174677, 291921088, 511241340,
	691753670, 784694710, 362962082, 14526381, 448799593, 702621656, 595397220, 175771340,
	19119024, 36757808, 25251051, 949891894, 583518723, 767430152, 666855297, 860296237,
	899772744, 74650963, 769237277, 490473921, 164331492, 252703514, 344022044, 244014210,
	545916498, 175935665, 568538603, 147647142, 810253254, 875728532, 217192296, 790486794,
	519702849, 627197788, 632746099, 307388146, 381045235, 523909635, 160141966, 548249005,
	947169254, 963716604, 872839769, 196109692, 721576580, 153714152, 804492971, 834411402,
	720198630, 70264863, 410376922, 799301476, 622114810, 59004664, 686893293, 830650627,
	801677200, 257469897, 527106906, 887275054, 468054241, 716878153, 18074126, 270408697,
	392741353, 563281173, 951378346, 217417797, 290235949, 53435165, 876870077, 886691667,
	377657430, 129213674, 129453568, 560990790, 332144605, 331766813, 791297613, 926343091,
	652611874, 521329531, 804798690, 253275179, 879033852, 769899133, 641472276, 201518475,
	634980290, 340405084, 536076657, 640386729, 550259529, 189468633, 226600062, 424159603,
	989346980, 913587364, 809294017, 39804426, 290029131, 355472843, 466977557, 948896893,
	246239186, 377907990, 250920727, 747519287, 379959954, 116707893, 709076675, 873286910,
	625200281, 259234794, 600402599, 738788974, 390074558, 570885374, 276881397, 685457858,
	13175103, 956962808, 114037983, 625916000, 258244872, 153147578, 216086968, 636908074,
	262882150, 566797296, 287585763, 233917398, 946830364, 88942834, 26081238, 421544685,
	239754689, 441048423, 755004923, 455415723, 254770423, 240989762, 739503521, 771450194,
	199968858, 879985979, 669466117, 258795744, 109307781, 562513245, 617157586, 484132549,
	656729178, 623569015, 358104040, 316548588, 290139769, 465853262, 982126017, 935140300,
	440764316, 55013137, 779258331, 989112512, 555791581, 123264216, 966114903, 987121574,
	364003283, 250675571, 91464086, 451269694, 333857090, 619514113, 219553920, 367598420,
	105217391, 295566026, 914258848, 533448110, 695639912, 44607518, 197944264, 444499751,
	646568868, 213224254, 300536541, 532586683, 579490494, 782928283, 91493755, 793747066,
	937342115, 55707898, 359711068, 810998263, 514711418, 670228180, 880053369, 239635794,
	584909084, 268848759, 592751483, 616794532, 59545381, 488413189, 734143148, 414767106,
	81799985, 657879515, 334175303, 380099864, 616623138, 444245426, 992227127, 304678680,
	690387116, 624287418, 185163660, 731303566, 983578622, 856918442, 180003257, 962800195,
	92607248, 400787149, 244240140, 845879294, 939720097, 490816487, 233349291, 104647467,
	452007054, 334915148, 50431285, 968402496, 620526604, 508361950, 636576018, 307820685,
	23856842, 208765027, 963571316, 679332809, 839518748, 176572199, 776266728, 101129643,
	131381944, 238007587, 157045307, 350979431, 908408257, 56626943, 781627799, 818616662,
	69946711, 49091999, 695644754, 845410486, 355015207, 733194426, 779855013, 888601812,
	908149670, 709616028, 438764368, 262609715, 200550756, 175712179, 319051057, 965448245,
	264948306, 581760991, 628176261, 158279546, 869870703, 22600205, 483356178, 904978480,
	807287523, 805470832, 219855902, 772091144, 485872058, 128897981, 251153535, 192023469,
	641848989, 283811693, 609320037, 177484597, 710244676, 980388083, 296969302, 147217139,
	802277179, 246099233, 914363135, 470508365, 945472206, 937336437, 100280919, 949983041,
	875701850, 841734030, 191759810, 344663955, 756949289, 414199368, 402287189, 440919112,
	745423153, 27019405, 939875094, 507500667, 752360448, 932863282, 647614022, 784125359,
	843037146, 136352512, 607012851, 23459254, 629898651, 726380817, 596092962, 758562507,
	893994782, 750258316, 106984126, 256528141, 240999241, 717900539, 377988935, 780770891,
	132250216, 458763856, 707662292, 406498545, 170822026, 785287876, 25573259, 617989690,
	197548253, 530259872, 565422624, 661004721, 60038451, 796111230, 517857808, 354391675,
	525707799, 677844913, 403248433, 63533201, 279099534, 947374913, 408451988, 829111685,
	376096720, 801456337, 139119910, 336850187, 161527374, 595462233, 1848282, 517261440,
	457063964, 817472396, 144100079, 683011729, 803561052, 161561569, 226137956, 754520722,
	105840336, 572937469, 799264398, 844690148, 452120558, 693455240, 622422639, 877193249,
	878284001, 69851234, 465729263, 684145625, 385404954, 916932336, 352780036, 45931516,
	687751559, 394454271, 717836361, 186405319, 643678892, 165728189, 960757863, 241679415,
	839175430, 484405016, 818448893, 615344283, 389026899, 873511231, 299390912, 342050422,
	170787791, 573275557, 209467558, 233770719, 920301651, 761978470, 257535814, 151911182,
	482957225, 603772720, 86342769, 824387682, 127255077, 699865226, 50823692, 994437925,
	928507410, 223271521, 316867540, 838354996, 119077975, 660389742, 597961465, 205490473,
	929659739, 17295967, 114963789, 197845887, 487782741, 984185581, 566157759, 90561013,
	620382696, 132740642, 85300000, 196369866, 489662729, 365427463, 612532600, 386721609,
	678611878, 892734272, 782123566, 139160794, 333174841, 345708644, 592105037, 903625752,
	446955151, 534847102, 448619812, 483263571, 623545558, 139568061, 219062986, 196443871,
	84236048, 185708222, 314819378, 237759330, 491054742, 814370482, 695655041, 964419096,
	139665212, 645253420, 360374087, 819557807, 157001149, 699349965, 533918202, 324578196,
	840944926, 460791, 656617384, 118024702, 31685737, 848955722, 52779157, 550447529,
	882526402, 124678889, 435476724, 921965924, 96917086, 28794926, 94914385, 226597336,
	391923106, 591129825, 957887172, 301764461, 263896249, 469319844, 467092192, 199087011,
	494793004, 143796633, 480535745, 625029782, 837709327, 57253623, 930253243, 643467278,
	827675781, 978449234, 840710882, 547283485, 134156411, 594189178, 930452876, 772059581,
	107171423, 552784369, 482091550, 478797081, 270340051, 665057048, 773212317, 993457265,
	657192521, 114227868, 104237950, 47716662, 905222707, 3347639, 84570350, 313662067,
	753993075, 844144774, 759531355, 99595179, 341033418, 594809764, 447820415, 838043945,
	667718529, 273135923, 574605506, 597321930, 929700714, 892726043, 329555232, 227893836,
	467588754, 571328702, 677425641, 431113407, 814219687, 486503749, 3574746, 727733401,
	53495836, 110479803, 299762551, 37880438, 730757024, 823619222, 196837421, 297369239,
	207595897, 367828103, 786135223, 481464091, 918967812, 191403547, 746238926, 479340648,
	393436527, 707152380, 869215081, 589373544, 828376938, 683211316, 445684310, 133787832,
	269813018, 579669674, 959663797, 962033330, 926373361, 639765576, 819166763, 546925099,
	946617817, 777476964, 174619303, 532425258, 809271640, 734985459, 836969754, 647859665,
	941027990, 534687618, 931171362, 519244923, 823956738, 764612887, 261081896, 272821160,
	93475618, 731461517, 231987947, 935123455, 835676502, 481881173, 550585930, 174987615,
	856873596, 807742628, 17622639, 313529576, 550840787, 567742040, 256934222, 835044968,
	439590637, 138272338, 55616110, 302276410, 319286298, 157090599, 902479249, 437130553,
	717085190, 124097977, 302196512, 835198497, 310086782, 345568880, 295110475, 357479489,
	914260723, 748562799, 676900440, 539940790, 333920790, 436849542, 237704508, 651857770,
	245280646, 26254913, 491372368, 376511349, 231827507, 77210352, 810196923, 381322090,
	912131287, 357265041, 834455920, 136371622, 561142685, 138481279, 594927358, 416710033,
	792026805, 663955029, 652676125, 644785289, 558422904, 923891195, 400713829, 888113796,
	861481277, 986166926, 127225904, 144182144, 146663364, 661405288, 179258871, 802495120,
	548741735, 777845842, 357515957, 491483027, 806722601, 47552913, 918650213, 480994705,
	127023279, 215123155, 243210620, 3505616, 972933993, 694107579, 463272260, 209030689,
	523767341, 449439369, 876822012, 179732894, 593399179, 127937675, 611096260, 237261047,
	372372263, 731780504, 546101569, 83927652, 293103617, 688652080, 698985469, 903758704,
	637697735, 554194654, 979180921, 923440474, 740184544, 474544443, 263550826, 584069838,
	453739760, 950093624, 742050703, 826047016, 729907164, 183100370, 679893807, 442637016,
	261200153, 536973709, 724931612, 632245896, 726202768, 881570949, 792400342, 934102439,
	692339981, 183614056, 393320815, 652611337, 969793112, 90114336, 648314968, 50331389,
	89666563, 289421740, 56958351, 428885101, 722193242, 180751710, 144377294, 144011058,
	677543783, 661056421, 635394475, 719947147, 17011231, 720191387, 399254223, 895977374,
	344573088, 78870007, 312847436, 968738701, 726696364, 574445427, 485802935, 109511769,
	861404499, 369383620, 962453941, 97864415, 349884484, 443378810, 320083636, 97797798,
	15832984, 314745250, 293003018, 282940551, 477453856, 99132377, 147686621, 48605630,
	650395286, 603726443, 65034683, 804089995, 603135349, 539531873, 574683418, 815398250,
	558492246, 844795507, 740119273, 69885114, 593826579, 923330618, 981840076, 702075068,
	663449376, 331772476, 606383972, 614143521, 20432826, 25959414, 584956112, 49227683,
	825051585, 680259864, 413229993, 156225878, 664378049, 953335889, 593374326, 44289936,
	583284715, 395191605, 840728924, 171607689, 521400992, 89144137, 511567454, 27349023,
	923222974, 306725322, 694291836, 947986934, 790857060, 648885418, 218203679, 469073319,
	808070537, 684310348, 934432987, 922757164, 239292243, 416508230, 593962166, 838617401,
	826620400, 284156653, 878499454, 296265834, 445709403, 530370156, 77677111, 617915165,
	937398984, 885523553, 288166397, 591974179, 332168097, 711837378, 161121300, 22826263,
	558080789, 456623136, 277530924, 483710985, 684227224, 293833626, 369663218, 42725196,
	915984649, 273816686, 916028779, 933805313, 272474439, 850060750, 110265890, 525573604,
	657328927, 210276873, 39072228, 617948384, 222825675, 294144532, 484484831, 904393189,
	115540989, 346232020, 347765303, 873715444, 97221692, 840573425, 925142158, 307778207,
	991078225, 579251581, 438886947, 861671071, 194299570, 977108863, 844047472, 544903021,
	732661370, 698373719, 40670518, 992504767, 383765483, 172906028, 301545320, 37247513,
	706029275, 187358176, 158405004, 345992415, 530098751, 429886704, 648947362, 835524302,
	663323190, 345485180, 800548220, 354438650, 285725254, 274349019, 769096342, 923553274,
	738905108, 248010168, 978038533, 361158087, 390812713, 466864864, 760066260, 978809210,
	996544062, 979770422, 576179850, 297459362, 644060103, 263847545, 840145751, 80905220,
	401212366, 503554759, 42140484, 893467390, 253258694, 32993716, 850139312, 758174068,
	555973212, 625722724, 656294096, 659806453, 331763605, 207976061, 931243564, 784870408,
	980043233, 291162262, 919835501, 967853608, 589104029, 674225141, 822508402, 841001599,
	518512226, 416965750, 635469293, 316829007, 19454299, 949505694, 73009498, 905254430,
	895405022, 545895147, 324684946, 917233724, 85987225, 816545103, 637813557, 712868097,
	132192765, 548400904, 316862657, 372077365, 264721262, 846797482, 652435370, 842263497,
	597894231, 582182027, 129173678, 780386596, 550268923, 388359238, 622084924, 966234741,
	758445789, 129100201, 384628745, 744819168, 733414879, 153340512, 848821635, 47852966,
	636951913, 391954480, 674912400, 447902804, 669274368, 948303830, 272810365, 201666935,
	2856694, 55552898, 562436372, 228263252, 285654875, 691450979, 88910472, 111165385,
	947342478, 985359602, 320996252, 475811885, 95381719, 85222585, 265948454, 963603560,
	377833337, 46331074, 937887726, 467519500, 863382863, 306747289, 818912419, 617710439,
	786075225, 297449777, 675699736, 575315169, 571921840, 65947633, 951200945, 155444046,
	965419686, 369181360, 611694487, 259008451, 606267146, 664671876, 520607604, 101779813,
	395095090, 868232402, 365962710, 262473181, 919993464, 698775335, 904630449, 430182021,
	606916011, 425157156, 989607675, 681836310, 734640063, 359166790, 128163877, 919531567,
	188433847, 27040060, 192274191, 179929621, 184886897, 433937281, 386533506, 777889009,
	336142208, 837002887, 669066956, 667423354, 13432922, 895106942, 26971844, 971926366,
	121279219, 66670666, 477063928, 12417692, 852410220, 296463457, 826098296, 735635698,
	135345979, 713165838, 867194396, 352800477, 25505008, 701666831, 630535655, 886905521,
	860403973, 645100534, 301766534, 782083893, 146543442, 89318262, 914849894, 402450673,
	904986798, 181681636, 148451785, 696643012, 460837744, 820814069, 233787830, 120628696,
	396099425, 946467464, 651948112, 338053108, 641960516, 175847197, 295029873, 470323038,
	149281412, 309173796, 793244226, 683482453, 116635044, 678875166, 608250374, 719853513,
	240442489, 101608134, 583739189, 496961229, 295794645, 504247991, 682609963, 346174754,
	50943450, 639111257, 18455858, 109253017, 292925002, 429445576, 772164052, 635535278,
	521535558, 630696311, 833546148, 868025806, 135800816, 545232742, 780520731, 506450117,
	520772605, 822098937, 157857288, 604293800, 79990190, 475962237, 605065386, 347352069,
	280382318, 221740297, 488514395, 505504078, 642958444, 792893483, 391069892, 383107426,
	764786896, 16453453, 529322178, 172541958, 881249724, 151911789, 423939921, 524863494,
	58023116, 203086391, 418644998, 717843345, 724519774, 349747806, 272401064, 206722117,
	464077171, 636495603, 839392987, 593086198, 589746181, 76290449, 777010671, 211256399,
	735594008, 961412830, 378457060, 330915866, 958850171, 455410113, 403384295, 912863492,
	869373752, 954118104, 275450602, 490698761, 499009966, 289773412, 165004520, 407822505,
	8696133, 581888586, 508933269, 942284184, 257817672, 489583572, 560565726, 249220903,
	697188385, 563821593, 24267151, 524154697, 481647208, 617525603, 447671929, 896054819,
	477645338, 959891477, 743775484, 328727821, 667187961, 204111514, 303385895, 211482214,
	149436239, 449928330, 548656374, 373988220, 952450847, 728193095, 146179997, 912986028,
	223630480, 763301257, 133790241, 103737783, 263839084, 601262934, 244825803, 923247857,
	984485756, 144642061, 821783923, 353976001, 320023237, 645765668, 861042461, 385028240,
	816606673, 758185535, 26338081, 942540913, 432463136, 484008413, 5142870, 764491575,
	22316349, 529889146, 828461951, 305024654, 852670636, 428400412, 612949061, 339650723,
	680021043, 185387157, 668791202, 718849121, 704483681, 908263089, 816616176, 680838393,
	951035350, 429546528, 605178469, 522604237, 818497555, 703314448, 489429394, 53727675,
	362424474, 369008751, 21829849, 532790205, 61906620, 721999811, 606312417, 829790081,
	170235078, 44956004, 902098592, 73015469, 144183491, 44877400, 926716626, 248159816,
	181667447, 401438531, 370437380, 916410724, 570129445, 989988880, 926511727, 914272501,
	820258811, 530207277, 583232620, 755872818, 321095229, 265812891, 444849446, 685544646,
	504295826, 541506322, 896798002, 569708491, 862163359, 676522230, 538311732, 42382079,
	210221049, 560446919, 854872175, 625878832, 192729287, 77749055, 710347464, 628342591,
	332167472, 466910153, 577778976, 564497619, 175882404, 283097915, 95093799, 509908839,
	734952577, 841808275, 38625193, 786036850, 417705036, 68680440, 540066977, 269150225,
	766361494, 336090884, 84321193, 280203960, 297997743, 178966085, 848678857, 86318377,
	233570942, 88044212, 773856717, 642492367, 968598918, 7923398, 517133579, 319924513,
	992840497, 707616088, 108706765, 876482281, 823662590, 352060832, 57819144, 645395014,
	224753607, 665889993, 205717063, 994559644, 371794284, 299729453, 284679684, 171532075,
	417671938, 913963390, 186714466, 588164340, 834032028, 508904542, 429943776, 526702391,
	199754274, 201310703, 574457312, 540071744, 677794456, 535887041, 964504446, 764297968,
	376941230, 120851188, 78654797, 323084053, 811293030, 994596687, 674983515, 795816469,
	528811743, 651556124, 73934185, 22130546, 854828283, 184389704, 988386160, 419814036,
	11880047, 850695134, 353913860, 469564395, 951386596, 501085955, 777757272, 977267901,
	690889853, 344505503, 576057909, 261938607, 927609200, 769188314, 402615911, 34007203,
	275790726, 848508787, 837866556, 560092926, 116948865, 85493396, 447688814, 929226181,
	46114055, 24618985, 823438432, 687826893, 458421848, 882556116, 89244410, 206503430,
	106186450, 270642826, 599867778, 439856003, 844598806, 250740210, 571348669, 259100138,
	142637366, 338887575, 924035004, 427153398, 137661923, 736475989, 530752634, 666132307,
	150546053, 133841183, 799712563, 851960991, 713812871, 208329791, 260197391, 138169811,
	820840164, 973416859, 782945321, 914393279, 131129071, 334224545, 807793715, 916321356,
	966438917, 878315595, 331598879, 352381355, 939612086, 570164942, 161108367, 31601778,
	526491062, 542685267, 413297781, 678812449, 862951592, 112290246, 582549307, 277564304,
	431896075, 231014904, 18491445, 199326249, 302440367, 942901583, 67695081, 607308307,
	13628507, 556423227, 556306205, 693249322, 102786825, 537221787, 667644632, 780919470,
	158021876, 897827094, 330538746, 687221906, 952057610, 733038341, 674548456, 684830504,
	970717474, 444262369, 940191172, 513297265, 496576117, 579686618, 759673776, 550853011,
	734833661, 564587579, 814674201, 23586806, 908117838, 5875161, 306519720, 451986616,
	571657768, 48223848, 96470470, 345743318, 187456116, 772893811, 869164602, 60040496,
	328332504, 779366243, 329470213, 652736724, 747960626, 657091417, 863074370, 787446829,
	435070063, 623736537, 207765335, 493686509, 875756938, 954860361, 545483325, 465604360,
	632143386, 412009788, 841087457, 312469714, 352980017, 781041573, 67459480, 94717394,
	580295592, 484743095, 766740033, 156164946, 321932885, 872229996, 172704053, 609327165,
	962477966, 595527497, 605313222, 270271149, 199840427, 118370786, 324630369, 258539443,
	716138426, 512127605, 280520465, 78957255, 92848329, 270309256, 611545106, 156710979,
	638741189, 777091864, 151279269, 414542492, 990500572, 444400474, 966210992, 672960670,
	785705697, 52184453, 103358922, 209322712, 293143174, 659688403, 338813186, 179934132,
	728804571, 706767352, 811326531, 691614842, 635546550, 144968464, 39171783, 743487154,
	11188756, 884540547, 863837568, 502645073, 866216519, 959795495, 898196474, 376740545,
	753715698, 572703035, 756095860, 28553817, 339351290, 978158497, 445592328, 460582078,
	739853962, 234174479, 236890308, 879430753, 235984749, 442858771, 708510277, 694861683,
	20536106, 823148157, 68898349, 227412905, 68982013, 427700438, 641003539, 198155877,
	475379345, 479722019, 489224971, 557893287, 53600097, 498219122, 835183580, 279726792,
	45105841, 70400966, 144955273, 550229180, 844702828, 698644464, 754636851, 910966442,
	88462174, 533823783, 839843278, 102815362, 1058406, 250999329, 333114989, 108775261,
	271673172, 434014290, 519821323, 398294075, 244159078, 71319975, 553312174, 552559423,
	625998719, 810075839, 27862271, 601175456, 173520639, 117091095, 360236004, 682340234,
	982138522, 418937956, 590072620, 26321770, 490442284, 389678896, 775182825, 606000865,
	585775775, 731605509, 234473743, 750658410, 843531981, 502182829, 121409652, 508833921,
	604809222, 320579892, 916133373, 767683639, 414570378, 392581947, 239652131, 841050928,
	663183030, 446140153, 756137568, 345073246, 170994502, 343795285, 653122748, 234073292,
	199722980, 772512042, 732995579, 888838111, 332820800, 594590212, 941402752, 195991887,
	254095126, 76620972, 547954476, 780055617, 202793068, 189625574, 70688592, 774072917,
	211807634, 38182896, 293862492, 316506284, 189897207, 937377923, 820116095, 568902032,
	219219551, 582829248, 795970159, 307779534, 353730355, 512997217, 70212047, 448837720,
	478008419, 577206628, 130376959, 652718424, 739654344, 394326533, 427523039, 861375618,
	288570720, 975117500, 883642159, 456223325, 605147845, 651980380, 796503611, 762771487,
	194715230, 332407413, 320792078, 273056848, 981659596, 374663642, 750402106, 769724788,
	243463207, 644042580, 948010625, 62919681, 516926061, 35031605, 699490639, 15809659,
	246865373, 555685083, 275224120, 97456205, 789836498, 919055661, 236972339, 69119379,
	463376487, 118904174, 124313101, 648395181, 622016349, 975773811, 322637786, 17159815,
	316443541, 193417819, 757956619, 878291353, 505594195, 154647096, 637674575, 123621444,
	47796138, 213856079, 291372290, 80990879, 643542050, 290086276, 132710759, 476416218,
	869035744, 13879455, 399347479, 859161716, 234291570, 297719050, 725951147, 644140370,
	68708468, 115175080, 216455137, 575016946, 621255943, 243327745, 290159333, 114527137,
	202922168, 84253788, 880109266, 341605987, 486073609, 4325869, 829348773, 766446016,
	755349214, 926834402, 167338226, 949904466, 921437348, 820399067, 202251560, 91335001,
	245262975, 527860881, 889862601, 309052503, 721320084, 396948822, 474599774, 984670553,
	199900503, 477308009, 133614401, 829863761, 847458803, 745790839, 326181066, 537085885,
	136244583, 923515993, 234807081, 633319129, 584786945, 678747750, 688619098, 950060238,
	673535121, 12822883, 21719762, 95954553, 924730103, 339521276, 77829022, 281009669,
	650969410, 598539041, 873034881, 350798882, 60317069, 970896938, 376205428, 804360343,
	932978164, 844048899, 745154197, 56278893, 992409462, 937153689, 111911740, 861055034,
	566222746, 767463984, 196031778, 514290709, 739269274, 10324240, 234767857, 327366463,
	882182333, 211464752, 984603674, 198511117, 327020279, 753938251, 57496690, 867401585,
	55188168, 179119644, 992735620, 940655392, 228433556, 908891899, 85176811, 68178778,
	43322401, 114897075, 838367978, 658804039, 776153848, 296012255, 497329128, 206759785,
	495968583, 340664922, 420636333, 41335721, 298683714, 249501811, 414147514, 22561795,
	376912768, 776295582, 554013451, 912819936, 868860139, 105517663, 267574715, 5624147,
	571946805, 90393647, 540316130, 880278342, 849591518, 846801105, 569371821, 49567999,
	519554076, 272187637, 815025654, 986225023, 526841847, 629729251, 683636184, 582360864,
	188658038, 324271132, 154136405, 601012989, 105813819, 928541494, 757581097, 906910768,
	120331960, 823650831, 331680173, 97862451, 37876724, 24558322, 130881011, 160878695,
	353720239, 16721175, 984712829, 47064594, 72583622, 132166074, 356446911, 751834753,
	682482512, 314671670, 881860612, 436159014, 372318604, 705498699, 36595153, 103369305,
	830419870, 925161720, 954800526, 143223367, 516876350, 992353547, 724835029, 964590200,
	367085466, 577624007, 331990601, 221981610, 51964406, 908269299, 688999973, 771222625,
	669127165, 786564615, 264891297, 508505089, 333712360, 454530661, 115775111, 401565655,
	981114129, 371980514, 988534103, 529077037, 983917841, 806674480, 577924967, 342608874,
	86710835, 829422854, 139050913, 82662577, 341156890, 577152570, 167103457, 668918863,
	845382098, 486690141, 390710472, 521636702, 112985273, 357943543, 804265483, 182793009,
	810103736, 263854993, 196544713, 784202215, 310545181, 995430509, 279500295, 122457225,
	412999099, 462318283, 408011865, 624156906, 259949637, 958369082, 141568223, 34557060,
	630008035, 870789770, 176408518, 822578909, 741774775, 963823020, 151672075, 626850974,
	88471951, 565312786, 856396516, 886658660, 267111404, 242653461, 290544610, 11151030,
	764354348, 95816085, 78288916, 180438995, 768115224, 370224620, 606558516, 879828954,
	937542343, 260185587, 940056545, 907134214, 673064896, 714964707, 193706142, 212405819,
	209246227, 663774518, 705845966, 623127069, 406849384, 52957814, 725326004, 441167356,
	438006446, 111508950, 636883067, 817016654, 897272481, 602995767, 906026686, 62551345,
	277861984, 894386295, 215219336, 730491490, 175946756, 201554591, 876832916, 96345711,
	276610758, 613415012, 901572468, 593756907, 901259198, 332034545, 573643216, 46045482,
	725469211, 620508305, 208166827, 986765882, 177281054, 949409761, 941419855, 309261688,
	28547735, 861469088, 862130411, 693056001, 550894417, 371726640, 640450210, 952414614,
	151404581, 656911230, 884615987, 773358306, 168940336, 653154640, 644953442, 451995852,
	812022795, 312842253, 904385809, 613040051, 611504036, 383975919, 947605176, 924834821,
	894191013, 950098681, 760257196, 913476090, 326798724, 919057265, 70540273, 910930663,
	321297312, 321069965, 911872271, 604566313, 514999548, 51431808, 364926145, 997276609,
	775554083, 354002485, 784567397, 590126246, 194422764, 118594387, 158423181, 819079329,
	596569842, 165994748, 896195670, 369038079, 895759536, 738389718, 425757889, 680574530,
	634671016, 99088265, 484376066, 592220027, 921331194, 195559689, 306835883, 272571801,
	136316264, 685977009, 957390890, 320576772, 169520709, 987921345, 957423342, 300443615,
	170299187, 625809087, 917197292, 765257612, 421696309, 634700800, 759197826, 584388112,
	323809443, 947105879, 423981273, 453848606, 29954254, 902300753, 883690662, 576371726,
	471849450, 454523263, 650687806, 456843691, 86318656, 60296783, 414341913, 712261739,
	471967432, 252361515, 585535342, 358915463, 819585010, 971483447, 215215071, 404617543,
	575347258, 695635104, 690170422, 576577850, 406329036, 158735945, 399115630, 758943766,
	71058891, 489660060, 588638456, 791316161, 13155943, 39449925, 109984426, 957552993,
	505276194, 524693279, 465867283, 547312062, 764614408, 242755198, 743279898, 561832423,
	906801156, 632642156, 61305424, 169878024, 848607796, 700659709, 370741909, 624763383,
	636730506, 596536763, 489716308, 579735446, 796001959, 413999954, 913744152, 107590341,
	717114582, 301604576, 746830315, 50198736, 646061306, 714710105, 204206483, 175601554,
	40086858, 363322188, 588215609, 249711248, 16371795, 863388586, 120162072, 312058066,
	201223272, 646440640, 374695584, 301368228, 412929875, 861923004, 172684043, 350052978,
	386228700, 453918457, 825504666, 549553250, 630003718, 673298689, 837598292, 151407320,
	800380384, 245879624, 441587080, 789786575, 789683347, 192728795, 710423720, 91680866,
	789875034, 33945770, 573633262, 558463261, 347757418, 140824500, 788686738, 694546648,
	141834436, 736691281, 404481110, 428699574, 85443301, 134553125, 711160618, 901371032,
	998219457, 386853319, 881480988, 522259253, 722959962, 884010836, 86444421, 179989813,
	272922562, 425633810, 352241800, 73782965, 199385702, 992839898, 597818281, 137931413,
	359035788, 566447788, 708784641, 247556239, 654187711, 198389603, 216389153, 1879167,
	732606601, 976399609, 237650913, 316780674, 414350414, 637874256, 199767034, 775290891,
	843760715, 961642096, 146373644, 668919235, 500157141, 510926384, 234025125, 684134567,
	711476742, 362587500, 944375902, 553502048, 787674044, 79441228, 579055898, 800726911,
	864829665, 157842003, 163811457, 67337474, 691517613, 704887023, 876611440, 807390740,
	753140358, 628708556, 721957942, 955843306, 776496420, 991860291, 682859133, 446048809,
	794240359, 159811254, 982990351, 254982167, 878314210, 501629115, 671655424, 934817646,
	161174412, 375400976, 993669863, 685154032, 352701523, 253889077, 346324922, 772418501,
	241486050, 324979184, 806711973, 441412076, 404049049, 390071380, 773545778, 609542884,
	98805199, 307287358, 568811899, 654569604, 19912251, 986230402, 350916767, 878806466,
	48334220, 118830347, 287776386, 851845179, 983748578, 804662110, 248696978, 396335894,
	913453454, 623496267, 586822146, 127831709, 84171818, 559799407, 177567467, 290878492,
	583177582, 467168573, 204648234, 41568170, 609539176, 562931908, 833124992, 340626044,
	731609607, 847566319, 781869888, 162908757, 594902488, 555978905, 450895710, 802793251,
	714653706, 990401521, 828238873, 619890509, 623389865, 737486935, 348458201, 612643208,
	86443135, 302371977, 996076805, 510711698, 36856577, 616964319, 434016751, 421737105,
	617669563, 186562235, 494736257, 851331814, 717940502, 913297287, 678487841, 515619551,
	688861582, 187871751, 462551951, 160572352, 827210291, 840100433, 921722502, 428787848,
	132782021, 266579620, 340202622, 858370222, 134313932, 611899586, 461657996, 995769871,
	10945009, 855717996, 749788657, 581303741, 769297078, 535666355, 647528287, 362633755,
	779225352, 789856795, 203519189, 407609519, 316528640, 488089564, 941470686, 781045485,
	970176281, 386830765, 687729260, 990944159, 715666366, 417213083, 866062879, 818721088,
	333301287, 17465023, 356528093, 108041659, 550145232, 84627398, 787279748, 281080834,
	718210191, 58563828, 525624345, 186806859, 268076989, 39931496, 816311411, 325133178,
	520569296, 553895806, 274020007, 679202518, 751510268, 531010736, 973283187, 564888308,
	733849884, 516223656, 854303044, 543644367, 85339842, 981110348, 779478311, 919005946,
	508276228, 283810405, 637581648, 545450802, 971540074, 993360051, 927765552, 741087871,
	391112087, 813737631, 3481786, 320962517, 349584625, 357841592, 305186535, 247661446,
	689073648, 425352871, 419777046, 772583713, 297211394, 33495282, 676694069, 185924222,
	330786005, 761422626, 914369409, 533715163, 67347975, 121745321, 886390822, 148409658,
	573645847, 284744880, 660859628, 784290748, 670502143, 285771597, 204310278, 692608318,
	341122102, 192860478, 335525795, 5371615, 678026384, 801659809, 952801614, 748822060,
	200419842, 273450932, 719126471, 347065081, 988273789, 764707195, 152830783, 381355304,
	692638234, 284683007, 945350635, 129193900, 921315494, 470516995, 483856490, 458826846,
	911561316, 145909748, 865582049, 355249971, 506588369, 201706524, 852564738, 351373565,
	629812035, 374758387, 689211577, 131249327, 634681434, 914755301, 493110828, 635982343,
	310562870, 783820949, 932951976, 233423003, 190011866, 638668888, 832014905, 356181904,
	257036686, 773532056, 81543648, 640482829, 3648318, 489927411, 263502036, 638230707,
	204959007, 303990270, 417088373, 71180975, 381038893, 121277520, 272526380, 30801202,
	187580258, 347787744, 563317348, 877349564, 974083740, 368918145, 285668555, 358372696,
	879280837, 523703998, 956682127, 550572250, 271858572, 816724680, 334440591, 589791328,
	905077610, 550773256, 896945703, 38354177, 849749934, 435060122, 722091121, 578860300,
	762843188, 751388045, 303963060, 921297407, 233252890, 300333374, 784005430, 633271012,
	994625274, 790516156, 649401794, 593098109, 55101110, 353863509, 870208183, 2367139,
	103128368, 511251461, 337502306, 896164156, 779665176, 894434711, 51565533, 437323893,
	188817098, 638776591, 867315470, 860323332, 723552512, 591650536, 103129265, 61458985,
	133300147, 904041525, 92876289, 409667283, 687934570, 90976888, 514406651, 2073985,
	156512889, 611143233, 799055931, 428171665, 483511516, 172042071, 70498801, 369698107,
	648946778, 956625642, 531568085, 436822635, 184842145, 939971554, 404996831, 826498291,
	346518628, 606999374, 580038492, 871997187, 905932750, 404411354, 191947830, 750430594,
	287218789, 140584095, 6017625, 735346925, 793415043, 505837941, 486674224, 431568636,
	588851594, 726096077, 825540874, 847180617, 997319716, 354240973, 139866495, 316633224,
	662474952, 66872359, 977453378, 577071894, 484408776, 86217299, 814120053, 677584524,
	717550702, 664428447, 10158310, 7957358, 416213415, 884366808, 190112197, 274820999,
	587555465, 252095, 590855335, 740491757, 601273596, 291583435, 527914141, 491455732,
	869509463, 518792947, 799478722, 615957179, 301956095, 488640974, 876306082, 872841522,
	105622721, 634049930, 773712221, 92044677, 78888265, 533365591, 570523019, 703312972,
	849367587, 384549822, 268932397, 402969729, 924845769, 376965488, 966395226, 560794648,
	648151526, 530190153, 519213343, 156245309, 783909186, 985226580, 281744027, 254080066,
	878040863, 967039161, 312239752, 411120549, 149384802, 409793416, 854073806, 904104835,
	517033362, 117278427, 358078495, 827063762, 673606705, 670320354, 30746921, 386885013,
	237835918, 338823122, 868702747, 355509093, 304263223, 963133030, 332999654, 817270268,
	729251452, 814759121, 820446763, 354734939, 22062064, 576052360, 98733015, 634694308,
	47900642, 1161559, 402414452, 877775822, 390292192, 776558970, 553771385, 221584409,
	850555187, 705825077, 209998762, 63086509, 120604749, 655680422, 169991371, 482082555,
	25430737, 729174234, 184508823, 503228354, 819894104, 823322950, 362067877, 476709973,
	708613432, 69992070, 316412452, 75760785, 702081446, 829834476, 591786552, 206614749,
	765190007, 846693948, 400970560, 661466803, 936176528, 239348348, 366003981, 696124215,
	874408867, 692491453, 671474112, 804004038, 970779453, 603404797, 412597970, 602983891,
	395922176, 881436909, 648783832, 726100087, 139685161, 415495269, 262070767, 198756247,
	345608416, 1373358, 43571866, 699396280, 423209285, 481572020, 823937420, 132778719,
	588739558, 895211895, 675733066, 156652679, 388216764, 318299410, 144446099, 495635707,
	690718720, 727260667, 550317761, 363682697, 23883032, 492780451, 462279967, 655323091,
	615800953, 359495230, 802387903, 941207702, 132984970, 987247633, 273713330, 209116668,
	10813958, 803200041, 947541936, 994333169, 610412181, 679332023, 195823921, 99363800,
	844483385, 94972468, 762164450, 954244159, 38358926, 865597122, 372430715, 543443296,
	42384375, 901562641, 135666523, 409061989, 794444231, 131091247, 570766915, 99744170,
	589229224, 43451333, 243128631, 179388073, 98453969, 661869464, 208030182, 189864605,
	882264058, 534524021, 526173425, 212739071, 947730259, 9590659, 996806673, 105550408,
	592228975, 326235929, 429878951, 401056468, 604767463, 322900863, 191363863, 365902166,
	825490058, 707643997, 393947400, 687008112, 383499205, 975469493, 267996675, 861387786,
	563068539, 374453914, 281938057, 377303185, 104743578, 564607247, 975403579, 747661836,
	252850511, 508218490, 58711001, 22596927, 30765916, 228943471, 948892939, 421599986,
	9622349, 936875283, 358842067, 729290066, 193330712, 134906961, 283932461, 776261507,
	652942840, 306525796, 429702702, 337399619, 158059209, 435453445, 88732226, 738304772,
	980354659, 778842899, 666031451, 9970418, 89541287, 425987139, 377635379, 587999978,
	202604098, 74237979, 269906330, 133934377, 876385878, 376493163, 218122669, 628752953,
	288222851, 387290589, 953505312, 946035415, 23555631, 793137609, 808303049, 638264325,
	277615259, 847455109, 98352242, 83350407, 738285913, 68268267, 400589369, 608489061,
	883929478, 571486524, 389928254, 671327624, 237186106, 277903091, 190718413, 792943970,
	862885671, 400494442, 525033542, 209116213, 528570366, 435351262, 887316461, 612404595,
	46922722, 635316557, 995844931, 265938759, 81299909, 830606028, 60002640, 250219797,
	582470925, 48345535, 743165000, 5744210, 586423203, 657830115, 33752263, 912319018,
	210091097, 708907208, 816981871, 984119246, 570108958, 209814627, 26511145, 553279632,
	190843016, 729478925, 353233655, 968915660, 271252199, 641463711, 522896983, 515322223,
	286722289, 335956543, 389939975, 777264215, 49250589, 370785287, 216939823, 600445726,
	534488148, 344846220, 10876078, 473736834, 733765500, 126473931, 310889509, 136645145,
	416469001, 800677766, 724251841, 121994638, 870369633, 151242137, 702899712, 201940369,
	187675153, 538989636, 270544796, 351144555, 301212699, 234772417, 30590150, 146074201,
	626373849, 396465020, 843382171, 282555942, 236630231, 47006801, 885046326, 73004861,
	911660635, 916993056, 791092570, 733217648, 168249030, 103241849, 893144698, 614462498,
	906705486, 302435702, 809543712, 34011145, 911177002, 919752736, 181099159, 862435196,
	377262012, 269188812, 955488246, 596894384, 595288451, 870301287, 656542935, 806402646,
	584791099, 743525619, 646972367, 882365038, 481330698, 538924367, 161999046, 607070922,
	642854978, 617631923, 551184755, 929981884, 940773934, 556315760, 284683382, 187145070,
	615430403, 24944884, 468636669, 885476992, 607081958, 9608930, 640729060, 204212405,
	359397276, 279388719, 912962422, 203795928, 515383775, 575833370, 293983546, 220399006,
	141145460, 520985362, 893966192, 901825263, 910070872, 176644385, 216525283, 224615750,
	712333871, 837895054, 611549774, 738985890, 63554053, 472751772, 499681328, 301690862,
	663936374, 924270408, 957275862, 565119055, 483776548, 252826, 736538568, 32067421,
	580131409, 993831810, 469708072, 932944995, 209113858, 779815280, 284611973, 51492878,
	313182277, 172401154, 571300661, 261195942, 646193233, 352601011, 210143530, 648884452,
	841639861, 237561836, 152774710, 648528419, 351943052, 957003518, 600823579, 489572482,
	918899061, 236715000, 424355690, 908449805, 913957004, 326806307, 444120247, 121973129,
	925383257, 799156619, 210104057, 34183665, 147224299, 742629522, 443981919, 739986487,
	430909394, 268561102, 828034933, 729815904, 389312124, 14049814, 733317866, 921950125,
	213683380, 249137339, 686119018, 945367059, 485921777, 794102142, 198944166, 386305647,
	366304524, 814963769, 895365244, 350002234, 721085234, 139048815, 421177956, 710202894,
	25291651, 834136291, 143742272, 150376840, 407510568, 567985003, 9841690, 349313788,
	16609803, 258702323, 543596114, 877135990, 366930076, 653525118, 521914877, 172412950,
	974815450, 418490226, 616728483, 238812051, 936227699, 322180144, 786937754, 373150516,
	664816487, 673434402, 252673832, 169738383, 506326976, 583620460, 121966250, 9516481,
	32032244, 474265567, 373371608, 740698412, 553803093, 97480301, 45534212, 523651642,
	435695448, 537883363, 257948599, 187707880, 259675798, 352876128, 744981195, 86049029,
	119030165, 705195683, 114246980, 175888231, 87921688, 678214319, 993682322, 44965183,
	925834328, 601712746, 269673850, 938075687, 992209545, 485255885, 517144816, 155153013,
	443676106, 322910027, 92923697, 975948088, 105844454, 329483996, 684439401, 345810391,
	893959449, 996157977, 558879538, 257432736, 323536275, 854195890, 124212216, 418080919,
	555727293, 64368928, 366836898, 818049645, 975777710, 679670417, 635928967, 955443809,
	493388556, 345330328, 990861699, 624838058, 205204856, 416630611, 556010687, 547484793,
	170519648, 54248438, 521831133, 587915186, 808263046, 956093891, 351353363, 975419472,
	129785820, 701514202, 438962687, 67555944, 8671582, 176021754, 969221027, 147673410,
	171131074, 919118117, 9888441, 830675447, 458099691, 830872501, 80275536, 901994443,
	655240904, 113094060, 913342428, 684394072, 263536838, 38928781, 211180381, 95503259,
	839941962, 414543193, 681020360, 216720552, 311053133, 691717331, 314845345, 866622801,
	559951552, 256935936, 218419341, 211675659, 307994768, 182137759, 766897051, 543008677,
	789829593, 611489239, 709596046, 317196455, 628621191, 925083908, 429523644, 751777751,
	44344525, 537625725, 645955711, 676196564, 888530685, 768977917, 315076144, 342753948,
	140975543, 677434206, 477525776, 558454934, 585681432, 981227516, 89114690, 671958683,
	751666828, 130215942, 277236743, 378486638, 22156213, 143797973, 596178680, 478720901,
	845347712, 578244570, 143976243, 531131318, 826386916, 80867618, 617218532, 705730103,
	643301664, 72323535, 490618841, 480608209, 995262826, 307484496, 395712836, 863526793,
	303299112, 383580707, 464720025, 313377900, 751196781, 400297533, 640546575, 130524332,
	205681915, 154448142, 31245826, 457691580, 955063255, 335781134, 595184324, 381500753,
	530420097, 611732125, 825890601, 995410731, 810220376, 112276680, 57658459, 88931131,
	61779332, 64134718, 140446847, 832252364, 658151904, 462095453, 906020513, 39566265,
	857005350, 419118927, 760752899, 125036158, 350697522, 579054405, 804679202, 134460627,
	381236221, 899520801, 578946967, 201650727, 615676075, 400436794, 106361957, 813060630,
	249174130, 17204172, 669091147, 366649480, 512463417, 869563589, 81145880, 960784702,
	375187308, 661030236, 10561318, 601178441, 82593012, 700080736, 197698374, 430061340,
	224087061, 21581324, 278863048, 340189525, 635741277, 847411037, 289072258, 960314658,
	843944886, 369618522, 358551951, 262099755, 237241121, 699838751, 764411061, 757394014,
	311280308, 222598514, 942844913, 977019319, 445345796, 738394287, 803282920, 136893597,
	745753383, 775169300, 810829141, 186995898, 861494168, 737235606, 122095601, 402132456,
	404814306, 486866267, 709342625, 88252531, 905529148, 229668812, 897023441, 816729084,
	501590017, 845143677, 307029803, 159356072, 630142248, 634825817, 327190707, 501600919,
	567648772, 872727241, 620384878, 810945272, 460655252, 911870220, 556499557, 654750944,
	478984643, 71019046, 240976895, 486586671, 267307083, 358591867, 842741337, 789436280,
	766512373, 193457498, 406922649, 928198464, 273519875, 268435189, 916922648, 748440867,
	721007344, 645508074, 724242555, 808913002, 82590180, 642745144, 513543585, 968744540,
	470895965, 294178732, 486965456, 421366553, 134411390, 2803115, 331442504, 916701715,
	642185573, 789911076, 948060478, 896176530, 836454349, 313735390, 829384754, 802645138,
	294358155, 504995607, 609664360, 839151955, 230649591, 223459805, 718693999, 258087622,
	6325826, 447080054, 225516603, 745060299, 260486897, 63250984, 318917950, 46818132,
	625218604, 289108525, 272451355, 589351733, 602375150, 32097299, 665223231, 840352233,
	440973366, 407094565, 5449128, 518263316, 983519024, 3365226, 568388800, 662176810,
	89534510, 480163784, 881084443, 871543433, 175717034, 423373078, 840081870, 539544178,
	426578535, 27930143, 890736358, 781072916, 895163983, 485852565, 121374756, 125877629,
	513216330, 368571908, 681235598, 869808886, 948466914, 26064928, 381461688, 964588700,
	504580285, 363111074, 671899360, 149797390, 59582953, 937655525, 847377129, 460199577,
	78173719, 399854541, 452575601, 887786293, 609706883, 422925865, 425726930, 343832555,
	921397688, 427758228, 124796245, 687328113, 488260418, 612162359, 711065450, 8013324,
	22818060, 311304900, 689554567, 498246828, 841675053, 860987428, 223568585, 802019154,
	46380787, 74840854, 882125654, 336340744, 400696906, 422275362, 699506687, 263062607,
	254922573, 82996024, 455877916, 467755937, 167322498, 610656711, 134407442, 498556218,
	219822075, 530877181, 943473092, 325700118, 895227561, 113602686, 188574572, 120255533,
	292417477, 23816739, 858914405, 452244323, 82665451, 176254052, 480188735, 279132076,
	971262715, 659018265, 747169437, 10641461, 996596605, 515543991, 779323920, 848573799,
	415060121, 821250891, 654479936, 435182806, 137905974, 101083229, 543306402, 14693365,
	204142616, 592559608, 840938853, 892210123, 417996055, 400961688, 73018069, 408692202,
	208989124, 879804304, 956861261, 984961040, 796639467, 569208598, 799864022, 979146168,
	223412010, 393574163, 811004921, 580774897, 325723275, 992311237, 707912605, 665170116,
	960117615, 968260417, 924527878, 90222180, 769776009, 375954373, 852871432, 383068994,
	211926446, 44534532, 866027004, 826722928, 724436320, 121897207, 388482364, 636882177,
	570018845, 279122524, 365373506, 319700955, 781116388, 431427756, 390825540, 792863112,
	242605137, 716243809, 482658031, 104938506, 45929734, 933447729, 387091315, 591482313,
	237661008, 156316038, 225233736, 613961457, 628001130, 379540975, 555602488, 892395396,
	402297732, 900151166, 719726378, 666139598, 625353752, 100583778, 235100027, 538253886,
	442774488, 982079715, 525591981, 461491175, 955963599, 119574893, 5373994, 997897138,
	42666435, 803115127, 916642513, 258924346, 298443816, 705102524, 171317092, 932773122,
	871349246, 441589434, 551067433, 385720067, 957505197, 71853331, 933485546, 199953526,
	121509689, 837290027, 163568097, 41942690, 867405624, 24512106, 807998548, 758245636,
	161574942, 290046641, 345410734, 321739339, 211074905, 570650491, 230128723, 530143406,
	526209409, 207835554, 895975496, 564804145, 786951251, 900332432, 596956000, 993645113,
	548661451, 332672845, 586357670, 692854130, 896740467, 352376570, 49972536, 368964899,
	300768292, 968666700, 412397325, 559710600, 956908803, 953573140, 189300705, 601741276,
	313471555, 991705692, 650741656, 491830167, 136273101, 359668070, 826275428, 660387881,
	648890548, 708597002, 819221164, 448950011, 51502977, 209004236, 696439660, 704964365,
	448096394, 778635980, 536904165, 240968255, 796638048, 925058535, 52942401, 779932175,
	386377403, 894376139, 33187153, 438534724, 135877873, 238679500, 43090316, 428596127,
	587422360, 419110867, 205512403, 733979933, 180577094, 80121679, 623762983, 553136584,
	123742956, 560260059, 248102215, 257779863, 632187319, 582882602, 466789477, 298834010,
	987939533, 126672505, 65419893, 955220071, 399031560, 290471929, 896987902, 719340771,
	677174902, 675076286, 739860719, 770212259, 79442162, 44839866, 551238310, 73432212,
	254478574, 466558573, 385849783, 450839875, 524682881, 52649427, 608993930, 563157096,
	880694125, 37300999, 4241204, 387461331, 752541416, 232042107, 915437008, 622320530,
	113844945, 382505557, 340417524, 663197716, 451884761, 863109120, 615214437, 403203993,
	277409475, 978278776, 387509325, 357356625, 959577875, 963829928, 141694307, 948468662,
	268886375, 318963768, 175717819, 614269689, 962649934, 635206134, 611100095, 784058896,
	867342717, 114202893, 910661567, 928587175, 367009664, 803749642, 493552291, 208027541,
	927289435, 677603778, 840250512, 653318892, 893032521, 540370462, 90927895, 603662239,
	346247747, 724599232, 168751610, 710139178, 733052357, 754711821, 312372761, 445026292,
	664834607, 612856482, 541824186, 222002046, 392711986, 478282171, 117634114, 467639966,
	805873525, 479580394, 617133604, 42861440, 182568270, 932221815, 518360992, 632710656,
	983476167, 579578884, 42523187, 55295083, 486916555, 638512805, 571007655, 448464228,
	101448001, 528483710, 498799476, 683906543, 555925119, 778027845, 928478322, 249517926,
	390569280, 490944398, 637762081, 615005143, 495998432, 210339736, 52610465, 124606300,
	15766298, 175139216, 950044845, 964236485, 554765205, 497610108, 821791214, 464365790,
	363763327, 535412077, 788192997, 49399374, 41345457, 801746163, 145525483, 494368128,
	853719046, 688554004, 195310140, 899631028, 483469015, 382610654, 620291605, 762432493,
	935767957, 454719046, 904305987, 600387162, 934100671, 231137074, 440361102, 361888552,
	93374833, 455472280, 959790890, 722178385, 661340929, 742359915, 496263129, 206931858,
	159015901, 301565016, 709442799, 400735213, 72235407, 191146851, 954052920, 548242770,
	26402243, 99178182, 937095019, 821832256, 843962633, 938564451, 959646528, 109222995,
	508613041, 722535188, 962203657, 237358302, 715492801, 976246079, 688740314, 2555438,
	44615183, 110161403, 147380067, 948121574, 827748486, 129668468, 700141558, 192657087,
	134148582, 341643746, 21769259, 630082173, 24828957, 451790763, 495842990, 978627698,
	21529066, 285106692, 565227213, 666263937, 101224771, 56126199, 244637848, 713202738,
	127417680, 450108881, 903756967, 265225237, 603761099, 128582071, 197864168, 590549564,
	428540803, 942126235, 627268591, 459052657, 59149335, 40240166, 8090846, 767931205,
	484767855, 232127708, 867169053, 332185089, 525272619, 596068580, 316409397, 522706980,
	488456676, 516749460, 141811150, 111580522, 141940009, 351187522, 305495678, 845567324,
	825835285, 750766628, 30929149, 111750427, 188528483, 387150902, 450804146, 997893847,
	397835929, 840993439, 800441581, 374379393, 954819618, 850335582, 160926881, 274121338,
	43847241, 343697981, 264823033, 779575170, 735214201, 934268528, 119458370, 881840172,
	39052270, 225295231, 858216234, 788036531, 271853725, 616417839, 606867820, 894233162,
	972918293, 807016257, 973682608, 958456794, 592151332, 72273299, 911363366, 586054074,
	191515562, 439149568, 524066489, 198023423, 372508991, 15542389, 850075816, 850568467,
	151969014, 415406228, 943592153, 219407288, 361306852, 557476220, 404238160, 899703897,
	394418889, 397274572, 330160273, 365407153, 232337484, 660005499, 654376364, 766092042,
	768480291, 988022278, 581982350, 426387568, 653139170, 709265730, 626686296, 11537156,
	658960802, 278726755, 452934763, 883390427, 509839391, 7203055, 329976687, 183417436,
	729490470, 21859437, 169917166, 670223275, 642549659, 438788425, 554040441, 198335452,
	967278955, 461851991, 666266224, 706109393, 210217529, 181097523, 381532193, 433675377,
	76727400, 831748900, 73057433, 143503270, 168130142, 359535144, 754257688, 512024931,
	915877528, 797684389, 132522927, 723817862, 658083873, 187361996, 860381383, 546886454,
	384998943, 846223045, 624953387, 786819272, 850224618, 285221707, 178675368, 232571897,
	404250912, 177684761, 820652768, 345403456, 678875925, 253586525, 702283367, 624038453,
	648970509, 169810254, 244028273, 350691123, 296870920, 144037830, 86555995, 253323983,
	502678867, 982689318, 585883162, 992737615, 226590485, 417038850, 69661015, 714481813,
	764966281, 233504444, 66067271, 60303979, 108933312, 486570417, 396367732, 11335639,
	608549742, 499409525, 508346082, 929426627, 627211604, 580395032, 619383188, 67090437,
	391326774, 921440156, 412547977, 940274090, 738372116, 982854856, 896279029, 690217678,
	305263694, 239553846, 289985946, 303404044, 880727406, 812954794, 453448517, 454592047,
	585299643, 526015847, 312178997, 198442331, 758282110, 488570256, 963066407, 768758869,
	810993821, 234898704, 463640359, 657535831, 991333540, 989412425, 518238991, 636225834,
	661473977, 303701806, 375476733, 255952871, 162200715, 807714106, 408924759, 982671897,
	576874665, 332979806, 53671627, 368926781, 249008531, 874490374, 982937984, 662732334,
	530021579, 767941170, 947590633, 883670550, 314334867, 277165222, 853787942, 496769473,
	793271205, 118364992, 377799633, 249790269, 206827519, 903679061, 961862258, 726056337,
	368308424, 305407703, 354166669, 534476680, 134375593, 586640823, 148703782, 616101145,
	193900263, 715179958, 573503502, 850362688, 695651804, 87175316, 814940833, 759130520,
	81083443, 615898944, 263988246, 300504049, 315971253, 965199414, 311478823, 660989217,
	890854771, 563992537, 172272541, 849418366, 726496847, 384206118, 218177227, 181408104,
	981417794, 775177167, 55333122, 105148834, 517181258, 174118723, 628418692, 795897152,
	829097178, 205462149, 922590189, 268072875, 147609679, 943609605, 103589994, 463633448,
	185781362, 761127737, 978296497, 216693434, 918122317, 523977088, 196159202, 763444663,
	753905246, 18936261, 685723283, 819553238, 793466955, 761684109, 480315481, 263003312,
	169555925, 236559528, 817720236, 848373640, 932966226, 828945291, 453484713, 39963591,
	671091681, 804112360, 386695581, 71476220, 587039955, 100408558, 981016053, 721024548,
	934957641, 954852810, 130219362, 785732968, 167995595, 173609138, 326915588, 5181223,
	303291669, 33070262, 621697970, 987069078, 693553743, 183061048, 300132268, 512492471,
	56005264, 602039675, 203405077, 167306466, 220835510, 287632986, 537608411, 527188163,
	345990543, 462714296, 919151817, 77634214, 254881279, 378017625, 617605753, 659400772,
	296483160, 615447274, 909143711, 535771217, 390788135, 974160152, 236612412, 532734455,
	727190138, 808976610, 421672295, 509170119, 809186340, 171529949, 974482823, 618995093,
	853982963, 529112817, 123003566, 632298125, 311053477, 939316818, 970038716, 113167489,
	887340637, 339077967, 41701256, 766817278, 811333631, 759100249, 99296282, 406790691,
	489694611, 650019506, 154136180, 57544733, 989105856, 650522168, 619046249, 460161983,
	699801252, 941161585, 535495755, 253345949, 245704138, 795273212, 818769467, 316473961,
	73207251, 444705661, 591142555, 383548086, 744990327, 995120457, 749539419, 267687044,
	817853929, 674267159, 33449482, 88178162, 970206105, 38707318, 324949513, 115880091,
	20297311, 443022645, 566286375, 935736392, 972536526, 781991597, 273529477, 500267835,
	318143901, 606038362, 655656224, 399833143, 406885391, 111732140, 442973234, 620613190,
	431253211, 385709010, 698412968, 497659504, 136951294, 177022699, 963852472, 912529726,
	758072698, 545608245, 513553649, 748185456, 700951088, 851242066, 149837755, 890080177,
	168162850, 261072434, 301880450, 828514918, 956662150, 848749402, 892533056, 355069958,
	217732101, 347939193, 891649421, 386903531, 272047771, 367245754, 49326232, 584472777,
	36271383, 762510234, 51955009, 623876055, 936579838, 17021840, 173735070, 784036351,
	886257365, 960778336, 782733883, 5855670, 165721220, 769202511, 626248409, 792407392,
	689526671, 793054858, 237780959, 802025043, 693505641, 94243071, 114624291, 451049479,
	732147681, 74406138, 178534591, 58955895, 166834493, 212428596, 411363064, 209757472,
	397669110, 520595277, 489389390, 439272967, 437985565, 986094548, 35160250, 462709175,
	915385579, 346029109, 320547754, 46248187, 451501648, 29265074, 964987683, 996833073,
	705876730, 858860889, 797572765, 437029076, 230861939, 892465106, 54409056, 687539042,
	217589530, 67224898, 431096649, 103677837, 348872009, 186479138, 270769921, 635602210,
	785504919, 925511318, 363654918, 755451234, 43138827, 268153852, 143711660, 676982240,
	93502839, 788821164, 991463120, 397059308, 50686300, 558627581, 276052810, 565320862,
	764896820, 344799755, 379151277, 72099445, 955030381, 423497557, 283400435, 228681752,
	624456764, 235013116, 918612411, 994302321, 451631618, 632766449, 500602634, 426424422,
	936514026, 254497419, 263615428, 777205611, 805895652, 835704358, 773896852, 396530490,
	753164564, 431486303, 328086395, 358564303, 488389505, 378212448, 672508931, 335289705,
	350141918, 554535244, 16276984, 71524998, 801916116, 815415756, 733876686, 863473896,
	491635456, 18893115, 615500383, 865343804, 533274256, 684527671, 427376717, 163169213,
	784778738, 338404090, 543800387, 675669934, 733396643, 534463422, 464312520, 366630825,
	876948479, 666757294, 290031937, 416995670, 709664044, 234019718, 38243537, 866208916,
	682324919, 366019444, 884501415, 906957965, 427394744, 320716411, 504778819, 881306960,
	717559090, 787150642, 469190550, 726142212, 572610372, 380299316, 442799822, 237822115,
	140913543, 935520638, 541938733, 106282478, 167930905, 986433089, 745564115, 820331494,
	274973419, 138698429, 60814964, 912206998, 737012109, 713225042, 597554568, 907247465,
	862125900, 791543168, 248445145, 382050301, 108128824, 885751013, 322102730, 424571826,
	250042496, 910944656, 349209784, 737814774, 95308935, 536416173, 752259770, 709763050,
	723248565, 760000144, 339223, 174867438, 255280832, 758790139, 707700636, 388572984,
	457506007, 735823217, 952340740, 699509826, 931867561, 373556201, 309601112, 364325438,
	369074340, 180829504, 188580610, 480218435, 485343417, 152931025, 587435479, 938175027,
	607453676, 317222380, 861102801, 522808373, 816528107, 693735038, 131883412, 867238475,
	146936534, 227848121, 872256089, 674723753, 766643876, 389700154, 253961334, 991448206,
	77360696, 967808500, 676780461, 406437867, 427778889, 988977497, 69000965, 467488285,
	226913694, 195017453, 266939915, 483217810, 803622746, 930846290, 98806157, 930615788,
	27057800, 717012820, 513083119, 203658322, 111326031, 323694190, 176443609, 225376470,
	277886748, 996725251, 561921715, 342058935, 351571679, 303927507, 181602626, 18505928,
	248733668, 534186549, 368772479, 983782113, 297737758, 680605052, 288018522, 908592414,
	856792647, 16545829, 73523590, 102541368, 996477643, 442102884, 747073814, 329019805,
	137230530, 692229152, 310541412, 88985176, 301443075, 481806683, 626242706, 173481792,
	13654547, 973226019, 734916815, 261632195, 713010557, 664440318, 671217984, 107196245,
	432187529, 278857277, 152824412, 394589142, 824839516, 47108027, 658561666, 30818990,
	141461269, 827830467, 969881584, 901561280, 175487578, 538629442, 424776626, 443365470,
	783279345, 432854710, 415379714, 691636551, 495297391, 846190570, 962236694, 760380538,
	255233971, 145435882, 124548730, 357454177, 127387836, 674629142, 229648463, 497510901,
	990009015, 711913043, 278312653, 178853857, 903783784, 972703349, 298744432, 984570280,
	979535193, 275255855, 622694973, 442176177, 459456823, 133891728, 181263169, 408565261,
	475293423, 951100296, 134729662, 881484774, 93437564, 62590710, 450065901, 107383733,
	747662027, 246867463, 478224719, 944122971, 881168664, 974417739, 577295727, 703902679,
	860605604, 78773219, 177802756, 709580892, 483440584, 738617728, 67535019, 614813097,
	452683681, 32471816, 881687843, 683825313, 51729660, 93064346, 665388422, 174412510,
	368003628, 60391272, 844390299, 413495245, 440418727, 183866025, 107111085, 558251883,
	338311679, 508173792, 628872050, 737944166, 146350375, 679882550, 546798145, 192409444,
	976050233, 919193536, 278254866, 689047905, 815476895, 263737137, 952578968, 968455573,
	399620140, 768603926, 419574368, 574866439, 701420711, 129892916, 305779220, 563197579,
	761789224, 380294467, 130174095, 863487955, 86260056, 670743308, 978004848, 611771005,
	306913085, 589926312, 777378866, 657202151, 811279675, 504581471, 89105681, 344413261,
	52373983, 482643608, 12133159, 739173400, 496432557, 122192339, 44272905, 829017987,
	817524367, 194669272, 256810485, 401367005, 449804001, 932025727, 56762362, 920832508,
	2819696, 882029901, 223098239, 142964406, 284754994, 231621173, 368885033, 456536619,
	333578440, 277171621, 767035122, 710179539, 26201407, 525893387, 353712223, 325739180,
	804680317, 721756953, 80243350, 532384846, 482993187, 84439659, 282031363, 556748833,
	943193170, 502602406, 715878297, 26340185, 141076312, 380828624, 961826087, 262176173,
	981403057, 841216939, 813487023, 272019549, 740661544, 331755880, 599017294, 210158296,
	387930488, 158877662, 965564030, 268452551, 386708723, 412906079, 426722714, 390394182,
	234657474, 411878651, 44547793, 595194965, 694578077, 58431178, 730534774, 770995712,
	964713035, 108601928, 33341317, 940652987, 480301700, 144132033, 483873087, 569143126,
	797883336, 412407247, 891622355, 74284551, 721185685, 637389654, 38913433, 351696511,
	554372227, 164440290, 554732278, 829638374, 256642317, 513144428, 566342607, 389579424,
	376136740, 269959431, 92753364, 807466689, 365968664, 816804032, 49412179, 509824961,
	524201507, 659783650, 833196753, 631728878, 396836316, 180576798, 80487935, 559327148,
	677458619, 584572570, 574731169, 599179277, 937675525, 709291664, 814478186, 604676153,
	267870305, 691651758, 908450309, 435369952, 410676189, 269861106, 40704419, 53229721,
	565356831, 127477753, 220767320, 725473988, 328872012, 597426442, 262403819, 963888755,
	698863503, 498490659, 44904860, 213254369, 84240259, 636061783, 110113018, 599181259,
	211579328, 279641527, 960732376, 548527430, 696347550, 898447414, 329648467, 177376885,
	695139108, 676634913, 439140671, 142268607, 127094520, 643373793, 677516954, 30692385,
	992469406, 384260837, 141716326, 587343613, 590446356, 212805949, 683316459, 677879278,
	399857384, 291485366, 880602865, 21391948, 263720567, 289077696, 619351894, 260246944,
	957333193, 610919423, 771908483, 516257758, 273072671, 897097892, 127536979, 979306051,
	830659092, 815290642, 768987037, 242539962, 588404014, 403413789, 531388102, 826954570,
	92904365, 948737062, 200844602, 833129086, 927257502, 27367077, 952951584, 771109120,
	479624682, 170561820, 734485512, 341471683, 306310209, 75676449, 997433820, 877617605,
	36020668, 714617161, 28683458, 136908199, 600867306, 665092161, 856358139, 600751120,
	594238820, 571161246, 424560051, 304889557, 359100425, 597547503, 295173970, 227644685,
	138842663, 853199811, 60799155, 608611403, 153925116, 95504298, 387752345, 84212050,
	768224890, 547004178, 806782587, 562951895, 937798634, 265173471, 93149909, 585637704,
	511727321, 847430113, 970944146, 901835268, 383906845, 539556076, 16957041, 71622098,
	956955770, 492585152, 618723966, 295901203, 284473409, 217675767, 773000628, 544198627,
	972529536, 618836013, 634603322, 372384162, 881713173, 857260428, 771816239, 940663254,
	940576967, 680839877, 838911740, 902942668, 462665349, 406968446, 220382554, 328915968,
	111307793, 644300861, 887942066, 550146868, 895425628, 915286166, 130547092, 912699726,
	920740072, 534438585, 630758117, 170250019, 345582741, 287857874, 694022242, 725461204,
	413313981, 274108178, 806803053, 889883436, 935435380, 266847682, 800268641, 149140934,
	282055556, 994556569, 911815659, 851698618, 296095090, 38660900, 925982096, 682869101,
	654248624, 265993394, 692853860, 461793438, 130652410, 551738437, 876422719, 202210817,
	621677930, 903251215, 990030573, 446343616, 90058859, 934278189, 664672819, 946351126,
	10761166, 958286315, 95873547, 280076406, 918796704, 298971867, 61324402, 838473696,
	847367415, 850597435, 257273001, 924723953, 47248654, 473781526, 163351695, 344375475,
	645913750, 772906850, 702485418, 444382261, 112552374, 429311168, 572960837, 854978193,
	619094041, 97466866, 613333590, 882242577, 487637690, 513781638, 116733842, 360859949,
	384856535, 524339337, 448884626, 373785157, 235384626, 461484327, 908465005, 727209255,
	432519599, 981675332, 830119211, 663178614, 995077048, 538448186, 307111427, 478866807,
	155593252, 155417366, 965081013, 307740714, 700159500, 736010749, 915220614, 324994850,
	192780811, 788330294, 634499822, 777925553, 308503055, 859956112, 282556347, 289553064,
	133464975, 286574560, 419790311, 573655750, 837246751, 882693105, 567950154, 841342314,
	912052381, 581106242, 752778131, 88992064, 461693853, 831744318, 484267699, 384651099,
	498727223, 334853810, 609448478, 653685985, 591892694, 464554688, 831681394, 946099649,
	263304046, 190202078, 51501261, 995199216, 970469102, 148832258, 819657598, 882856354,
	313232110, 598234630, 240953582, 10701083, 28467056, 997506509, 839956292, 514485419,
	114280963, 444689820, 616773992, 520196339, 288048289, 373299619, 686980776, 175676535,
	774928015, 577362571, 752385811, 687587022, 696507462, 167826208, 217460417, 216408265,
	307107320, 825943978, 296393598, 906640738, 763260213, 62357387, 485661150, 457711108,
	687972760, 14772611, 21871790, 183854216, 502567950, 402700534, 187857952, 693437156,
	956809356, 143598876, 13593384, 754836881, 4139979, 781445846, 987106333, 209057822,
	530899061, 480936573, 847071517, 864772901, 448163490, 275127542, 839525513, 627741739,
	118706101, 588286410, 187996740, 527364220, 744991755, 797295030, 952424956, 369602281,
	283048043, 629966878, 228439506, 851456825, 475626658, 97962618, 430987909, 246918851,
	836710721, 550057187, 887916535, 731200664, 995824078, 98814699, 503581104, 512801825,
	27414613, 713617176, 147486393, 254995975, 670401397, 303496760, 238083502, 885725633,
	356893069, 869117016, 89333279, 447162511, 192112466, 61261459, 806653265, 452132383,
	284380955, 267561296, 954632744, 882967561, 580098544, 641343208, 759042331, 575460232,
	427113038, 457429676, 758637695, 326872410, 630617327, 876373728, 150898227, 262718854,
	924007343, 609084038, 594641040, 464852259, 42924151, 515486092, 66151784, 728730439,
	55360495, 523292123, 253902149, 429584489, 598583578, 840974457, 313280591, 107622178,
	801099053, 447926382, 440749862, 113293183, 864267624, 149591882, 825560104, 758947796,
	892694364, 408581664, 69945215, 862722883, 603799258, 579192924, 882741269, 760944149,
	996385547, 50200659, 326117340, 415313694, 342534791, 638293457, 963025744, 253648248,
	443807400, 92747360, 697580792, 200826164, 818136461, 499864863, 314269559, 680024613,
	969517280, 375830268, 123665830, 963757269, 674069114, 305116577, 921779674, 220556121,
	568616581, 492987124, 164412329, 156488011, 924856566, 529175712, 461467891, 694994679,
	200102422, 509468850, 526937105, 137323455, 795862109, 431098184, 209457798, 206446371,
	130165565, 395591260, 950880667, 650679027, 678848212, 291827097, 641544883, 263640285,
	172024307, 597379991, 609644004, 845523304, 765370805, 664328725, 156376287, 57553637,
	732273554, 739355275, 839614386, 86141846, 143780764, 468391827, 450174128, 458466154,
	616729845, 118803017, 60181672, 602697403, 941326279, 380187975, 903331649, 29082773,
	778059496, 686077168, 832579920, 950238100, 354813587, 434804423, 2937538, 862067507,
	840715297, 889982117, 630223595, 49755994, 271433412, 471121199, 582208290, 27901482,
	95936679, 584282878, 615402135, 607264137, 213873695, 177911413, 136788540, 508204739,
	818537445, 31520509, 559866101, 793617562, 905760346, 154732487, 58030481, 976514095,
	629634134, 594307534, 730176914, 391374466, 88990274, 711072158, 904466534, 305837262,
	399669166, 243204500, 688025266, 625240404, 460020228, 688530626, 50744655, 56146488,
	383940143, 605265040, 279953053, 813384630, 526055410, 878230984, 475917059, 627248798,
	36144485, 257117119, 475270891, 707366985, 474473468, 119828861, 4308236, 836904716,
	474733431, 554226331, 660154721, 962634892, 894719961, 584688343, 88593866, 597830955,
	362167880, 816599645, 229348776, 875819863, 979988557, 410218666, 309395394, 487179059,
	271200931, 218352827, 153340489, 438382648, 23769561, 99567676, 665188966, 3477285,
	551448064, 162559374, 409772649, 645264624, 792763016, 708144434, 388429934, 510662414,
	253893765, 866526006, 778471126, 681008148, 890884654, 414001359, 537511961, 327351687,
	469648600, 134944666, 53151854, 394177763, 438150503, 925303660, 815328453, 339932072,
	65679204, 526093324, 870298606, 382026434, 310756516, 993060811, 355928564, 411954673,
	536176425, 513858819, 567063613, 787374638, 781854274, 627726601, 533071673, 76671250,
	670721645, 100086501, 594578302, 146631750, 136406792, 619430020, 827946214, 911004685,
	756255774, 229859904, 867819493, 545693194, 702647622, 302572523, 968777034, 373613327,
	268831988, 839708102, 316245590, 254859914, 156250493, 358100802, 820869463, 11367460,
	226147145, 675822667, 93279279, 941891742, 425883340, 854717821, 616167360, 601418547,
	225698685, 816015484, 170765262, 112400358, 442478235, 909390820, 950968790, 25568010,
	832571944, 343734137, 961783116, 710686017, 168121229, 881996617, 976158772, 83606315,
	424701963, 158003576, 52529229, 798549172, 191107667, 497524016, 64421938, 890840211,
	680657599, 938490011, 65152208, 183288171, 731256495, 763125321, 553118576, 641138937,
	654858732, 312755629, 267105139, 308717400, 521275493, 641967063, 209671063, 617211011,
	812876471, 483485145, 445461366, 387189056, 375794900, 298913456, 676938345, 125616846,
	405695790, 554112184, 957122569, 623202414, 300829500, 275141882, 742092935, 742228930,
	22661905, 411711865, 337785566, 369516359, 715046787, 782086247, 866173404, 645113220,
	894299102, 222236007, 133182293, 57923987, 669995671, 26492240, 664021636, 700143838,
	512055803, 705322657, 703708924, 914959130, 14286735, 358185333, 992205836, 816210144,
	797306377, 455198017, 851541861, 721614815, 872601574, 634328472, 537872105, 76982003,
	340407524, 182127414, 789661882, 280477220, 208951037, 210145645, 849304323, 791601503,
	464723449, 502665900, 634988327, 483105498, 41236786, 418439596, 803806203, 249314171,
	312092644, 630907237, 963929187, 919228927, 152341138, 630465863, 566954511, 452899508,
	647679843, 294469349, 257498914, 82084657, 355727184, 151082972, 884755357, 72192690,
	701459840, 90279522, 800050019, 927609224, 680569219, 466545745, 786822994, 666103007,
	730366154, 181155802, 554309316, 853562214, 215118045, 373678072, 208967870, 794569873,
	128884610, 152261438, 648530581, 220915741, 524978640, 275767214, 34591882, 681322867,
	956550665, 212505947, 448040265, 943146049, 718934652, 795957558, 557267565, 892386655,
	115387081, 992767572, 552501861, 438426403, 717552623, 13083063, 894278655, 867021160,
	898568348, 767053460, 345710644, 834269813, 547967871, 750377943, 952500055, 849257702,
	760404728, 886963129, 849594653, 893230059, 164322239, 647997908, 446312916, 374658082,
	313188681, 715039466, 276145179, 938904658, 580048184, 30157066, 467925771, 696723687,
	628077606, 756581507, 767418868, 856495744, 572392640, 840827703, 662349962, 949258128,
	661403769, 660714677, 338974405, 777936292, 276599586, 25474067, 986527156, 143371776,
	135839439, 661956160, 603679440, 650725528, 58673082, 699053359, 488380679, 354209523,
	346715295, 594743958, 585389015, 306762974, 380410122, 190278103, 964340394, 605335086,
	935293100, 534983748, 257288911, 330243695, 419990003, 602830972, 393470932, 494985451,
	358990430, 337262370, 889688088, 439581366, 102601140, 530406491, 116611270, 366160007,
	118935526, 767169603, 428747305, 523087006, 716546674, 309050017, 914545191, 675464455,
	868898456, 333205227, 489449738, 109048789, 99081727, 174308354, 504967377, 464217462,
	288517200, 181779875, 988319908, 561089416, 318412187, 215872243, 362504646, 472721474,
	719464962, 477349777, 990630256, 651190367, 424939260, 165325567, 294672467, 881299773,
	529148987, 355297352, 384677315, 822573479, 36561845, 156468274, 774335115, 919979815,
	978551995, 156018548, 269082439, 35046526, 55249595, 37554358, 275571095, 80749464,
	684359637, 378024806, 741413732, 555704076, 548023066, 603691213, 880095976, 725044561,
	772931269, 227865655, 817742592, 995560324, 74586056, 990230865, 446627053, 230532595,
	767279456, 669590992, 482986124, 270074213, 731368362, 652872465, 926395294, 548430543,
	255694712, 564590431, 146871508, 375870445, 139093101, 439524848, 148610958, 453980055,
	144400386, 112669295, 40806663, 801778765, 888550566, 859207654, 502023269, 698178252,
	379904456, 889181161, 577021040, 392834349, 748651399, 725852632, 120479796, 313790159,
	664332769, 903901988, 644733362, 87752044, 165838210, 138812774, 199021725, 493527338,
	393101377, 273852231, 505547866, 948401662, 612187562, 789070639, 518486278, 680558867,
	918401326, 642715232, 186032087, 917514747, 376192660, 975597050, 63651958, 557186115,
	130818973, 372754518, 37038002, 667313258, 128138035, 651745567, 535303140, 496834312,
	158274086, 291217363, 338949204, 926027858, 35829377, 886567721, 662912695, 140159061,
	810783770, 784154993, 612781385, 586453008, 321566673, 67866809, 53722726, 483300168,
	168848609, 771157852, 122197566, 300173918, 701358060, 66507586, 318641952, 567431391,
	78951115, 104636112, 11063016, 759172394, 347396672, 298787268, 169676571, 126822269,
	518233869, 143644942, 902413876, 393899400, 51370791, 662143523, 952620023, 533838375,
	608848341, 749595294, 488852267, 791482732, 482359836, 30693895, 87880516, 301361322,
	975538056, 902722859, 393749008, 758297558, 909942792, 522327349, 687295087, 848477072,
	941552927, 310820589, 268023350, 793809121, 178276247, 288652177, 99576462, 967114461,
	559114882, 781171679, 544471795, 571382899, 34839434, 101550509, 321748645, 256593492,
	523163696, 372835245, 386447273, 580528909, 498553610, 27758310, 96101640, 399935544,
	514284357, 160472433, 324304458, 742777021, 46457126, 474369544, 757593682, 885195812,
	581658405, 543787386, 95318389, 92767332, 165303498, 217198150, 603476799, 449876610,
	214114284, 908772698, 831445567, 146185538, 178027082, 819455106, 109497552, 232676844,
	188869913, 113280767, 247579332, 960201648, 523208876, 823224727, 104113705, 978405523,
	402502291, 832718614, 808270329, 981208073, 812113823, 474988141, 510677071, 443246391,
	161971620, 243954498, 382541677, 969785887, 860179261, 916652186, 85625861, 373695965,
	343066113, 302263227, 37832980, 571783822, 337752327, 978012108, 319198230, 258048860,
	114600913, 41646860, 896173947, 976441998, 242738280, 28911148, 164915740, 45043567,
	874761806, 127942195, 6291984, 523280182, 465795736, 843416619, 80707865, 453799201,
	300038465, 206788453, 168787861, 646360013, 506317949, 343870356, 905767461, 929783356,
	534034079, 264630351, 706209305, 938128088, 586702934, 317417515, 829680496, 550386702,
	126906968, 334816838, 8780426, 240751545, 60553699, 238906388, 738895379, 625202323,
	687915063, 171853040, 567274825, 935968684, 683234572, 187291645, 92842572, 733532032,
	572973411, 843011533, 713140208, 289878288, 238271800, 127637855, 840633119, 127500860,
	202244718, 496344472, 235091060, 722971280, 990119503, 803710793, 698688280, 428620405,
	118017645, 840274672, 704019293, 482706656, 593595440, 148988124, 494874391, 590821508,
	113506088, 141106553, 75372062, 836848615, 490549319, 441331075, 947464900, 285932621,
	806069307, 106331520, 806017849, 846321655, 491837224, 735986954, 336926573, 18066769,
	407478911, 914790449, 895378299, 786897976, 986799177, 456538365, 197156306, 568896763,
	430432761, 130424513, 438164261, 442220366, 89911032, 170967632, 617133682, 671893809,
	198557209, 156415781, 922849878, 512594907, 183912038, 126683355, 787563247, 309569554,
	310699012, 91390389, 997421497, 285624814, 317282634, 621838568, 402756296, 739491863,
	583752414, 86707410, 728234874, 361671970, 671377082, 797003279, 967548335, 42223338,
	989119052, 176260512, 864587598, 331190326, 114356924, 870118114, 469643917, 899924742,
	170869979, 340136477, 448427512, 683782461, 70375110, 980210877, 477987780, 357035688,
	282768145, 140786465, 363258056, 730584277, 314830265, 678601890, 467749245, 215798324,
	689240962, 466565717, 867107891, 113416041, 318909893, 315432975, 499906060, 719717535,
	557792692, 937492378, 245785989, 910907492, 180620399, 295770259, 199831704, 84117052,
	520496, 696610, 559129733, 962101351, 38375957, 418598370, 574212452, 540294591,
	611036992, 309486951, 816278375, 877880299, 606572962, 666867876, 643902782, 68414168,
	867352316, 961318584, 951776337, 659249836, 20834421, 163861683, 943125663, 779998218,
	427168405, 812148258, 284192684, 49724673, 340977919, 931600400, 38150001, 903122008,
	470967758, 470346867, 187984196, 824133715, 438659462, 142497505, 659926559, 617652309,
	84497995, 267866616, 179620369, 830210215, 384935254, 864916602, 197867447, 206830499,
	362339144, 665437309, 339292370, 320078343, 477859306, 129795086, 210852970, 396457373,
	529589599, 791874813, 192035288, 755759506, 676111371, 777912702, 273946275, 560840496,
	178093068, 972489426, 24184279, 809545984, 385815295, 187373111, 669524449, 488997113,
	967936672, 134613781, 850763342, 287672204, 732968773, 143597418, 238691365, 83470682,
	48127641, 18803271, 313715641, 430468214, 753373872, 60590854, 419575241, 751236546,
	416953197, 322973805, 928446980, 98686465, 573707706, 351789321, 68916093, 121443952,
	487872079, 69256417, 217403656, 131885938, 70351856, 215820009, 163095224, 224228388,
	549641787, 230412681, 436487643, 438152557, 470891780, 658068640, 127263213, 580842793,
	90823478, 758464011, 549711301, 332613585, 800759021, 621646266, 984272586, 483457920,
	787274930, 519503618, 447528295, 72820830, 963499121, 910353067, 850590318, 602502110,
	762884497, 868956789, 795306170, 742589420, 997754206, 225431512, 450899213, 247952944,
	514952744, 223742450, 695432750, 929224373, 612930036, 30923014, 822439724, 26444975,
	792745889, 396598380, 809419456, 412626396, 718799776, 11290524, 763733057, 762855547,
	646568513, 810391379, 626010003, 73149237, 900035848, 893117777, 158703160, 889395111,
	444855792, 581274755, 281316260, 523026100, 131701923, 851873117, 883393711, 540877492,
	39329263, 67153754, 286028852, 213837079, 241435535, 48403916, 671140661, 249167656,
	292592724, 839996542, 437462658, 922816928, 52254561, 414806043, 567227364, 691341098,
	765390776, 340954674, 475035128, 118507122, 818766452, 52484673, 781793367, 919971744,
	344117871, 636347787, 211270177, 187890260, 610919094, 991506578, 318977856, 538341530,
	831388678, 393662124, 37428061, 32185057, 996946610, 115036295, 467946262, 447828010,
	477074923, 113799862, 122631803, 211549593, 717956256, 652894686, 207770288, 553391170,
	299074396, 654318123, 495903023, 352573966, 272619052, 378241193, 209933645, 236961363,
	339672482, 14731112, 640265442, 279063460, 443193508, 83158751, 245536649, 615287059,
	102522509, 25441665, 139986581, 685480408, 668807834, 940712975, 817821790, 515659237,
	193021782, 522551879, 709872392, 977780369, 652797926, 853629966, 536472853, 780464361,
	886062498, 528906689, 729557891, 776593341, 948395787, 530936886, 536043741, 906927473,
	424023646, 961411788, 131939207, 820167330, 270289269, 51879415, 208726622, 480638718,
	598990751, 356199740, 990106784, 164602479, 638714896, 780673698, 618339461, 742883843,
	195844986, 961044950, 209731100, 726989503, 367176870, 387210681, 417175358, 334373348,
	553048069, 461607653, 875283526, 243916722, 231839570, 252832839, 449547336, 802518178,
	889010831, 109628954, 528054877, 152883121, 829870043, 515628915, 132372528, 698870391,
	305737423, 157963953, 818619194, 681249788, 65348028, 552820885, 737979089, 924083707,
	804435064, 620815075, 442513925, 382523362, 612892747, 952543757, 293796623, 188301744,
	388746841, 686720880, 752232195, 923430865, 586119085, 410342816, 980209611, 828729797,
	239933885, 976955484, 408670960, 843622187, 374690311, 186067835, 282412062, 205242468,
	13007805, 679440966, 679623375, 2104694, 927380044, 511533804, 164441207, 164554700,
	921547626, 514820323, 773576888, 790190002, 821663766, 662803849, 365854128, 471600789,
	3445560, 135680622, 708385303, 679656543, 577844065, 12900848, 575046491, 420556616,
	706464223, 423846189, 793765981, 658997234, 913254119, 196332561, 478690736, 705479279,
	568306294, 526101193, 259524773, 910561891, 286992084, 229544770, 155720963, 158297901,
	867842344, 763572490, 907753328, 63355027, 367545817, 759408846, 722407153, 571560812,
	109543305, 912495624, 701393592, 27671698, 70761010, 831927552, 124495962, 13644337,
	374948441, 172505158, 632480718, 580169933, 518992223, 44488419, 934739007, 142658198,
	847740132, 626450818, 153347868, 959285225, 65107484, 521501741, 749292818, 612214829,
	236393627, 814573532, 689970480, 520460281, 880289547, 336609130, 114110144, 622652453,
	746222360, 339583376, 651654992, 646891693, 354305594, 870609731, 994865682, 336106878,
	310901063, 152946199, 258823090, 641608535, 336746533, 730199919, 178287809, 950014683,
	454654676, 39211508, 885471155, 103672965, 872295277, 220623009, 76044799, 63143857,
	530988175, 967411062, 412621756, 78944109, 56618462, 891906407, 524240001, 170572378,
	748993028, 485529948, 285102566, 514222090, 939286435, 42256593, 828773125, 574126397,
	649202081, 308260051, 350528109, 266328471, 601395549, 60647686, 820555618, 466171988,
	222910140, 306618681, 593277046, 865301177, 484707972, 973334913, 416776152, 241842137,
	706633266, 889607819, 871596416, 357835194, 175868656, 587198486, 281209271, 914313375,
	861308982, 660967472, 761612963, 169076630, 173644363, 357011398, 348056420, 408288762,
	412887255, 989078166, 947154708, 70622238, 19898343, 38180666, 783791650, 826634490,
	390243513, 835878594, 245229167, 413782723, 669618344, 910914916, 231159958, 764241178,
	255492249, 82646181, 467273209, 193207182, 814642583, 740251362, 795632072, 846314824,
	692742883, 630144751, 594244991, 42023006, 872004480, 683530883, 321922588, 528632019,
	323548426, 434041584, 185501418, 924579235, 915384206, 687687326, 94275396, 428382111,
	789475199, 570238091, 573925929, 463542146, 269603965, 146516994, 288758655, 497469096,
	844533745, 111097346, 512691471, 144083209, 322759099, 11218755, 46203478, 880407386,
	153430402, 573107151, 220503857, 383228181, 233756449, 164039470, 917081072, 422350550,
	709519864, 807802470, 417515516, 654609528, 629388591, 608717269, 496494415, 187339384,
	299806798, 845447142, 164208931, 196418706, 554718873, 111809882, 585555693, 990314903,
	941757692, 893416215, 652312109, 982998955, 21300725, 676270711, 163796250, 776699221,
	913070840, 583021320, 589977728, 385803434, 221398264, 387996039, 548549997, 307535381,
	32254715, 996909333, 780281813, 680266989, 348288127, 353357709, 294910372, 506555263,
	881332402, 622527739, 809725160, 719541181, 713425327, 788128890, 209099707, 816564839,
	350635213, 967429381, 648799, 274998976, 347411955, 822003648, 249306691, 755925877,
	245792511, 19734639, 696158373, 886523921, 655585688, 385165823, 289121128, 987600392,
	910868175, 647145628, 939770645, 154308237, 593851498, 375198660, 177151371, 339795559,
	618823409, 444229371, 247036095, 946853800, 318541799, 613436195, 280708392, 456964859,
	886402664, 787123481, 970802753, 260161377, 983180111, 891010115, 115993034, 969301189,
	1817990, 856181191, 277956092, 364372443, 304806958, 348347898, 47630883, 201778716,
	147207621, 915742414, 975672226, 798696192, 831027188, 851687685, 605078880, 555718829,
	897836424, 859574325, 861167689, 45581094, 395400016, 484577947, 736774190, 424819842,
	14796824, 525441880, 646600516, 552493275, 382214240, 441017413, 828658831, 840385241,
	726794141, 967935499, 612267760, 538491621, 163934387, 674962984, 85583514, 334770990,
	755013761, 925280314, 717189299, 384914089, 229574448, 173698527, 212659000, 875214299,
	700802042, 473274981, 830738894, 741032659, 511955257, 895226916, 122034906, 727633950,
	947079067, 18535430, 376070268, 198296465, 622742978, 210900627, 293679384, 295415202,
	472214481, 146736694, 787223194, 590183478, 951581385, 504160750, 723851237, 792250607,
	634540646, 579773498, 423375412, 64056270, 444924986, 833992053, 127090916, 622019589,
	97004031, 517901912, 973912185, 864514128, 668261769, 589191658, 830609319, 653062811,
	173833665, 839276130, 372133159, 109489226, 49896487, 924957598, 563590763, 132644452,
	479899815, 898084657, 715249962, 800755701, 830536742, 716923450, 111628586, 947272574,
	855776113, 391126164, 911426701, 960408782, 765752029, 1126491, 198548427, 790013314,
	573979309, 163766298, 504619548, 198927770, 571935801, 97627132, 306419172, 191611424,
	640907262, 766407738, 764826987, 692582009, 326735862, 702095521, 493290839, 763241589,
	752576644, 782094579, 353525687, 629499788, 389340540, 819249080, 102136836, 352271861,
	563903639, 44170552, 877042930, 102045015, 600410311, 409400392, 986871936, 63506454,
	374801082, 877537640, 117233372, 781265436, 251978995, 46543742, 330090948, 68029215,
	800048756, 208120845, 879416893, 308224414, 154579954, 103612490, 58396424, 124565007,
	599964908, 783195259, 523397537, 626788115, 960467729, 306047300, 913638305, 576815042,
	233538179, 563772054, 963850055, 760697207, 349833881, 843122035, 268056648, 317535828,
	894966385, 47817794, 110636193, 877927996, 801995175, 689724033, 594119590, 553808058,
	599282581, 488140845, 587809146, 395749058, 579856444, 315499229, 130116274, 20433587,
	178103304, 540345373, 114152913, 397817670, 612648811, 230822044, 778704721, 102944941,
	217999064, 423749109, 467694267, 264411128, 116133927, 375895772, 597241395, 962131803,
	12240556, 918626894, 94401702, 330228812, 448127947, 929774174, 282123791, 72550388,
	167672022, 150951928, 153343640, 721705599, 805408584, 825490272, 313279953, 478041831,
	393873628, 815893545, 445667578, 356945149, 4574661, 482613975, 78689426, 761339080,
	320992898, 712545042, 949532911, 24903702, 282743564, 706550116, 410243834, 71315983,
	855241924, 127809916, 389291664, 209386517, 463555370, 182443263, 557918332, 813775159,
	370392155, 515979461, 339670046, 722583910, 652606562, 466758858, 844107241, 489983613,
	305678131, 509613613, 199630495, 453813346, 434688034, 943108584, 737372964, 688378246,
	959743276, 952432560, 82192214, 682069778, 238554106, 859252852, 330459646, 520817769,
	971858774, 332821530, 62935627, 681985837, 265795976, 769522712, 198417427, 129489025,
	225135214, 81291801, 280643050, 834362460, 624069069, 940247357, 304932973, 526207525,
	281586141, 673732186, 622993310, 60245706, 242982120, 347533655, 723851567, 903884505,
	848661970, 5808435, 4100177, 325200520, 463987409, 778690288, 952789124, 460486942,
	87362107, 769123156, 734842570, 151272358, 403517926, 636656532, 252129362, 320375499,
	828924609, 521350764, 396801120, 322164866, 267347858, 326798812, 460072210, 754585268,
	41844894, 623028132, 170252580, 425750789, 90889333, 400809240, 330273436, 599612651,
	283651917, 546316140, 362721138, 237891671, 341402068, 390173944, 129108590, 756712633,
	175133514, 121950760, 393747854, 741045935, 204053947, 886472370, 56804753, 166011895,
	370589691, 196694781, 33220760, 898449678, 715468987, 755498629, 790731847, 176897806,
	276243521, 475502044, 271440386, 898086553, 181367852, 481358849, 732938432, 706071230,
	522030133, 353791360, 640624980, 966395690, 464248798, 983632666, 813061991, 976792028,
	997376957, 105612655, 137877282, 783187328, 516232837, 203601430, 760156139, 36036184,
	356869972, 688343948, 46250748, 87519769, 538663018, 216426742, 248239482, 199696298,
	260427125, 868336482, 450074188, 462459913, 410714514, 616355162, 130360866, 568211595,
	891465965, 908536224, 597831287, 544203854, 747707336, 884286592, 125120788, 172569443,
	439339251, 507358268, 476983382, 401077415, 77539849, 956758024, 843095374, 947266908,
	987281124, 17613685, 885788414, 24329803, 760635516, 619335722, 993687809, 980207845,
	64661516, 97214875, 104645672, 51514492, 621396770, 975755186, 624244314, 798328304,
	25454257, 222746093, 632384124, 718104499, 309167409, 407794156, 407175817, 829136880,
	362212695, 974450879, 733474451, 885789439, 459253371, 611048507, 652455524, 945896274,
	647806190, 683648229, 962675029, 509157836, 379987386, 817697715, 629686275, 616128654,
	186181824, 549006943, 304263163, 780772676, 812206529, 191322425, 732709478, 981535590,
	827061937, 649537578, 546915497, 409418761, 191621112, 480571943, 356280644, 413420365,
	423316311, 180089340, 177316217, 744584108, 537712849, 729285994, 121467575, 694877133,
	579412081, 387518408, 765532843, 244370194, 281697045, 83794772, 288585723, 769917602,
	267640938, 202959117, 949088082, 784517933, 287040694, 468582083, 708399613, 622798571,
	964841902, 816332346, 475672432, 361127663, 705057289, 527593692, 461709436, 139382604,
	299252572, 242604903, 128577146, 371193735, 728796317, 45488906, 593028689, 698614550,
	415971722, 807715721, 358723871, 717180869, 527127298, 714960900, 886781232, 143732308,
	810040987, 478575906, 895231026, 292997136, 29027499, 78463386, 22484402, 796224520,
	44136501, 975085735, 377854960, 47697023, 602068169, 7287374, 910507016, 714195072,
	857956827, 322318104, 652652600, 429396710, 927433441, 966637188, 219167103, 924656211,
	179688171, 60512819, 174880815, 68468813, 865356434, 200133273, 536336324, 614337085,
	758991665, 700529731, 383796608, 170217531, 966630370, 945912949, 758710559, 822955037,
	384912188, 468693962, 851342393, 485586535, 548519041, 904336541, 376896000, 225100331,
	207700847, 190295095, 32931794, 917934260, 968576072, 346009912, 237852130, 516452946,
	703754945, 783986019, 902841081, 47259844, 524646399, 367779004, 421589982, 345748280,
	399398818, 721770840, 186587103, 893352297, 585339354, 933064963, 243571583, 414143741,
	720408798, 448952300, 259586972, 166113710, 229736868, 528431545, 780403018, 495777746,
	747579039, 708604644, 750441395, 964867022, 652617181, 301547888, 579916294, 125902556,
	748138564, 201433898, 958182885, 684753877, 445527004, 662938561, 811414835, 366575909,
	814755712, 137449199, 287052988, 48806974, 34976259, 161713530, 215021223, 976055248,
	745249347, 437458827, 67036003, 804334720, 226508387, 859193587, 326481959, 328577027,
	298373935, 794672656, 443050169, 507363585, 520146774, 508587008, 962405235, 382535062,
	96301484, 97927679, 885839173, 552174062, 391540612, 718198634, 771044307, 102828539,
	307448236, 706362352, 731390315, 772222945, 713171346, 659709897, 234582930, 238741767,
	958271665, 216632591, 226800788, 694447642, 870032187, 886385307, 438677846, 942347569,
	42074518, 274449419, 988432725, 537249132, 655244616, 252224118, 446420200, 623566631,
	312844333, 375404777, 217792569, 469615324, 769852289, 357956694, 182096373, 500646975,
	982127624, 960375732, 389004479, 555318333, 52155699, 441234930, 103361382, 5391796,
	992312568, 206121838, 143848982, 394550128, 585145329, 531838373, 711232595, 221784907,
	538863790, 639023672, 300252077, 395610416, 163274005, 564275477, 62234127, 420192486,
	585909077, 738325164, 782963531, 537973773, 247739669, 294355566, 461343408, 122666805,
	528558929, 652684837, 431835296, 169004271, 91735696, 43894405, 204513438, 103785835,
	541919464, 31807156, 652532661, 728319064, 521815993, 798338391, 971739200, 849980329,
	96501138, 80912632, 344952264, 905080491, 575022454, 547908299, 677762405, 476268592,
	632379785, 943622827, 751902927, 784560645, 592058324, 283721317, 45965853, 346992609,
	813255509, 344532645, 699350216, 455391409, 582093198, 963480555, 783699608, 298847178,
	675835510, 204358396, 938105377, 328455489, 464831376, 214432638, 87487987, 795473338,
	611769398, 509347280, 416966650, 390202116, 580941127, 761873371, 792204368, 574362753,
	923610593, 456168700, 751761909, 688541121, 301839578, 294739039, 552997322, 689853329,
	710541518, 829943092, 177334257, 655096159, 583038712, 679706529, 942573863, 391694994,
	535453658, 860868919, 139226005, 511283132, 553979550, 111906575, 633266261, 153189136,
	408153968, 560932704, 780633005, 717739796, 447266274, 712103910, 682990019, 469181737,
	823412293, 31555526, 283379293, 569206692, 626802069, 965765301, 138206758, 622308083,
	675346745, 694038877, 907071572, 232932486, 273165540, 725516963, 778161716, 997548490,
	535276389, 770955072, 363316420, 813494949, 398176810, 651068013, 488514761, 41673204,
	970094012, 829280376, 45487479, 170226519, 500865724, 881176955, 904152002, 394540963,
	187896357, 263638156, 413372311, 783980414, 230389916, 154225251, 621057948, 317597961,
	791931126, 510002885, 353635661, 780605101, 498885333, 562674911, 61931574, 325069961,
	312189789, 918849265, 444405850, 273436471, 142258553, 508695897, 338066724, 618150606,
	811516976, 38030666, 512581210, 725434753, 690186373, 566782454, 133306327, 507254144,
	595530449, 189703630, 606590915, 631418815, 90238426, 265940850, 596702055, 812788935,
	618049736, 848510070, 436165456, 534177717, 146278719, 876336024, 268434711, 36006377,
	410415047, 888708441, 326540093, 524103529, 788861897, 5000722, 736761458, 431076250,
	264048084, 954344075, 99871198, 475305432, 657638964, 943159110, 632119995, 495713214,
	537577512, 577113121, 588866086, 580161747, 169478572, 118214659, 712706031, 800028723,
	209805699, 37644737, 190002871, 313923367, 373941193, 442690561, 287245714, 125272577,
	477522688, 891095986, 581669525, 644634584, 12613186, 98337404, 764905674, 18322385,
	909045292, 235945883, 50446253, 263080550, 542922756, 68304755, 484118394, 896962298,
	108875137, 650466819, 738754062, 442081381, 910439826, 813189458, 850144238, 462859204,
	645349311, 627597678, 267028351, 204756388, 854581479, 726213794, 263173436, 588218447,
	127690737, 742663345, 417258948, 953269791, 754964424, 422415254, 303757518, 680147291,
	416989597, 906750646, 405802822, 228308642, 380924276, 451165989, 824339641, 181531795,
	510931819, 825312070, 809152148, 45801631, 701667765, 687759759, 455454710, 174904489,
	590393407, 386429792, 515352678, 11430588, 364265112, 227568435, 986279481, 243902931,
	259643713, 637907599, 43970361, 831966481, 716338649, 7522035, 312609248, 745774003,
	320547207, 578911734, 408280578, 390736422, 230092770, 50217478, 388345643, 970391194,
	474107824, 74406922, 338564100, 944489094, 634556931, 369473110, 752976518, 205093838,
	342653696, 375436752, 397487154, 725616932, 189598861, 904714771, 159186232, 97372333,
	232708299, 586425274, 563266225, 945973383, 118155208, 495018795, 171070575, 659673782,
	860169617, 201553068, 512619463, 913404856, 207179006, 949846228, 603409142, 201682553,
	616222621, 854919463, 460191939, 909285674, 540819416, 49299312, 955143246, 299736623,
	856611053, 376822913, 329335101, 237011896, 462471431, 27454513, 319569807, 328610785,
	748067093, 956758500, 159987293, 429330724, 765809599, 403812495, 958091808, 727132804,
	475149267, 40816595, 306790290, 737701328, 893621378, 664788305, 428468912, 10231325,
	549162110, 387743851, 260693998, 284099059, 206138747, 695502993, 323093207, 679192523,
	124801433, 631253663, 766429709, 285974405, 511135459, 8998358, 580744325, 907211539,
	191989264, 817084224, 280275229, 36113463, 585047039, 378038463, 817756202, 423212838,
	547187333, 617800025, 475783486, 583120042, 610542457, 829014756, 752622166, 663218502,
	507465515, 261266795, 179520532, 32955550, 496382965, 558590189, 167052410, 621749919,
	466598598, 86329644, 935959390, 87780318, 19857323, 40008715, 764296818, 243987549,
	615026723, 482990021, 138862857, 794607654, 875376230, 883616582, 438294662, 522095746,
	266454901, 148135177, 307409429, 925748901, 791651697, 880770763, 374664157, 973560636,
	357402609, 498260676, 102742406, 391283338, 901285897, 379543924, 839024863, 46818051,
	554467907, 672033810, 866171934, 824752741, 176395530, 10585312, 954563118, 381781834,
	278026251, 300803630, 408234944, 648314991, 228282045, 434315134, 399531852, 736522339,
	868909135, 141119608, 287541036, 583281122, 535712311, 556054419, 951886398, 264799841,
	896511718, 548944674, 160773576, 750893075, 5826296, 427270326, 480539039, 916775968,
	199244107, 963089574, 248524767, 413247037, 52441183, 974287495, 477750648, 327555241,
	929529593, 972447499, 237452228, 893598946, 217864916, 846111651, 823785641, 197311266,
	548833449, 444216436, 200030934, 890089559, 725057299, 128799609, 463526200, 202636379,
	655930012, 765612006, 666755054, 285019630, 500094076, 915429828, 340924073, 541298497,
	20952517, 971588866, 539689185, 575135131, 615253657, 408069545, 141410432, 609974115,
	923659263, 911226225, 624603605, 309405406, 315521034, 136911419, 762621976, 617564590,
	234169026, 650090346, 418978394, 361299627, 216001056, 719471073, 554429814, 122372237,
	42682998, 986834207, 554779627, 681724255, 666755626, 11882232, 614649229, 67112733,
	117025205, 520129568, 294996127, 77042248, 795062882, 598276311, 685101382, 91424645,
	331715253, 131946305, 81913771, 814383333, 890765262, 682858473, 765843755, 452538714,
	804238552, 690902985, 193106254, 391501153, 399755, 645036210, 773762183, 778936518,
	41118681, 199441862, 472008495, 963289345, 28781436, 706653095, 198515688, 494195389,
	205574540, 652339895, 904484579, 881945047, 964789212, 911868935, 593256084, 822746626,
	2318624, 582964405, 322093907, 422005732, 480535712, 908564412, 121117689, 764851036,
	590283297, 144687637, 693066779, 649430877, 133070985, 975138683, 681973893, 972060900,
	335633206, 774548721, 32377966, 305542796, 238989327, 900147357, 640626499, 573958041,
	822322644, 799192407, 312337492, 29548624, 178900447, 14956066, 619720699, 760142579,
	282420923, 632355687, 47602013, 631940055, 736522852, 353947655, 398432169, 947386779,
	866010856, 301186126, 452665778, 103713849, 871139405, 543765525, 660514179, 270644887,
	118909533, 226753166, 884245760, 949580905, 24846082, 45810491, 35834761, 871043957,
	477388420, 395586468, 456000586, 918325588, 666919588, 436714666, 735702383, 59897843,
	559833538, 395579402, 335720417, 514674780, 980416242, 203772181, 113547517, 489887946,
	935768507, 547794331, 306364622, 521396312, 726286154, 295682958, 460593720, 503469368,
	258478585, 277143388, 334401065, 152254264, 258890008, 875499347, 796700034, 522218491,
	424373916, 275177179, 468492272, 497730095, 774809679, 971894448, 562356090, 836410915,
	24536911, 547739941, 741351645, 467936893, 756679514, 721104915, 927665912, 765353908,
	951967787, 849085091, 322373980, 921637388, 767975601, 583523377, 424929182, 765999573,
	86834701, 341037580, 289967738, 272480325, 386062086, 383796708, 665016936, 608852574,
	344871828, 843574589, 169576772, 289967179, 721581752, 922998854, 263803223, 236052475,
	648062207, 87181299, 38805350, 606029794, 100195797, 12739719, 452340158, 622451455,
	133969287, 126130144, 513467315, 285246319, 533583924, 972016068, 933002648, 818567277,
	901868760, 819333071, 902521517, 745398337, 749929079, 49316534, 145076731, 265536836,
	937034425, 254984747, 16472262, 62004320, 66267847, 217581511, 499013135, 604762394,
	668797564, 51922027, 317480444, 984556370, 616439959, 38465036, 24804307, 909849711,
	309380768, 975759955, 882136302, 900244832, 79772371, 728113364, 65292534, 444033788,
	49404943, 714924822, 982326262, 377775344, 302801484, 582676302, 429388976, 179976074,
	666909962, 913384001, 432025413, 867590296, 519782298, 709283186, 685146095, 74295244,
	907592844, 266858268, 563342664, 262167796, 914274797, 689388443, 223841946, 380809218,
	726492795, 704520605, 704645952, 240090239, 981599410, 392341966, 737051281, 56889463,
	727913634, 648196237, 201084520, 685688588, 270212978, 798752778, 968028017, 96093935,
	996576193, 964239764, 601070003, 89718234, 329334178, 654324896, 930515571, 635802949,
	819692362, 693527901, 786470251, 552791085, 761111051, 34361546, 842826953, 971329925,
	883938945, 586522396, 488339587, 516384488, 906009903, 727824391, 850553082, 237034449,
	360269423, 85001092, 961911815, 164117158, 282583460, 584856480, 555966410, 709209653,
	869749688, 647534813, 29056404, 28451658, 18474844, 377078392, 909225626, 693744900,
	443535325, 879215268, 637725690, 489647013, 786569076, 796594366, 224915060, 111616093,
	313581344, 10966093, 649599227, 633598768, 64339479, 407153666, 112319329, 739036503,
	510962708, 146816953, 425327274, 393668777, 705504671, 16478168, 63901438, 946324047,
	65216237, 337877413, 698328434, 47535813, 887433918, 944228820, 889629148, 799594961,
	950556424, 714274666, 421084003, 778659036, 905830587, 407041390, 874444543, 75498091,
	88860786, 681387113, 551517748, 233848827, 758524941, 316270567, 643127804, 190242686,
	765291253, 64316952, 598488598, 391028364, 414539768, 571070659, 83828439, 170343549,
	208895640, 8078346, 336695908, 731479580, 824637131, 330753580, 353578501, 792784280,
	30860908, 501646292, 246519901, 411652583, 142801846, 281315008, 5815376, 112576049,
	888760811, 778658929, 402780370, 170109717, 514872685, 519112806, 983713820, 286354780,
	162881836, 3669973, 566852202, 194160361, 754238926, 79673992, 945165898, 153803983,
	854567609, 829670524, 592326194, 86670687, 335365129, 520923245, 748557847, 380227161,
	964112558, 910992448, 653413610, 297746671, 591665594, 65331347, 366877570, 226809731,
	328142793, 873441268, 984236439, 954189771, 791470141, 57835207, 98838903, 596809127,
	808919720, 336545636, 293049687, 714680045, 189405569, 930974602, 944823880, 231876168,
	121852766, 974628716, 923083358, 925008879, 535988211, 56769378, 148732345, 969116917,
	402273165, 789785728, 783280822, 373558754, 854979469, 660735364, 463539772, 952513791,
	928690075, 113949131, 26237985, 460959526, 853565185, 364848858, 333790549, 6117493,
	108643158, 73488792, 819057850, 880430247, 769136256, 803755369, 878344104, 8975660,
	135269006, 842347792, 923620993, 807870926, 888928584, 769712809, 335220798, 110486491,
	925099427, 749959713, 345541342, 600624858, 848977501, 481476038, 382303225, 669630943,
	333105486, 282794372, 961626526, 171050905, 87396941, 304701372, 42315343, 516298226,
	182635335, 712334060, 240865017, 664264555, 40434875, 886882255, 377874119, 412319014,
	502240551, 526088983, 572771436, 652375023, 928201396, 261772140, 798565196, 692800948,
	147043572, 839582257, 475736236, 938716652, 957634546, 439456405, 486519362, 50283355,
	573712984, 532506519, 634497746, 722935224, 215474818, 452045852, 53418462, 185005638,
	464449458, 53386417, 981497968, 898594293, 395886834, 19893903, 849804657, 187288142,
	397698082, 611085170, 729165956, 561450753, 500217456, 496509673, 898914015, 428085853,
	930967836, 757853614, 129592339, 11030691, 864803249, 8483279, 913970543, 846424476,
	935117672, 852975318, 586658304, 700364427, 461584751, 633008925, 256890419, 567398297,
	534830222, 984312301, 759438039, 317356134, 779838964, 681358033, 794866701, 549141007,
	718828733, 411224674, 803343603, 421105043, 188050432, 991422127, 356364802, 349219429,
	762732703, 674001578, 206938045, 782222493, 815717865, 955372941, 315367746, 723072085,
	440474396, 145555063, 888058877, 590810486, 161517106, 734737362, 193202938, 877863657,
	981087614, 937664164, 769254633, 318059070, 850620447, 645404990, 930145263, 593824737,
	335628894, 688417345, 679469159, 358427206, 839081418, 177228383, 313388354, 359902715,
	51483694, 267078727, 303920607, 224200814, 952519761, 472515398, 793953226, 4878543,
	184935718, 65620926, 252210461, 722510387, 548597783, 996559756, 823427235, 45890520,
	387144414, 336464152, 680570819, 928888096, 672084186, 837710543, 409678939, 776730507,
	788258676, 692450835, 373577211, 556908690, 543562485, 459319159, 537884754, 275755332,
	241032420, 307270824, 102785273, 954378507, 845292358, 451630962, 329296098, 966386966,
	646732201, 83889649, 329617123, 928135002, 66599180, 344114847, 701579910, 860951236,
	715286880, 909398300, 993977925, 245370849, 670785517, 728481930, 487545450, 221433836,
	68099895, 598212289, 176786441, 587577413, 756448737, 759733432, 50932383, 361502378,
	90095623, 668705964, 386238232, 202520747, 419728570, 806828233, 670001202, 706064339,
	167036421, 941810967, 434330899, 370566918, 430006919, 717292820, 389616556, 282625796,
	104051016, 560132061, 762815948, 773062888, 371754219, 285470864, 799095278, 733583061,
	362572358, 558755505, 763144755, 415271063, 952841714, 629415824, 899154153, 658508697,
	726814509, 541859788, 471382924, 244506662, 578507966, 493040057, 221017121, 303736,
	787671392, 224560562, 34455882, 31131504, 918032962, 571932105, 357978037, 532582759,
	541245173, 278523017, 785727714, 862206042, 441134591, 194060544, 320672522, 874659404,
	666366534, 458412740, 682319765, 27772410, 841468884, 145484207, 572145121, 539840346,
	255382982, 69175697, 605735900, 434451034, 721231023, 848635553, 666637416, 754197083,
	193503119, 590543697, 725623884, 809040047, 132696921, 685868272, 511252113, 717811961,
	197122858, 138102054, 293582337, 153568904, 90459628, 394023056, 601741309, 51504988,
	74429287, 664594916, 971958010, 63809749, 780662178, 34180134, 90743966, 264858183,
	748933078, 234813129, 364620803, 877853542, 388892230, 1361789, 479847422, 48647325,
	132805884, 727510052, 593558297, 144454270, 643147938, 841304876, 85930301, 844321310,
	996518129, 423739373, 615097507, 952385426, 961243704, 451032561, 831181311, 126650123,
	796935846, 247961412, 817123538, 872822060, 379251627, 107544802, 841478924, 381235137,
	36081834, 477338127, 630525853, 264136857, 408363603, 171613291, 168231064, 815245434,
	124574194, 803293935, 728223364, 535676175, 677441057, 713341286, 887700883, 179559668,
	386187061, 425790153, 252838549, 465146448, 107245898, 610237820, 446151626, 466120592,
	926012440, 255793266, 604891531, 37886283, 323295694, 895817034, 949688548, 299562662,
	748136730, 9895454, 286069793, 26937718, 51545183, 382888397, 366910501, 94365220,
	147265585, 889916951, 914439886, 796287260, 507320663, 49809525, 425461962, 770345203,
	675981859, 311439854, 57085808, 656015900, 369524555, 781908154, 927084147, 256711314,
	722608579, 429950455, 950830429, 127815872, 937736455, 657184645, 760338593, 638355459,
	26010317, 946891453, 697394110, 816912687, 812128180, 682715561, 837568728, 757982264,
	526866610, 788840456, 891580595, 557307276, 721170714, 398938019, 154257235, 428272240,
	63718307, 932076371, 278249413, 452547849, 718445577, 128994201, 26897550, 137716375,
	452261307, 57984300, 205219814, 995248090, 786225240, 796136126, 666469512, 115210862,
	833196367, 669584737, 475955258, 7816347, 816152565, 776975479, 668010398, 46766988,
	990444071, 118325435, 43450092, 477869909, 384090588, 162592496, 623610431, 957676554,
	215183989, 699486677, 395892605, 322347072, 993918173, 780865234, 72319807, 222428789,
	4595579, 439042869, 795573646, 185610981, 271069979, 306104471, 930278113, 205736704,
	271329520, 471601927, 840817344, 232174577, 923857571, 777541313, 199042701, 210608637,
	147427028, 716271422, 733809568, 970373761, 675514336, 629454636, 395911282, 604386869,
	284067960, 333596260, 637520900, 841705570, 327397341, 169160175, 254907006, 963350225,
	774597449, 592270963, 591919610, 525599176, 244988752, 201443807, 681458545, 812228770,
	578793798, 158108579, 972022559, 569692839, 353651940, 262449596, 609501745, 989608533,
	678783012, 228670663, 731572661, 269855179, 719983590, 129313421, 197931003, 769908974,
	926488159, 294636989, 48065677, 929287191, 426208428, 631072683, 230211646, 609309773,
	568563934, 473065210, 297154184, 134219249, 502114988, 692345265, 569567922, 399827295,
	921572820, 488708251, 971171902, 875953786, 610259252, 404883088, 611885368, 650181541,
	383628463, 189368443, 177818165, 931690599, 591700256, 177641693, 93305544, 41902760,
	970877511, 902549231, 342340421, 294605594, 768874423, 287231666, 121038837, 303886305,
	68242206, 839772818, 76044850, 401898332, 335075261, 937780316, 170111267, 545989114,
	808391881, 195900987, 790051871, 398934368, 202989769, 663118209, 735955239, 943314314,
	163493293, 391658715, 45962155, 247924577, 221756182, 201824907, 432748933, 866843843,
	818604440, 722788229, 441056530, 990693174, 473322447, 549447093, 358503237, 177635488,
	352851801, 390399489, 343514487, 983849421, 325300530, 537222539, 632957642, 710482824,
	67053789, 375494304, 250296156, 790246699, 377729454, 918187115, 261259936, 119991259,
	123192034, 989028960, 414458937, 848417878, 977359089, 198092576, 159009318, 977146713,
	178747877, 838006530, 246012400, 444616216, 516426827, 550459652, 135167631, 669178051,
	529859554, 406212046, 235991003, 677723981, 529765243, 322823123, 899433837, 523602519,
	239183912, 442977609, 540916589, 442066187, 883106827, 739483178, 748738985, 292352476,
	14733470, 609094826, 200435131, 914437813, 970672368, 547790403, 286936363, 947143520,
	337889202, 622014451, 895893273, 522008994, 614459995, 600314356, 687024774, 556969098,
	565063217, 721908791, 898444383, 639996412, 415897615, 323650096, 376222539, 410542322,
	205236179, 344150281, 917981055, 339244914, 381123557, 338562710, 272172934, 498598675,
	178575398, 13646841, 558235004, 926591620, 433798909, 287237488, 305400199, 375257216,
	646942175, 91664476, 346370489, 595635386, 630150212, 329225015, 302637946, 645281105,
	580871309, 835671695, 683790262, 282067899, 31205330, 700799884, 467623687, 4612234,
	265655566, 212309012, 639977945, 830676731, 118367861, 616097658, 326232186, 302620271,
	135817500, 406879247, 750704847, 152065197, 365465170, 338656342, 48268079, 161977083,
	663700529, 914317019, 1562052, 968566299, 551625507, 85253817, 338202129, 707468007,
	313966456, 510080262, 640480348, 679123116, 171038228, 145770184, 44584075, 138971662,
	388211591, 146051060, 328631713, 641609142, 242349702, 237095380, 505333417, 233013375,
	647215844, 707861230, 432619798, 165162834, 671792066, 764237982, 956454776, 880606055,
	275776230, 145115412, 703955154, 972921960, 908376500, 35197381, 183643943, 544406095,
	118781836, 298142688, 833038825, 995588876, 847648380, 432671075, 35284497, 138545892,
	335644328, 167547584, 784231446, 603283708, 757282208, 34264547, 934929372, 135608946,
	106243172, 137756861, 93977859, 219241758, 893758453, 668032640, 466504664, 23924768,
	979020668, 743302284, 931234687, 532020217, 431990101, 892789730, 510616737, 621091355,
	796669460, 269619741, 71014442, 740849235, 342945916, 352161521, 269999196, 205517171,
	784676812, 783359292, 153343975, 616423483, 276130183, 55084482, 66565066, 470655886,
	48496927, 64517043, 977943055, 512884161, 266810260, 960585242, 810808727, 882660709,
	772785466, 994111762, 652065688, 458514950, 100933624, 517457788, 497186654, 888214757,
	772979683, 36069617, 818070368, 477302590, 28945252, 803570486, 501113640, 180412413,
	695169305, 795765248, 610637693, 987063089, 975218270, 720765643, 639363475, 716895962,
	715961917, 593797736, 860732749, 858246650, 227605599, 630936680, 596179383, 257551815,
	772004253, 961986512, 971214774, 336903550, 97886420, 836421248, 95140427, 374296114,
	546863206, 224834604, 618000427, 63057084, 4837104, 190947216, 335488986, 676244218,
	82923064, 611481074, 149331602, 493446465, 111946006, 239258468, 239138715, 320024045,
	601711799, 72636605, 832787020, 672692392, 313160728, 481713838, 46402953, 374079035,
	815270636, 742630739, 742052977, 290454116, 314452021, 928507884, 331143064, 134835777,
	644312478, 593025172, 632112000, 343799617, 917062294, 930312621, 214555159, 499498431,
	17769059, 227220200, 20565046, 213776637, 307850984, 141151723, 57256034, 396543599,
	629259662, 164952004, 456197895, 2740729, 752229547, 467018398, 845103244, 209259295,
	971008244, 39458133, 976697436, 203335842, 468312310, 77363191, 347193353, 229890810,
	738295002, 958671664, 52780492, 639505816, 344415558, 323898559, 382921795, 470605289,
	705560460, 355878955, 325080201, 703552080, 785665211, 221680250, 81479498, 458659138,
	692301787, 524255655, 723393699, 949169588, 880843570, 106544325, 184006176, 21048493,
	275289495, 560713840, 431056296, 498423520, 496352605, 929154966, 799241633, 692459588,
	149995411, 208777923, 268936465, 399538781, 858468433, 589122628, 726808553, 799323745,
	81458382, 783141551, 923516739, 154186862, 217504338, 958858844, 473973455, 810367017,
	864799423, 845208567, 809288463, 712135764, 603831098, 420245233, 240515789, 477751066,
	928696839, 786083451, 642643942, 218205513, 179810823, 643590010, 379531945, 773568233,
	284186171, 406648896, 941617356, 398071896, 472404010, 136248997, 408125743, 92263138,
	663696901, 960383028, 656892284, 397308368, 903971166, 68052268, 319738397, 750607393,
	246177326, 158381064, 245745467, 645385893, 532025245, 212508280, 401120577, 870451768,
	832928086, 420262035, 290797284, 172512462, 832055793, 901943923, 89883403, 930507505,
	268779154, 134310684, 961786639, 573192195, 575966902, 854974808, 803753137, 361542051,
	835988676, 77505224, 248474559, 245796126, 389494789, 596039892, 824961077, 624707290,
	86400350, 433793921, 486420441, 417174105, 599008153, 597172424, 77267238, 272768246,
	94630013, 608890571, 37834082, 313553731, 488404013, 485155889, 661700332, 688325150,
	518698490, 94201882, 185996172, 608632422, 59255538, 693164687, 837626304, 721103086,
	871759537, 601219554, 953421754, 611961373, 44824223, 791751326, 960658341, 865908495,
	321709079, 9866417, 604107006, 201009443, 376419573, 89407447, 507562994, 391336274,
	374375705, 375829235, 758272765, 597018248, 883453097, 770093445, 273731848, 471218120,
	946212693, 487274081, 707480099, 64739907, 29855479, 438959372, 437421162, 136089960,
	143107420, 573438316, 907109192, 42027868, 364899315, 471714666, 147722278, 920147346,
	800553099, 352398911, 896244379, 659270227, 598646481, 408119239, 825927304, 600758339,
	585284928, 793123464, 794145199, 963457336, 2211144, 23234523, 664167478, 750120988,
	865864136, 413237829, 177368170, 801401088, 466462630, 903107521, 8700958, 295233878,
	855810427, 260872157, 129455989, 890324285, 430938770, 552519697, 731408034, 617741993,
	244789848, 674522607, 52945880, 989363718, 449690019, 692278159, 808359929, 278413081,
	562626876, 183304532, 553179891, 529983875, 652991597, 141172859, 143025706, 289575018,
	386206318, 648362490, 309222603, 257881186, 277791210, 411091094, 727358094, 979621136,
	774130848, 396934690, 622659423, 323187973, 731374979, 119457375, 195414112, 610663014,
	851633075, 412951650, 737055862, 365102528, 388909870, 37890732, 407970219, 740169370,
	87183268, 937334052, 991437494, 837582891, 877009724, 12983145, 87711218, 832400190,
	713794602, 973897664, 353648728, 882132123, 546853264, 32870928, 709116225, 474998704,
	851740181, 449996292, 906563533, 758609622, 797218820, 904968781, 854727930, 776620267,
	131117952, 272298727, 696222541, 851445207, 992463109, 678769312, 212969390, 303342920,
	660914683, 933023801, 75189453, 923540733, 764753410, 532734441, 369983644, 61396804,
	280474884, 586329163, 462779665, 97378590, 158961359, 444570800, 675961427, 219001330,
	475415788, 777779965, 326705036, 221224449, 416959443, 64739932, 548403488, 437212401,
	243820970, 162022185, 137578940, 174731020, 630079088, 38195846, 342676763, 194570642,
	970957467, 793884056, 939765773, 753095039, 538418737, 472180476, 951951209, 683571332,
	820033654, 423352731, 557861565, 36005437, 179740000, 320942060, 451274817, 517374226,
	59755316, 930587606, 915332979, 369980609, 6275890, 100785199, 592378913, 364709435,
	399700655, 585520684, 777849090, 340001913, 136622599, 566497517, 913871823, 642253625,
	256048531, 736981226, 514271956, 290403650, 347055625, 531051212, 845541100, 60406055,
	825581574, 891074167, 311155161, 12474201, 515010365, 442476204, 743112382, 717461701,
	97081850, 512687227, 319242938, 356865359, 768235747, 993450138, 413942202, 661568963,
	443639603, 787189270, 275998479, 102839489, 301170608, 251157312, 651115670, 614527244,
	805210498, 212289488, 401090258, 637074071, 560847055, 269756414, 796664726, 638959169,
	774376660, 301889297, 300713647, 703341189, 834968991, 36534569, 44999657, 824678517,
	164051002, 964063088, 229712994, 318090327, 556568928, 974325297, 539181057, 452753805,
	362476217, 399857726, 742783513, 443132764, 712360634, 181674510, 254592820, 698497887,
	814390766, 286197064, 265111974, 65062743, 543460300, 322751992, 543699643, 857089888,
	552383080, 551489310, 647591705, 277582585, 416048307, 445268567, 372859331, 35911602,
	63537375, 417907809, 640119043, 38180160, 844873087, 768037860, 212632881, 993232919,
	436759518, 390058527, 954241844, 935702400, 392346631, 202323006, 994798592, 813641698,
	793404592, 545314760, 951869229, 965980880, 91255377, 100517023, 167415343, 78370792,
	538430048, 71386965, 116175107, 576727622, 692897307, 833536380, 354212150, 957560157,
	196088915, 161188644, 870610212, 257635544, 815686325, 21490952, 430448232, 49267378,
	965968656, 211006640, 858425286, 989464063, 951944903, 110325052, 212276284, 855674214,
	671233262, 510499125, 209433026, 21963929, 941815979, 724777389, 254461193, 740925262,
	150434699, 157277874, 863625659, 566570041, 524492106, 211727223, 325467554, 477921679,
	927939320, 786080751, 508033505, 745525819, 932938764, 405768728, 935837082, 910586407,
	563163603, 557899527, 835356740, 497718682, 403585481, 958364334, 968947055, 820889658,
	67590602, 57982538, 238572077, 346029689, 246686931, 255657091, 17376531, 897655864,
	352073025, 504035232, 699101428, 874494738, 117304595, 693862602, 109381940, 890329894,
	333397901, 368413152, 783867223, 207361662, 371000235, 784679500, 231486229, 674015650,
	840124972, 235541942, 555181739, 509814257, 681253296, 371288465, 302887242, 705923483,
	797099580, 485566008, 318125935, 678904670, 262796356, 853189342, 223492004, 181428723,
	152029247, 60375833, 431108962, 899801372, 632092186, 554769341, 847092380, 351085786,
	933077722, 53568307, 699419426, 414708090, 273204586, 714954593, 569997873, 206480760,
	902082055, 450429410, 13358303, 365571030, 235674167, 671382751, 299515969, 281026642,
	964088788, 470890148, 72387193, 770215362, 598483271, 482136268, 630051633, 368570689,
	770264937, 23546309, 315645754, 366999141, 337181888, 651340540, 492348154, 223252027,
	270748831, 833301845, 892694266, 671238059, 629396602, 320539838, 585242257, 160430739,
	747653807, 879809611, 217955576, 327298912, 712806657, 288544907, 900009130, 466417899,
	311919379, 382795964, 390598180, 859516498, 759274305, 292281769, 614213744, 572079682,
	934664232, 95275657, 95449941, 866203434, 620377052, 221457122, 878465511, 271790611,
	258258126, 306317829, 852901824, 861900193, 663863085, 864582606, 625842324, 91010110,
	541451013, 850970713, 245723294, 437491210, 793235601, 327166189, 767573050, 464987950,
	196838189, 74628264, 791302114, 237245997, 674703970, 539448092, 606112175, 641805157,
	807031739, 715602768, 157957669, 448385106, 12638358, 932634551, 156390285, 301291894,
	153030785, 42677849, 833416407, 253865625, 614097632, 811063192, 416106420, 988245276,
	854866728, 471956760, 721750670, 909810570, 465913521, 137852537, 295115600, 643170902,
	785433216, 706363327, 212125107, 594026143, 959726060, 128084349, 52858709, 491783840,
	503502641, 211618458, 208851776, 452515696, 58176829, 426000539, 327379885, 436964801,
	657152152, 611092066, 284994106, 153153342, 653960859, 143221864, 671492919, 955649009,
	283479207, 422619674, 495064903, 42348147, 537570436, 914446330, 601767595, 16595669,
	143734591, 329062881, 34011467, 895664511, 647723431, 899621634, 975036658, 223775550,
	297947602, 272061546, 760879722, 244743339, 461587562, 960881312, 523127777, 900415044,
	220185945, 25029821, 82934195, 568925513, 904903307, 939635164, 797770022, 764900490,
	488469464, 929746512, 220446587, 533972359, 662750203, 596175874, 952114794, 611745462,
	966850322, 432332192, 823588923, 224761137, 180590373, 848841656, 672393288, 709311211,
	205196166, 924660552, 907852948, 338276947, 898464119, 687821922, 888360993, 237922147,
	166753107, 295779459, 796967920, 554650004, 137113107, 934077473, 706340412, 712937289,
	381583984, 503463353, 897852435, 940632919, 162156171, 932257385, 531242092, 131718719,
	227824191, 226092158, 710710181, 416837769, 202980460, 765989583, 727930761, 583296063,
	108455782, 157555623, 172225060, 350365678, 32907402, 638299450, 388480440, 230189016,
	156508633, 594217737, 925222500, 112243842, 858326736, 145798189, 856539398, 624178999,
	570592132, 961201013, 660915623, 207941990, 193730215, 162136469, 302678602, 726057726,
	610021965, 627977654, 687676398, 265936867, 645472946, 348014485, 702643876, 313315394,
	363674728, 335721939, 317292450, 142845886, 789023255, 113012029, 158992451, 357620159,
	417220563, 517209557, 505858961, 993033140, 506940201, 693085913, 289948659, 310140301,
	134077711, 707711137, 68847028, 823612608, 735636051, 823379490, 655213692, 186221975,
	349859279, 783848112, 908822766, 84994743, 238542650, 854065454, 714221647, 959313333,
	356931610, 364847814, 460809804, 303818184, 38967483, 214799058, 889936866, 714160767,
	578406141, 969667673, 152858152, 888975790, 985065653, 852541438, 242896897, 838102463,
	887112858, 39136475, 168889228, 725386266, 491914546, 118542494, 154095530, 362784581,
	236426299, 757554763, 572188801, 50347377, 509175160, 892006960, 793640337, 378973675,
	273780969, 230479296, 956269541, 931888664, 21571219, 84346147, 519733729, 656123486,
	940683039, 267518546, 466010599, 786941035, 57620720, 314931459, 775194970, 880471643,
	443297964, 251687911, 269270728, 772158625, 643699325, 898820747, 943397737, 231131136,
	279501726, 101590406, 885519860, 283174575, 240904054, 927927447, 233495327, 153342420,
	650953636, 544643222, 319608203, 485519428, 173861428, 366746928, 386867426, 337761820,
	947281048, 487181009, 268954522, 459084866, 856262951, 437121922, 303741530, 327216334,
	402662299, 312436263, 993335584, 301826461, 807721516, 380599777, 128469132, 300989822,
	623837946, 926006936, 551329620, 901589029, 846241409, 517399898, 509454274, 92137419,
	894089640, 927311472, 811854697, 820495481, 324457553, 604894611, 292078299, 696608301,
	542216921, 270019860, 676743313, 364063136, 585117967, 326922345, 322859477, 506266974,
	71844431, 718693484, 148506955, 17721091, 104465123, 429923031, 236166865, 66586970,
	936845145, 329584733, 277855804, 51177572, 911754232, 898404142, 447612187, 341296453,
	33030748, 786005023, 220726291, 550842107, 193060368, 358032848, 930040643, 448406568,
	640592808, 192161524, 25470674, 272076219, 859593006, 150592794, 582364915, 286707548,
	208583995, 369281344, 90382196, 815150054, 16065527, 693191692, 548346977, 947214221,
	892048602, 233045561, 750057466, 359841456, 738221947, 984276235, 334595147, 260771761,
	597099208, 434479562, 145067770, 128834977, 556849803, 230969163, 983879378, 733278185,
	511250831, 451961865, 769422016, 26448821, 370564435, 511743864, 401972284, 218962244,
	671156881, 489520264, 926885874, 69210406, 665353130, 147066307, 947812456, 873459120,
	669055084, 210634484, 970171930, 730895150, 992364093, 293014189, 826106854, 337280092,
	875032178, 541166412, 48678827, 579917654, 571778113, 552750579, 400216617, 84029349,
	52810330, 352123216, 617370934, 932638758, 828851851, 196017819, 403484856, 738330996,
	998244352
};
}


#line 6 "math/factorial_mod.hpp"
#include <algorithm>
#line 8 "math/factorial_mod.hpp"

inline mint factorial_mod(std::uint64_t n) {
	if (n >= mint::mod()) return 0;
	constexpr std::uint32_t step = 65536;
	std::uint32_t block = std::uint32_t((n + step / 2) / step), anchor = block * step;
	std::uint32_t first = std::uint32_t(std::min<std::uint64_t>(n, anchor)) + 1;
	std::uint32_t last = std::uint32_t(std::max<std::uint64_t>(n, anchor));
	std::uint64_t a = 1, b = 1, c = 1, d = 1;
	for (; last >= first && last - first >= 3; first += 4) {
		a = a * first % 998244353;
		b = b * (first + 1) % 998244353;
		c = c * (first + 2) % 998244353;
		d = d * (first + 3) % 998244353;
	}
	for (; first <= last; ++first) a = a * first % 998244353;
	mint product = mint::raw(std::uint32_t((a * b % 998244353) * (c * d % 998244353) % 998244353));
	mint result = mint::raw(factorial_mod_detail::table[block]);
	return anchor > n ? result / product : result * product;
}


#line 1 "components/fast_io.hpp"



#line 6 "components/fast_io.hpp"
#include <bit>
#line 8 "components/fast_io.hpp"
#include <charconv>
#include <cstddef>
#line 11 "components/fast_io.hpp"
#include <cstdio>
#include <cstring>
#include <memory>
#include <stdexcept>
#include <string>
#include <string_view>
#line 18 "components/fast_io.hpp"
#if defined(__unix__) || defined(__APPLE__)
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#endif

namespace fast_io_detail { struct BulkInput; struct BulkOutput; }

class FastInput {
	friend struct fast_io_detail::BulkInput;
	static constexpr std::size_t capacity = 1 << 16;
	FILE *file = nullptr;
	std::unique_ptr<char[]> buffer;
	const char *current = "", *end = current;
	std::string scratch;
	void *mapping = nullptr;
	std::size_t mapped_size = 0;
	bool refill() {
		if (!file) return false;
		std::size_t n = std::fread(buffer.get(), 1, capacity, file);
		current = buffer.get();
		end = current + n;
		return n;
	}
	static const char *scan(const char *p, const char *end) {
		while (end - p >= 8) {
			std::uint64_t x;
			std::memcpy(&x, p, 8);
			if ((x - 0x2121212121212121ULL) & ~x & 0x8080808080808080ULL) break;
			p += 8;
		}
		while (p != end && static_cast<unsigned char>(*p) > ' ') ++p;
		return p;
	}

public:
	explicit FastInput(FILE *input = stdin) {
#if defined(__unix__) || defined(__APPLE__)
		struct stat status;
		int fd = fileno(input);
		auto offset = ftello(input);
		if (fd >= 0 && offset >= 0 && !fstat(fd, &status) && S_ISREG(status.st_mode) && status.st_size > offset) {
			mapped_size = status.st_size;
			mapping = mmap(nullptr, mapped_size, PROT_READ, MAP_PRIVATE, fd, 0);
			if (mapping != MAP_FAILED) {
				current = static_cast<const char *>(mapping) + offset;
				end = static_cast<const char *>(mapping) + mapped_size;
				return;
			}
			mapping = nullptr;
		}
#endif
		file = input;
		buffer = std::make_unique_for_overwrite<char[]>(capacity);
	}
	explicit FastInput(std::string_view input) : current(input.empty() ? "" : input.data()), end(current + input.size()) {}
	FastInput(const FastInput &) = delete;
	FastInput &operator=(const FastInput &) = delete;
	~FastInput() {
#if defined(__unix__) || defined(__APPLE__)
		if (mapping) munmap(mapping, mapped_size);
#endif
	}
	std::string_view token() {
		while (true) {
			while (current != end && static_cast<unsigned char>(*current) <= ' ') ++current;
			if (current != end) break;
			if (!refill()) return {};
		}
		const char *begin = current;
		current = scan(current, end);
		if (current != end || !file) return {begin, std::size_t(current - begin)};
		scratch.assign(begin, end);
		while (refill()) {
			current = scan(current, end);
			scratch.append(buffer.get(), std::size_t(current - buffer.get()));
			if (current != end) break;
		}
		return scratch;
	}
	template <class T>
	bool read(T &value) {
		if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>) {
			while (true) {
				while (current != end && static_cast<unsigned char>(*current) <= ' ') ++current;
				if (current != end) break;
				if (!refill()) return false;
			}
			if constexpr (std::is_unsigned_v<T> && sizeof(T) == 4 && std::endian::native == std::endian::little) {
				if (end - current >= 11) {
					std::uint64_t x;
					std::memcpy(&x, current, 8);
					if (!(((x + 0x4646464646464646ULL) | (x - 0x3030303030303030ULL)) & 0x8080808080808080ULL)) {
						x &= 0x0f0f0f0f0f0f0f0fULL;
						x = (x * 10 + (x >> 8)) & 0x00ff00ff00ff00ffULL;
						x = (x * 100 + (x >> 16)) & 0x0000ffff0000ffffULL;
						std::uint64_t v = std::uint32_t(x * 10000 + (x >> 32));
						int n = 8;
						for (; n < 10 && static_cast<unsigned char>(current[n]) - unsigned('0') < 10; ++n)
							v = v * 10 + (current[n] - '0');
						if (static_cast<unsigned char>(current[n]) <= ' ' && v <= 0xffffffffULL) {
							current += n;
							value = T(v);
							return true;
						}
					}
				}
			}
			T parsed{};
			auto result = std::from_chars(current, end, parsed);
			if (result.ec == std::errc{} && (result.ptr != end ? static_cast<unsigned char>(*result.ptr) <= ' ' : !file)) {
				current = result.ptr;
				value = parsed;
				return true;
			}
		}
		auto s = token();
		if (s.empty()) return false;
		if constexpr (std::is_same_v<T, bool>) {
			assert(s == "0" || s == "1");
			value = s[0] == '1';
		} else if constexpr (std::is_integral_v<T>) {
			auto result = std::from_chars(s.data(), s.data() + s.size(), value);
			assert(result.ec == std::errc{} && result.ptr == s.data() + s.size());
			(void)result;
		} else value = T(s);
		return true;
	}
};

class FastOutput {
	friend struct fast_io_detail::BulkOutput;
	inline static constexpr auto quads = [] {
		std::array<std::array<char, 4>, 10000> table{};
		for (int i = 0; i < 10000; ++i)
			table[i] = {char('0' + i / 1000), char('0' + i / 100 % 10), char('0' + i / 10 % 10), char('0' + i % 10)};
		return table;
	}();
	FILE *file;
	std::unique_ptr<char[]> buffer = std::make_unique_for_overwrite<char[]>(1 << 16);
	std::size_t capacity = 1 << 16, length = 0;
	char *reserve(std::size_t n) {
		if (n > capacity - length) {
			if (!flush()) throw std::runtime_error("output failed");
			if (n > capacity) {
				std::size_t next = std::max(n, 2 * capacity);
				buffer = std::make_unique_for_overwrite<char[]>(next);
				capacity = next;
			}
		}
		return buffer.get() + length;
	}

public:
	explicit FastOutput(FILE *output = stdout) : file(output) {}
	FastOutput(const FastOutput &) = delete;
	FastOutput &operator=(const FastOutput &) = delete;
	~FastOutput() { flush(); }
	bool flush() {
		std::size_t offset = 0;
		while (offset < length) {
			auto n = std::fwrite(buffer.get() + offset, 1, length - offset, file);
			if (!n) {
				std::memmove(buffer.get(), buffer.get() + offset, length - offset);
				length -= offset;
				return false;
			}
			offset += n;
		}
		length = 0;
		return std::fflush(file) == 0;
	}
	void write(char c) { *reserve(1) = c; ++length; }
	void write(__uint128_t value) {
		char digits[40];
		char *end = digits + sizeof(digits), *begin = end;
		do { *--begin = char('0' + value % 10); value /= 10; } while (value);
		write(std::string_view(begin, end - begin));
	}
	void write(__int128_t value) {
		__uint128_t magnitude = __uint128_t(value);
		if (value < 0) write('-'), magnitude = 0 - magnitude;
		write(magnitude);
	}
	void write(std::string_view s) {
		char *out = reserve(s.size());
		if (!s.empty()) std::memcpy(out, s.data(), s.size());
		length += s.size();
	}
	template <class T> requires std::is_integral_v<T>
	void write(T value) {
		char *out = reserve(32);
		if constexpr (std::is_same_v<T, bool>) *out = '0' + value, ++length;
		else if constexpr (std::is_unsigned_v<T> && sizeof(T) == 4) {
			char *p = out;
			if (value >= 100000000) {
				auto high = value / 100000000, low = value % 100000000;
				p = std::to_chars(p, p + 2, high).ptr;
				std::memcpy(p, quads[low / 10000].data(), 4);
				std::memcpy(p + 4, quads[low % 10000].data(), 4);
				p += 8;
			} else if (value >= 10000) {
				p = std::to_chars(p, p + 4, value / 10000).ptr;
				std::memcpy(p, quads[value % 10000].data(), 4);
				p += 4;
			} else p = std::to_chars(p, p + 4, value).ptr;
			length += p - out;
		} else length += std::to_chars(out, out + 32, value).ptr - out;
	}
	template <class T> requires requires(const T &value, char *out) { value.decimal_capacity(); value.to_chars(out); }
	void write(const T &value) {
		char *out = reserve(value.decimal_capacity());
		length += value.to_chars(out) - out;
	}
	template <class T>
	void println(const T &value) { write(value); write('\n'); }
};


#line 4 "test/factorial_mod.test.cpp"
int main() {
	FastInput in;
	FastOutput out;
	int t = 0; in.read(t);
	while (t--) { std::uint64_t n = 0; in.read(n); out.println(factorial_mod(n).val()); }
}