The Preliminary Contest for ICPC Asia Nanjing 2019

#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int prime[maxn], isnprime[maxn], fai[maxn], cnt;
void sieve()
{
	isnprime[1] = 1;
	fai[1] = 1;
	for (register long long i = 1; i <= 1000000; i++)
	{
		if (!isnprime[i])
			prime[++cnt] = i, fai[i] = i - 1;
		for (int j = 1; j <= cnt && prime[j] * i <= 1000000; j++)
		{
			isnprime[i * prime[j]] = 1;
			if (i % prime[j] == 0)
			{
				fai[i * prime[j]] = fai[i] * prime[j];
				break;
			}
			fai[i * prime[j]] = fai[i] * (prime[j] - 1);
		}
	}
}
int t, m, a, b, phi[maxn], ct;
int my_pow(int a, int p, int m)
{
	long long ret = 1, tem = a;
	while (p)
	{
		if (p & 1)
			ret = ret * tem % m;
		tem = tem * tem % m;
		p >>= 1;
	}
	return ret;
}
int my_pow2(int a, int p)
{
	long long ret = 1, tem = a;
	while (p)
	{
		if (p & 1)
			ret = ret * tem;
		tem = tem * tem;
		p >>= 1;
	}
	return ret;
}
int get2(int b)
{
	if (b == 0)
		return 1;
	if (b == 1)
		return a;
	return my_pow2(a, get2(b - 1));
}
int get(int b, int m)
{
	if (m == 1)
		return 0;
	if (b == 0)
		return 1;
	int ans;
	if (b > ct)
		ans = get(b - 1, fai[m]), ans += fai[m];
	else
		ans = get2(b - 1);
	return my_pow(a, ans, m);
}
int main(void)
{
	scanf("%d", &t);
	sieve();
	while (t--)
	{
		scanf("%d%d%d", &a, &b, &m);
		if (a == 1)
		{
			cout << 1 % m << endl;
			continue;
		}
		if (m == 1)
		{
			cout << "0\n";
			continue;
		}
		if (b == 0)
		{
			printf("1\n");
			continue;
		}
		if (a >= 8)
			ct = 1;
		else if (a >= 4)
			ct = 2;
		else if (a == 3)
			ct = 2;
		else if (a == 2)
			ct = 3;
		printf("%d\n", get(b, m));
	}
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mod
{
	const ll M, SM;
	Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
	ll qadd(ll &a, ll b) const { return a += b, a < M ? a : (a -= M); } //假如a和b都已经在同余系内，就不必取模了，取模运算耗时很高
	ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); }		//考虑a和b不在同余系内甚至为负数的情况
	ll mul(ll a, ll b) const { return add(a * b, M); }
	/*
	ll mul(ll a, ll b) const { return add(a * b, -M * ll((long double)a / M * b)); }
	ll mul(ll a, ll b) const //无循环快速计算同余乘法，根据a*b是否爆ll替换a*b%M，需要a<M且b<M，可以调用时手动取模
	{
		ll c = a / SM, d = b / SM;
		a %= SM, b %= SM;
		ll e = add(add(a * d, b * c), c * d / SM * (SM * SM - M));
		return add(add(a * b, e % SM * SM), add(c * d % SM, e / SM) * (SM * SM - M));
	}
	*/
	ll pow(ll a, ll b) const
	{
		ll r = 1;
		for (a = add(a, M); b; b >>= 1, a = mul(a, a))
			if (b & 1)
				r = mul(r, a);
		return r;
	}
	ll inv(ll a) const { return pow(a, M - 2); } //要求M为素数
	/*
	ll inv(ll a) const							 //模m下a的乘法逆元，不存在返回-1（m为素数时a不为0必有逆元）
	{
		ll x, y, d = gcd(a, M, x, y);
		return d == 1 ? add(x, M) : -1; //return pow(a, phi(M) - 1);
	}
	vector<ll> sol(ll a, ll b) const //解同余方程，返回ax=b(mod M)循环节内所有解
	{
		vector<ll> ans;
		ll x, y, d = gcd(a, M, x, y);
		if (b % d)
			return ans;
		ans.push_back(mul((b / d) % (M / d), x));
		for (ll i = 1; i < d; ++i)
			ans.push_back(add(ans.back(), M / d));
		return ans;
	}
	*/
	ll log(ll a, ll b) const
	{
		unordered_map<ll, ll> x;
		for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
			if (!x.count(e))
				x[e] = i;
		for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
			if (x.count(b))
				return i * SM + x[b];
		return -1;
	}
} M(998244353);
struct EulerSieve
{
	vector<int> p, m, phi, mu; //素数序列，最小素因子，欧拉函数，莫比乌斯函数
	EulerSieve(int N) : m(N, 0), phi(N, 0), mu(N, 0)
	{
		phi[1] = mu[1] = 1;					 //m[1]=0,m[i]==i可判断i是素数
		for (long long i = 2, k; i < N; ++i) //防i*p[j]爆int
		{
			if (!m[i])
				p.push_back(m[i] = i), phi[i] = i - 1, mu[i] = -1; //i是素数
			for (int j = 0; j < p.size() && (k = i * p[j]) < N; ++j)
			{
				phi[k] = phi[i] * p[j];
				if ((m[k] = p[j]) == m[i])
				{
					mu[k] = 0;
					break;
				}
				phi[k] -= phi[i];
				mu[k] = -mu[i];
			}
		}
	}
} e(1e5 + 9);
ll a[] = {0, 535977894, 824090374, 966355039, 844688201, 642370795, 275302155, 412496450, 351516858, 758344268, 410326949, 885337764, 833437643, 538941894, 271795048, 447629209, 717437611, 656631107, 247231186, 169703783, 990456193, 501845081, 925025543, 594413550, 207768571, 927850544, 70897603, 955296959, 694095430, 180420785, 203871433, 927818684, 239425325, 753017780, 983651693, 816765852, 173664845, 578432829, 189259009, 390230583, 523151811, 861880791, 82787274, 207422220, 438956898, 983406554, 784578299, 262392277, 804955230, 314170684, 971594286, 224938360, 819980744, 237762570, 647272052, 158541460, 71655539, 478183961, 69213427, 212142319, 40641371, 351615372, 109219314, 215457754, 839274293, 471635686, 656110335, 412179567, 353272899, 162747922, 323873941, 290750052, 20055930, 320615278, 808314734, 586254171, 770146490, 801987924, 375201768, 973354358, 64288140, 30045836, 18769272, 139134951, 340469322, 741089853, 152465175, 88311691, 984030370, 776930584, 752386088, 143304586, 142151017, 12478459, 756222391, 595709359, 759751223, 619533230, 854747387, 932441226, 461781693, 970915034, 339112813, 233122318, 648934547, 954293182, 9294418, 513109596, 278576223, 641712443, 812006606, 236047469, 859777823, 971307234, 333418038, 754598761, 645929752, 116833839, 764092397, 831022567, 769154241, 50123780, 580404024, 222562382, 770380141, 690451183, 798542315, 897943387, 621999182, 959543334, 705809824, 761924662, 618271603, 175560381, 459554926, 800485977, 976154908, 883751468, 567060351, 663178564, 991560128, 491047593, 290102842, 611204715, 977788683, 300076736, 440110485, 128448070, 272599995, 621882616, 35991823, 841405563, 315834117, 842371103, 326644734, 628558886, 363764462, 94337168, 304583668, 593200820, 653388070, 919332497, 853535557, 70967170, 644418281, 10057177, 727883679, 272875233, 819999559, 853196533, 933728966, 644474101, 704192241, 742100361, 156923211, 51925951, 786932390, 756305863, 256832282, 41977451, 241270931, 704304745, 161853865, 639452887, 620306236, 796649173, 570084350, 733217962, 424596817, 89482994, 187643078, 72123046, 283688777, 328410926, 915819492, 414576058, 503075557, 753692511, 273947656, 949430276, 179154857, 667665170, 809421312, 310285383, 817367942, 59845204, 593425668, 493434958, 495237662, 103836246, 357487940, 362996911, 30378096, 217571720, 566122495, 459978283, 303727729, 284658650, 459215815, 276334900, 587585139, 896015376, 251786569, 769883318, 864890289, 601597575, 994653369, 657908283, 437222282, 740878530, 961057946, 129521788, 692290590, 658425180, 984298605, 97150123, 746894851, 47086327, 788849506, 361249017, 239299760, 541287907, 850807294, 860898171, 687336666, 923561724, 930150083, 358652026, 685912662, 616662334, 724888431, 630716632, 165868823, 996486438, 872656834, 569237967, 893977819, 614250419, 380331209, 638376564, 819774113, 639083827, 326611913, 713016165, 77248254, 393469385, 925453150, 206447218, 35478159, 804909560, 109642673, 578477943, 48294188, 483932690, 745681781, 363982532, 885993424, 376057859, 48778413, 238969962, 852424354, 454657220, 932202553, 971253075, 752295432, 594754205, 541167885, 101006865, 735753283, 266240069, 946759297, 993546979, 648703039, 641751957, 957386564, 559892478, 866824724, 651917780, 681742206, 914860176, 995133426, 963518543, 122734001, 850773902, 718294984, 982077522, 747855092, 59306684, 328749091, 653452039, 791857315, 675650904, 285742025, 115141331, 302916471, 187175236, 794270408, 649299839, 37368535, 787385064, 358383923, 424078708, 974448295, 656528851, 325216292, 27142237, 569929425, 788751092, 341251101, 553452230, 59672982, 203066831, 728912240, 302769296, 589354447, 719681405, 861709693, 487358273, 331335036, 134286455, 852297317, 429539830, 915825923, 944087000, 839810457, 821885473, 300511340, 448201153, 289715669, 705492009, 244295844, 626741103, 141141115, 444190749, 606598814, 165007366, 786335728, 987363889, 595605499, 421264570, 391548625, 123099601, 133110210, 632196202, 423435323, 308333281, 686987517, 787634249, 476684612, 54218607, 157099372, 761420709, 986225022, 746783818, 496684535, 434700191, 788549250, 445459518, 256246645, 63600604, 402792725, 124701313, 319334141, 893021981, 386170341, 524461150, 667117316, 639909762, 260385300, 816614545, 388407204, 17718038, 983697729, 895972898, 510816595, 660743096, 80537445, 33702443, 599770711, 215982973, 438865781, 514238553, 843597259, 387249488, 600831751, 360334793, 11051982, 492235401, 347626519, 742680023, 149544889, 631055497, 309320992, 48186648, 736859429, 395532883, 429678077, 194070161, 414290631, 89120410, 450220048, 848180743, 616406692, 714115048, 493858031, 785681782, 271326458, 550169680, 38026413, 830640013, 493792762, 556039882, 859569602, 753148171, 227720189, 265978392, 825854274, 348046681, 78868363, 923496365, 518818339, 207845153, 804051804, 560972237, 279613699, 642976081, 495422354, 607741877, 111997445, 204905789, 474365739, 975599226, 668867572, 90503463, 32946535, 508779295, 39104475, 884740649, 623999720, 627988354, 952182330, 923541702, 745890847, 359954593, 632621537, 200697656, 588518369, 586335274, 925224598, 784556582, 257961241, 98664155, 114965313, 150375411, 504951265, 385959114, 202170862, 15564909, 942990332, 192404122, 48981154, 611429290, 878467220, 15922653, 235408928, 515694245, 991422427, 968660530, 200138098, 57556630, 60323338, 749754675, 258626747, 698436112, 210347689, 190712090, 264040999, 892426739, 645622403, 679891775, 814577040, 950922764, 306273330, 871429019, 322885798, 182327421, 448751091, 110439113, 598690201, 655610148, 693738261, 741320691, 424743909, 203071698, 30623192, 151893755, 167917706, 845569134, 362806291, 908139881, 288476812, 216667318, 364610414, 927352113, 634981576, 128472195, 303992638, 473726623, 766154459, 200057456, 192814991, 44014021, 986262473, 110399125, 876230934, 165226991, 886532912, 220815659, 751175480, 376586125, 705104812, 595503944, 807925431, 636393200, 472775663, 969989266, 991859731, 327138311, 194833050, 626036839, 564184032, 634694002, 706306978, 339089877, 74966055, 233460263, 130168828, 527081813, 23554382, 238085591, 775862438, 961391341, 756282851, 885747204, 120082446, 531414321, 941876508, 606981126, 20290804, 233300598, 921602884, 384221218, 798867727, 147732352, 838178527, 367790206, 120819896, 80131887, 969947930, 751341132, 135829164, 918375106, 279090978, 390581324, 815074498, 214843849, 396318259, 540583314, 126492775, 441249128, 374478559, 231694217, 948348896, 354522214, 355747662, 802859439, 76515620, 152091880, 418330817, 491200361, 358543893, 719064084, 527173349, 400233021, 454249088, 554533488, 796099914, 961682074, 826110169, 835615609, 962660735, 695277104, 340450132, 161599508, 504177220, 773577692, 128780530, 599789456, 730076360, 170187955, 673245400, 644066416, 684063040, 747507830, 39066400, 719062692, 813557250, 943461700, 907635938, 498275348, 199741191, 436559325, 305279385, 392980807, 32855739, 583375964, 371700993, 502472011, 993266048, 574126310, 577129908, 247413105, 399844213, 523283309, 311358165, 929357043, 141192079, 87263096, 701437036, 964252895, 320557665, 675809059, 4641230, 438391849, 448594876, 6327058, 620231101, 680663871, 385140949, 701367163, 3048293, 926376652, 966785067, 946674684, 385455238, 880515621, 675413906, 557238057, 97421660, 474539734, 950932940, 302410554, 361912768, 964365543, 544889396, 1376218, 695973844, 731847030, 121505638, 779996848, 455785895, 669050365, 841156489, 666708279, 356805103, 996449022, 834152069, 765043553, 663051135, 707540361, 490636496, 315846644, 698770573, 170980873, 783292266, 393906246, 965554197, 643174955, 25323455, 378300448, 844401367, 330427250, 473340018, 330176862, 575768688, 619587743, 182113557, 911325142, 210837769, 254750840, 778564522, 446501419, 135827819, 391185260, 221498305, 810787751, 969250444, 25913448, 175413873, 715847871, 761895083, 477347154, 229461411, 915926912, 162937879, 727872712, 625101369, 569222944, 814274904, 781870594, 128183643, 96273813, 502556749, 652672307, 764510684, 763901481, 172811126, 923094595, 888150879, 363756756, 653289877, 885626182, 459792395, 366651940, 318530494, 320393265, 992357679, 184338335, 231833782, 40502454, 448361376, 109154034, 952418690, 741933072, 211523858, 322246474, 585039707, 240101776, 386523525, 408752716, 641114711, 59432636, 982995850, 474707071, 649128826, 363425493, 828455436, 434285319, 360910918, 97361324, 72870590, 448448195, 833476209, 902688097, 142061320, 769702707, 851073141, 902437102, 75498732, 22069888, 779478152, 494280990, 585594704, 883340730, 210940679, 543438664, 362862781, 406298911, 85274181, 705348879, 751650517, 487588118, 843331684, 457437801, 903052749, 705079314, 422565257, 90525446, 305359872, 978921059, 869405151, 864436621, 393911986, 108573591, 970835579, 759711442, 141805881, 983464872, 424993528, 207914973, 295655089, 88913428, 916818958, 266074006, 642261896, 146913423, 628132474, 408052359, 71100353, 485727720, 445527122, 489658217, 881627083, 140780409, 899190315, 830864470, 772468947, 658216810, 425385691, 13021225, 521709800, 58712697, 816416503, 641011938, 241319198, 959561231, 176511366, 898929655, 913052764, 344448217, 129030603, 625002534, 593081664, 885581622, 748117063, 936922617, 210519037, 629208652, 420328991, 966437858, 101318167, 820475509, 766186286, 517101967, 67643959, 700601939, 32145692, 968206576, 479760933, 321383984, 754810403, 852513544, 140336964, 694853340, 270747568, 47785262, 386215111, 544798832, 109744877, 87739738, 957664101, 495396711, 74055053, 24155304, 542124056, 444419933, 222539400, 23937466, 442234270, 396738774, 341545364, 465275931, 918261767, 878724233, 236320839, 165322451, 701740441, 925088241, 608560013, 793733166, 894099563, 736108481, 373380669, 581351420, 241029737, 429127207, 232956622, 50598510, 872489402, 602198493, 215913304, 396282492, 529586224, 646058284, 357378034, 597029603, 505147722, 433207671, 908852013, 329531936, 598153536, 944809217, 779530971, 145389249, 71781801, 244353037, 457189556, 768558302, 617313030, 408193819, 865029648, 613540049, 802282253, 458847035, 389465696, 385020378, 134431810, 219985002, 282293028, 502475403, 435833664, 706882380, 421026405, 857595558, 796771823, 565440543, 271873319, 947003255, 467494122, 339767018, 430834567, 475196427, 366601426, 63186868, 617077795, 736255237, 936855472, 517614781, 252827955, 319308237, 55594511, 919262022, 468354212, 898439401, 738813121, 419001365, 337460738, 217562355, 621083368, 806183077, 959448842, 207560633, 42643608, 130112224, 982458698, 298840879, 949474252, 485802690, 441777619, 224639034, 487762526, 841577391, 589636276, 650284213, 29561402, 844657931, 69093925, 522121493, 100888963, 526681649, 848912276, 138416842, 820399304, 820060122, 827092449, 890607665, 502425826, 496066764, 391730481, 285531950, 450326370, 878943049, 901200148, 316718938, 554656870, 616470718, 410205989, 711087821, 384084112, 905137312, 343634705, 584506507, 947953336, 997395558, 627558568, 282319775, 818122866, 770363016, 497226432, 975180769, 165274525, 404223372, 541323112, 897742171, 762329334, 136351399, 911462385, 559079163, 766499689, 37189865, 276884679, 541924440, 645466886, 5694830, 613960055, 853739294, 967407136, 912720022, 871376294, 638218894, 161222904, 396339452, 331060414, 700308276, 676573575, 622653654, 55096646, 761357095, 586218831, 266131442, 114750226, 42347782, 158161970, 643720480, 189024251, 497196300, 705942645, 354772202, 109978249, 699813753, 899394768, 704839037, 732271238, 224234205, 424441380, 837026373, 83008420, 390398105, 182700870, 199736203, 485488528, 258637394, 854543367, 721595763, 370184960, 896557157, 12172494, 362877247, 51264583, 373454540, 420674924, 594933448, 857725319, 773439349, 902387562, 73305503, 823593758, 479333138, 727459277, 909229339, 28336581, 189470529, 379855146, 540766140, 681752032, 149423964, 988573926, 503962763, 973170495, 400993312, 628115864, 976774301, 61787779, 144610540, 353533843, 506469061, 330466811, 540802595, 517757846, 796389136, 108107992, 863044731, 93215481, 215519980, 860231048, 270366725, 284551912, 613904876, 94601687, 799539252, 426992050, 127622501, 402094014, 979772559, 944855480, 152946559, 990322288, 686002195, 578090593, 99163323, 551897774, 360659441, 955393701, 724978943, 726043297, 603053334, 851858996, 494820051, 921006782, 196526332, 567725728, 687922669, 870539617, 412563587, 697346679, 351088775, 943425099, 160939750, 187121386, 271734157, 646267521, 40513739, 894140801, 775135431, 584012984, 121854461, 981356989, 863082644, 439323564, 114887661, 190980483, 189007745, 672676904, 616905457, 616110507, 193394234, 145985943, 596222042, 540667712, 947340314, 811543748, 148248628, 670550493, 211443603, 328979878, 389369710, 166087123, 770059693, 941075149, 661153976, 591864319, 985104917, 144348967, 671315387, 664242316, 908633076, 337526124, 167046174, 876990296, 681378690, 666302780, 129532372, 576655628, 127509720, 682518546, 883758312, 698864809, 850689767, 76309359, 931355540, 419146335, 392880697, 591170987, 383975218, 82281705, 174969364, 737378000, 683128144, 398875635, 426782960, 669972654, 186031116, 955225798, 596152713, 174238027, 63829870, 360523315, 376435780, 950377578, 505662805, 708786915, 712919467, 527276649, 460626423, 243151977, 984302219, 765727440, 914431487, 934766821, 456493952, 352015296, 940127937, 676216593, 678893974, 906471825, 566028275, 968141772, 283095750, 36142384, 139561241, 747650888, 728567244, 917689642, 81808164, 312251173, 82102921, 779064131, 367984112, 275733455, 555373366, 842547277, 931279414, 511791167, 339001452, 247798845, 114048796, 227185886, 663591482, 907458609, 583659265, 163601459, 485556553, 810462461, 783429750, 698772624, 242588351, 48213629, 765502139, 640972815, 183446535, 947431032, 571453673, 737460732, 425414966, 175090498, 696001260, 114180125, 546448168, 721323815, 925673493, 535047327, 338136868, 140326251, 125728629, 317165912, 186869289, 793865823, 807176106, 505543238, 341105616, 185680252, 821471748, 458624047, 16149680, 818038698, 175886876, 246430113, 505605415, 873827607, 125522074, 760773233, 247794944, 10831880, 669409963, 845258236, 139184694, 726381561, 852469139, 778889338, 696720197, 939805477, 741933280, 231125381, 952355828, 76812712, 33676513, 449103143, 656104373, 409751586, 963119399, 651009369, 766545423, 692932742, 145635325, 376007491, 132400138, 831443961, 975375340, 112028994, 80718137, 264189778, 664751726, 58513535, 984133019, 628409358, 796690932, 818064123, 74654444, 314632794, 873322224, 249271426, 612297016, 578417693, 13383478, 202524735, 319123198, 286676167, 12319396, 693841230, 280069000, 756595260, 630138780, 254389485, 320520004, 151539367, 413051791, 120234730, 367510305, 982551828, 770311482, 30285430, 534525964, 984444737, 655352506, 538519850, 754472797, 413775354, 874683064, 687421626, 477596084, 252191322, 164897080, 519542241, 546219563, 567718295, 990760945, 638801677, 705332240, 285316678, 166749154, 495824979, 807263297, 77483925, 891552451, 756846483, 96757793, 832752781, 389305461, 396393948, 757126271, 848315712, 224975828, 648872309, 914041751, 409064774, 281782082, 54089097, 537489815, 735747100, 421836475, 411477899, 801688491, 769052577, 931017498, 167558299, 269068553, 254757031, 641533117, 80650915, 925610737, 543446413, 232508857, 946420179, 232446778, 665407982, 288952616, 53677864, 828235838, 384555325, 743904989, 124249865, 756657547, 938808851, 801829498, 420876237, 587955279, 738037253, 486182152, 481398255, 559516708, 72599875, 501596290, 519790542, 645262517, 520897648, 269378469, 989744466, 857799740, 477234341, 648342621, 511686970, 283270888, 53933683, 54603804, 771938588, 53255596, 454403638, 342967212, 37275553, 222302931, 187638900, 37014155, 192840732, 738318374, 418996873, 934946454, 105370551, 93107501, 647166289, 774414915, 846179615, 677415634, 89606380, 403748023, 578752586, 898386179, 256537421, 276064807, 280516677, 762051647, 284090213, 20317058, 753111783, 199560460, 222351461, 41881278, 731147610, 995031819, 686379693, 330174422, 123734356, 228808881, 789132194, 94789780, 235267556, 115514098, 768217836, 771967309, 318794738, 387656955, 228434112, 468760862, 116354591, 568492445, 643455206, 953203097, 512820613, 949174715, 538530952, 635409135, 746462007, 8733148, 439556793, 228253900, 520395511, 210693006, 590112230, 694248925, 975690112, 311582219, 7549024, 877805223, 622282846, 363425552, 681205389, 848895003, 330012017, 566718252, 88287833, 349485468, 396715691, 270396944, 634062063, 570311656, 798320074, 722753659, 384834387, 113445048, 525375927, 981540690, 790185637, 606525386, 500948501, 363362319, 661913555, 466051556, 171061392, 889527911, 234617807, 453227090, 163865680, 474341064, 42830446, 96964360, 442316846, 629925661, 992174791, 222217508, 994090356, 571593884, 847272490, 656985115, 705010669, 262107890, 87468085, 593676982, 987934371, 757587887, 700904670, 815386269, 731354741, 148916421, 865051332, 431884787, 340954664, 460871079, 266166610, 802889320, 900682050, 957475739, 70091506, 899934524, 811537641, 721426900, 504878261, 936264273, 551188689, 711539237, 804585772, 228676256, 182975279, 914382703, 674442006, 137908721, 924242683, 105973903, 271321666, 301690956, 191272419, 398703133, 748480752, 228596532, 249719186, 824412187, 695787033, 729044204, 60139537, 900070905, 157035647, 79270495, 27028258, 718419386, 244315263, 450242507, 309206196, 91283527, 658357178, 51696517, 546314215, 679157432, 275323138, 490449236, 627934007, 179117539, 345043400, 77773940, 130296328, 666642391, 737100055, 637719908, 261882079, 959985463, 460999381, 438594949, 596118497, 561651825, 375866347, 440540405, 93164894, 43991293, 458602223, 251607027, 392476159, 565130381, 111918035, 228545174, 455686206, 683011825, 399891833, 813331897, 46455595, 912340254, 490588826, 275028472, 447126766, 38271059, 205093065, 34168816, 476390747, 395843219, 718705489, 320988033, 832560675, 747933306, 148932930, 830130233, 133315945, 11961793, 581588849, 630786507, 463849167, 277645764, 351658530, 775331311, 275492427, 452701380, 968072613, 706794575, 406919801, 209547497, 841113745, 74874751, 548114968, 420693898, 509540751, 391389344, 3687795, 267548552, 55678783, 497415665, 455399106, 470095825, 87491840, 755139799, 98790852, 439285749, 986688826, 647303601, 648811204, 811801051, 576921399, 128065193, 27144294, 741022915, 571330362, 74474249, 299800442, 510447989, 815332166, 688543432, 76919980, 985178605, 511899696, 929936087, 343378232, 846768712, 524784360, 618472170, 194159676, 516925795, 330545054, 773782053, 62398921, 445257964, 508060708, 744946173, 927820386, 272164774, 262219126, 462369606, 154147230, 691519035, 890783503, 835884524, 585626049, 557003538, 223339626, 775035177, 137953743, 554406795, 110419232, 195339810, 900221317, 126134076, 550879743, 467251218, 542379302, 557247848, 333745164, 575175340, 549525952, 947810992, 223955555, 277597290, 579324586, 493613624, 156594072, 748841328, 349460107, 906685116, 929297354, 454724915, 339753479, 832417119, 399138527, 174852208, 778058655, 948718455, 183707074, 200595920, 698158849, 410826098, 800469207, 611036782, 245095816, 636469595, 692218585, 624768426, 631786258, 337666348, 205738105, 100154915, 413029612, 328674907, 624331569, 899567809, 977082427, 651387517, 751282890, 729044241, 837019302, 209094542, 751963317, 346673361, 644707348, 261212903, 426134776, 176854983, 852244345, 90407068, 561470080, 969099274, 873718305, 470768369, 480311677, 289410567, 405126284, 184928771, 646684718, 624938331, 191645297, 76500699, 12939575, 603066182, 154944509, 595161602, 720804103, 887257736, 822928763, 58177070, 87697423, 543800717, 967389309, 886247427, 361497709, 203069817, 18978379, 345565421, 786181265, 343150201, 242798341, 710023261, 350749588, 225045335, 893981680, 607714897, 839538992, 645164959, 694398005, 150239747, 116946185, 374166022, 768292155, 990784395, 235245632, 753095357, 195248316, 334054907, 140535271, 129662729, 977299835, 910497270, 338941399, 431759246, 805371779, 264634450, 244342773, 811896977, 136877229, 615538842, 246496067, 407878489, 551584494, 974746903, 608654067, 652230933, 71635673, 987116095, 198307382, 837999692, 806278854, 348311728, 142365285, 232232263, 63489553, 648265920, 748211486, 564019221, 673842425, 848414800, 820675319, 538461695, 767677571, 589106629, 279640838, 588596689, 868151654, 318076844, 644100073, 689740883, 95139824, 575106531, 110443291, 19574771, 724546048, 302787461, 46080487, 793889515, 448386679, 830122136, 442567123, 79690139, 850054205, 214307243, 206062049, 222562882, 585150023, 312092846, 177269085, 647974393, 528933335, 677122764, 864746236, 568081034, 406647915, 850176461, 820807392, 434840699, 244185057, 143350031, 432271376, 935426719, 52005176, 302268268, 396337823, 68946260, 19937031, 840407083, 239633120, 18497576, 718210017, 827663092, 575300994, 470348908, 193308937, 236774944, 33936395, 698687203, 215842436, 271353981, 506094739, 18671300, 101588836, 937381035, 937359971, 934948427, 638441734, 70669769, 134772493, 225165927, 322725539, 791808875, 769905655, 964637015, 924035825, 116978066, 573589783, 28786002, 235135522, 980950629, 550721144, 411627387, 399471078, 21871811, 955254690, 889092688, 721790720, 127218153, 368741430, 592929778, 946866611, 354854365, 250948721, 280327184, 134843872, 780965954, 674639386, 7431228, 290858742, 192499361, 633070844, 266436305, 127719727, 100081653, 785523768, 594533598, 582516188, 885432660, 231968403, 207081645, 832386728, 746993751, 691674856, 127139795, 911828683, 315641486, 370662518, 420817287, 263002023, 965635743, 517452430, 756149528, 924121377, 471692197, 378287820, 862912432, 45841717, 82832363, 850460852, 397800372, 24987753, 776086528, 376688155, 342901286, 701928300, 955082702, 474293982, 184923013, 445464838, 570859466, 246996294, 89297066, 667974373, 166793788, 695694386, 699092173, 454394668, 512042167, 361131037, 774423023, 522948916, 268577787, 233207266, 127471207, 857108363, 450385976, 723909251, 905980790, 134864308, 735962259, 980582157, 167155509, 95085587, 546390175, 275825756, 229788184, 478925627, 709455210, 857741065, 409962989, 153371424, 104810919, 455692668, 219279328, 684023805, 23084765, 568951481, 60706024, 943697305, 501283275, 773229264, 8405576, 546892400, 966465901, 220408478, 318768416, 475899191, 570021109, 426910529, 332751415, 371108861, 452401505, 452999574, 908585516, 143750005, 64230287, 83670828, 642072256, 416284874, 685032679, 22279329, 28391757, 255338731, 713203138, 427428023, 27285690, 176408696, 517200842, 630834411, 661237493, 205750778, 131164548, 322930008, 551088577, 728858852, 33315042, 736842748, 555047890, 242451650, 634478049, 434557853, 100943268, 893276803, 679167294, 803372116, 24444522, 958383453, 422494235, 691002230, 744963689, 770542961, 299764854, 52941536, 551659178, 877927480, 504692707, 511142970, 68614189, 711855346, 368498769, 232814129, 101757716, 921490501, 573728674, 99047005, 108843450, 238346402, 284834847, 164652675, 600583409, 201422679, 243549549, 653028985, 898600040, 265661265, 320927308, 875588422, 100822420, 993188208, 441720936, 511080447, 11505586, 864806325, 203974488, 15964793, 408558525, 485174535, 127055365, 562495221, 968429232, 674508830, 451789688, 436132986, 226916289, 549876280, 250274649, 968306413, 508160075, 854844564, 585837061, 829851673, 953897675, 420878540, 48150512, 466685463, 256377113, 161629899, 444235114, 851900210, 109742978, 454010790, 967678792, 344317272, 187884962, 805991816, 3684397, 95008247, 328306662, 674915240, 126104277, 978490719, 233579760, 141300325, 187389820, 86899150, 859823579, 637626425, 127933378, 762381219, 340301736, 578447149, 10334592, 312348147, 371199069, 64078276, 445993572, 705923136, 873613147, 350689843, 874965390, 553925699, 485272497, 211382971, 26502103, 147462305, 309725450, 714233131, 924879808, 882966373, 888100529, 417625496, 204520333, 84085980, 703358257, 451048798, 98130691, 654331087, 450225027, 592908866, 169687823, 720552954, 350927768, 501427530, 793160071, 803746085, 85807311, 761480854, 379954088, 13238856, 464152420, 162621872, 656799203, 165762879, 977944007, 690705997, 669042404, 529985279, 220883664, 763932031, 827600799, 180225689, 36456717, 928801986, 342993789, 782230098, 678438484, 553408061, 493918209, 215326078, 245614847, 381074498, 5105659, 947330995, 357677329, 72645609, 673186063, 659952288, 441920260, 682418353, 12985886, 740324885, 78407403, 430122360, 978535891, 482964054, 425540026, 838257325, 298442613, 839352747, 492634153, 764990807, 794847287, 738498821, 67532035, 232099079, 839913658, 448625689, 422234820, 36136868, 341137607, 440654049, 397879864, 722305723, 741192043, 189306152, 880981519, 219817674, 293574406, 373048270, 39629465, 912649527, 791145559, 19010747, 49241054, 457586274, 907449701, 448457545, 320265472, 551485945, 765694093, 260833054, 913964357, 551252924, 441458484, 495963888, 663468029, 234444422, 275314096, 147564771, 876473937, 595818415, 235927193, 874740059, 344980128, 820742441, 967800835, 798384134, 46546429, 738636780, 211064550, 372734842, 180190843, 431867257, 443596036, 299208360, 954748310, 116145826, 645767316, 656128259, 873505132, 804694687, 513909217, 554063446, 286580571, 790865005, 172846709, 598668923, 117649322, 27528194, 994256231, 819883632, 153835877, 942883875, 523126739, 509963212, 49692722, 103296887, 24260221, 574255213, 605613703, 584545118, 244318867, 736644368, 899003073, 798497909, 166883443, 115422182, 314043965, 765028144, 557468326, 288356090, 642175961, 594414514, 394423409, 539789519, 548047434, 314668874, 164432026, 806691274, 329718606, 885404356, 79544139, 24347936, 601019074, 512223063, 777425384, 875676202, 545653172, 904979645, 935013564, 163597867, 147408614, 29471699, 965263277, 763068286, 632696753, 821881344, 289490269, 699179159, 233607708, 986393620, 940804175, 819643453, 925508873, 405479746, 976410425, 491791601, 981980901, 741264918, 71000012, 239441712, 824355010, 849341590, 787022275, 931779448, 981974503, 757360726, 200087380, 334407799, 965969964, 980890328, 352479682, 117135143, 887576599, 768285520, 49281569, 278218865, 948007895, 696784720, 300677311, 947906138, 689505826, 225986864, 674121750, 616288271, 87947845, 203938412, 895817557, 579574880, 724503432, 233316300, 676012392, 516982067, 228830809, 135237058, 138462620, 277117100, 914170056, 931942734, 272294120, 180939207, 160876569, 376285377, 78926640, 332660007, 450451579, 779407395, 76275622, 194930738, 773354049, 590372747, 17009065, 632722805, 276728609, 659714229, 790242012, 410412270, 454156822, 683283062, 754853382, 657384882, 116605624, 404913157, 752697052, 161375531, 127524685, 833561569, 607942943, 353625518, 599192937, 776739494, 144622212, 800563442, 117268622, 948969982, 143171989, 245218698, 915878901, 812184757, 743441683, 66603796, 951207978, 693123517, 98168949, 712402800, 176850210, 618063870, 185927098, 511467581, 647585859, 528435292, 148229838, 992847307, 29733182, 989862669, 602373553, 45659594, 17054889, 297324694, 469897693, 132409589, 882763277, 97800670, 845019091, 916148016, 291320762, 516559057, 183737854, 439487425, 560580476, 298741723, 58867654, 713376154, 823482132, 589312527, 313410937, 100379775, 751710732, 901613738, 963997930, 557015121, 416432880, 974941219, 487090152, 688398201, 216976203, 349867091, 642509910, 281181838, 373690873, 944704966, 570674184, 79062477, 70394991, 59190112, 837249379, 266254335, 808263792, 165487576, 463161732, 555304299, 907811567, 149400580, 332989347, 899209361, 361007045, 746831588, 133941920, 494513121, 860360782, 6107547, 405596321, 427504859, 647283849, 751878775, 729557203, 161867991, 223771012, 973084573, 347653710, 86518385, 27643131, 132681823, 722122835, 477330360, 933701367, 707919662, 725308428, 498652482, 96935470, 30387920, 574911116, 944150639, 197870397, 942119117, 493554302, 126159151, 970021268, 528018965, 719078308, 348714695, 934255326, 84997961, 848794026, 379558015, 78061439, 602544451, 741613942, 968459454, 865269956, 439192570, 921701285, 205432154, 415085654, 374754615, 475244826, 865981973, 270339013, 94589820, 26852766, 851752452, 395935612, 701056225, 574264727, 414295527, 898437592, 61089409, 268130614, 908934281, 460709425, 513650894, 632188865, 41302485, 791947727, 237016872, 33537059, 215121050, 623523779, 231662468, 611969339, 758538490, 734385845, 493655224, 680698968, 868444229, 682276882, 964431569, 871645648, 745119372, 925744546, 571919048, 160808246, 64600504, 185685560, 829339115, 86572992, 907643335, 845180836, 279568634, 411622090, 468105675, 277260934, 167361288, 13724945, 461057396, 378474804, 265727603, 321042055, 741235429, 581220039, 343584452, 499357741, 923242118, 481187646, 564805157, 675769747, 25362141, 333589529, 317497018, 341071842, 531998632, 412560362, 792240299, 72069116, 134285622, 279884974, 974017881, 812567553, 452673630, 912619512, 185710546, 304181005, 140753091, 439523009, 988846503, 213378949, 679005974, 338479197, 615614858, 983103748, 170963999, 662117732, 545202379, 134476162, 85077221, 67698701, 521015569, 765762761, 21644546, 891938206, 76087750, 455868257, 754192730, 956575790, 197265099, 7369264, 845350582, 726641037, 18232321, 271825891, 836664325, 75750711, 498385863, 598975493, 601432768, 954553035, 190483523, 988127495, 142579166, 305223514, 216772016, 275562355, 750551603, 31521017, 767529842, 414969283, 617725183, 638200140, 73360649, 988956634, 435222549, 425013624, 226129881, 761648127, 160077637, 205656984, 408301000, 940254707, 681502105, 298444107, 536714361, 514655969, 222193678, 802411591, 441267755, 421190379, 941028103, 996238245, 688688961, 310074223, 613886575, 939632147, 701702893, 472528473, 277514133, 494157380, 534784321, 937006914, 847239919, 120969002, 814554911, 530765606, 461624189, 731639095, 206638577, 5510068, 414580746, 554116714, 613364249, 954312443, 286789104, 700768339, 474838916, 846053796, 285703636, 529361401, 586708797, 512878973, 451514966, 184308809, 517871869, 851550587, 123701229, 419452466, 355054021, 90369742, 475098687, 601118938, 50837747, 757446567, 586556156, 335016141, 680969735, 817481175, 779550153, 380296035, 830101265, 782969562, 627258822, 637871889, 340559430, 898472510, 93061391, 814356690, 565797762, 110042378, 202291236, 131242527, 308830548, 67383049, 777114723, 496004269, 186445807, 414487038, 292471254, 252982167, 29796366, 886474181, 858026244, 860899811, 542707932, 203712394, 383125092, 504739434, 364166596, 79528394, 557730530, 433158251, 595827921, 896675967, 798222444, 249340512, 412411726, 974532605, 341779575, 212634171, 550291482, 748939208, 111844308, 571856950, 385281095, 778188604, 280443697, 478223930, 42570456, 973125271, 329819799, 536018752, 651569634, 960586758, 710473354, 587335388, 124927991, 590218479, 796100115, 933831614, 183497162, 716604001, 645728417, 455772280, 358524063, 939832206, 455815853, 828939900, 509052887, 635879190, 617619454, 842647159, 5543300, 974647289, 86995691, 410563763, 282584918, 52135685, 789860541, 9031458, 749190423, 876884590, 22517285, 849843967, 191575812, 423660217, 553299504, 747159224, 865376058, 828372668, 800305892, 247227567, 750471797, 276540765, 336607555, 621294688, 87706522, 449434222, 71024397, 24036823, 521099965, 524050981, 119019760, 422771005, 157444889, 732468582, 697736611, 578832162, 388225775, 760537071, 640414296, 649693721, 478707903, 680217916, 79097377, 658912961, 854547086, 67273608, 525530578, 641749427, 508783263, 111443082, 521394577, 530121840, 760321377, 890219323, 268317767, 762781259, 41393344, 99359429, 882714897, 649820218, 560899902, 156800965, 912622814, 18287246, 206682597, 387224486, 863966775, 125884324, 910706534, 606495272, 925768825, 342582443, 139325669, 789812868, 733218696, 870673092, 571034912, 930503472, 246537906, 934674831, 883464742, 320634351, 96221301, 146222912, 872665564, 653482238, 970941330, 385513697, 986948454, 867785662, 463269328, 921404819, 416147547, 794414266, 636725655, 723426061, 168279038, 300978776, 897634912, 583942845, 343202894, 524927677, 315476451, 412809037, 382315013, 251297443, 808589601, 924921234, 571010280, 585407210, 663911841, 996522611, 996477894, 70139986, 720652165, 649807041, 731971947, 895538445, 136579760, 418549101, 614324792, 348917594, 73116746, 71488177, 312908925, 748190567, 238184687, 453852990, 374165358, 339558744, 885509602, 616225186, 963637990, 920813223, 469531880, 24970120, 493527743, 395111545, 492777438, 708625830, 693531265, 139170274, 581575247, 583006642, 709179610, 523722355, 273630931, 89429360, 466173709, 442077373, 816546919, 173130316, 813631559, 223947052, 195026379, 523602754, 499741082, 486122894, 143927836, 259664169, 973040261, 855229433, 527721080, 302513276, 106655842, 11872902, 639854180, 759414845, 832347679, 909928461, 657759922, 103935900, 712703744, 83562468, 643793638, 230219473, 8564250, 844070353, 606670077, 12006276, 874605780, 669962723, 352367700, 9160294, 67000138, 993639739, 46763903, 688309497, 981055690, 855627870, 967519917, 87469290, 465947892, 617749729, 934429814, 12438603, 819155187, 603005300, 993104816, 787130475, 926756617, 132506294, 3307956, 62599661, 957531087, 427044172, 394645805, 903071156, 25010902, 930351597, 153088392, 79434952, 112732947, 243755902, 947440796, 107826562, 819021623, 85990537, 745888874, 331024304, 216557291, 920245716, 737381835, 634900131, 710035370, 567514017, 531729131, 951787282, 881639728, 341195781, 981742631, 114561485, 246268056, 717753447, 832903889, 212879351, 108321201, 614834096, 24667806, 675001033, 986537612, 107717074, 214250653, 158063891, 49511586, 658729252, 966116833, 71467881, 118039140, 169213588, 403084391, 516767833, 69241105, 560336138, 14434649, 635953495, 982045787, 472827327, 145165402, 80578319, 837070943, 967432191, 94052707, 419952790, 519205454, 534162694, 111251010, 485523840, 357877015, 539270155, 424498300, 142690303, 629946453, 677904334, 32517419, 551583059, 96830957, 287053779, 386816478, 362434866, 725359777, 929988122, 775923301, 243202308, 482383810, 298319461, 484389021, 183634252, 328927618, 299485119, 676196578, 119453610, 297598737, 39054796, 348760651, 23786991, 498631694, 771337380, 91796907, 568022316, 907099951, 432380642, 764999063, 549341861, 735215566, 323468102, 790890339, 407822220, 739918819, 585155855, 123368729, 279801117, 897396844, 200648776, 626040470, 502781223, 40835110, 522622132, 905808004, 977323037, 172977473, 260945606, 795882341, 718737187, 824723366, 208248073, 670744049, 140424565, 763841224, 321798392, 309739710, 11448017, 732125302, 435747731, 431388852, 40921557, 172907767, 364751567, 481101509, 363926649, 62920422, 919045497, 774069238, 169901778, 739963918, 28730763, 772103919, 481050479, 543871439, 669037062, 266414986, 681375929, 27456887, 556884867, 984186895, 460805493, 647307572, 289517487, 126014883, 642497270, 559050336, 504905159, 713712321, 9258829, 35995609, 351814125, 767263929, 882789146, 949183788, 214012132, 7926997, 534371630, 76138202, 615144994, 286127036, 757911478, 788073176, 460764711, 7942677, 248477773, 369146547, 681148503, 802468564, 556116246, 37963123, 124264919, 591934225, 522969106, 6023779, 250237267, 19945579, 98089898, 323124942, 950048446, 870506641, 608536626, 622765429, 309099182, 126719701, 791173264, 638228980, 59405634, 606047868, 47853434, 123056536, 234183362, 8717582, 932982778, 895397320, 641700680, 116927617, 782811614, 626564502, 227069791, 470827021, 239703247, 775409180, 249544087, 751433429, 905013328, 943291448, 921964388, 414080243, 531493378, 415484581, 148207956, 633299394, 428957531, 632654007, 829093060, 416909378, 620549233, 15372991, 37997754, 129240184, 361528323, 32405707, 321598168, 899288497, 742936259, 786591836, 721679084, 577966859, 44308618, 917085276, 50201868, 418859422, 22967639, 897169920, 570019013, 921597271, 181483082, 21068421, 358615997, 139155683, 161046781, 586433195, 706227352, 120681748, 773179105, 518275626, 822779812, 646413497, 335977629, 808721897, 206554913, 883491535, 564371797, 898314892, 542657689, 825876795, 875702264, 794565642, 799835993, 294845192, 432264909, 723785105, 515627902, 606710792, 60275834, 684122937, 232711245, 831049509, 950174999, 404231657, 786266269, 979565154, 149061937, 729778884, 171734614, 848305649, 493306260, 342275603, 969711471, 119033460, 243684075, 18990533, 873846829, 546413542, 46697909, 380775125, 484388474, 151764453, 756174975, 840831718, 494718000, 65290424, 28796116, 554200486, 865783388, 713298340, 779395929, 124588216, 954158780, 563962520, 27917967, 680496132, 172427662, 57350873, 958100177, 578689088, 772545405, 905985271, 641440551, 881049136, 541565056, 664255811, 357822934, 331789063, 613158114, 479584960, 364531667, 777320500, 653357782, 473599879, 619402697, 203981059, 35888845, 106519146, 195076573, 832062864, 926607164, 918795261, 995386170, 170176872, 231075274, 254097938, 559251248, 208921170, 189246873, 803952983, 27496470, 188606152, 454355756, 21674388, 76812391, 252748609, 425506864, 217230620, 499265517, 482796139, 761326742, 851233811, 514815321, 746058485, 413099678, 865168949, 875818159, 606258928, 318484782, 711160872, 121226943, 816716408, 107558313, 624998043, 564882214, 457484055, 55513225, 981446734, 764087641, 502363869, 519871818, 501910235, 858236082, 287455254, 352860013, 869941866, 628195241, 648636854, 379405569, 428075574, 238540122, 943375677, 618907307, 388223358, 656332572, 661213858, 12317570, 172703201, 166807186, 342156587, 422480475, 529530481, 934741588, 368001670, 422899115, 566150970, 394664520, 950626119, 611761296, 809783198, 797811127, 457362356, 157089341, 753897022, 629943325, 593781026, 424380239, 944120681, 472659574, 866525251, 652914179, 887703665, 170728375, 776090842, 57027516, 886426257, 723446202, 985374467, 457568320, 89696860, 985610497, 379172735, 747610413, 181994106, 45090123, 374088524, 189601925, 308208403, 90540897, 874925049, 272336204, 170869675, 280191119, 149182401, 955129676, 700755804, 227832541, 671901873, 879434704, 376529331, 473385786, 870282797, 557732857, 25685886, 674907682, 893113380, 70467586, 861011370, 623683552, 25072048, 536323185, 425477875, 148883066, 487336778, 990101971, 714044406, 616005672, 15597727, 558172878, 244355819, 786050813, 330595546, 701704528, 537775021, 693347265, 637976448, 525327757, 499249066, 530608074, 741088391, 140903729, 935226892, 66194874, 707484341, 704117658, 28126556, 561304778, 383439300, 833881732, 350104149, 57373943, 849810365, 77876006, 67575779, 504636044, 318816421, 435772143, 512411014, 40546398, 840417837, 348886025, 10954294, 340420945, 306885513, 388653830, 616136120, 991756002, 599108198, 925244933, 912019920, 610110995, 725508891, 724171439, 74504717, 795481842, 532108862, 90021304, 406979546, 134299656, 468019559, 923759629, 944112622, 471101044, 446558828, 431658406, 961868516, 944732681, 459595972, 661319816, 653982350, 819831198, 665967923, 81684216, 708723223, 379519460, 816885903, 919469592, 301649913, 55010167, 720595470, 477806811, 299690079, 30596722, 647829104, 887594543, 237797866, 382399248, 393119305, 528213555, 673726565, 259889050, 390573304, 104448919, 112402605, 238434225, 158658245, 126249096, 715084942, 421899158, 634962906, 495515753, 894619779, 725048658, 689783456, 357046928, 63546233, 677638921, 98068132, 485707286, 425922222, 481555447, 471610519, 284357719, 328193516, 782727366, 612604675, 519620828, 736401481, 393179906, 409000157, 715434095, 792115653, 556837914, 55330021, 283718640, 391928837, 108914134, 588410197, 582330373, 630636921, 92669847, 982129170, 935534214, 403488211, 316820728, 793782559, 32615676, 27632805, 365919715, 31595126, 44241096, 826999338, 21857652, 569600323, 989839194, 904633697, 188897515, 466140342, 407085930, 735501746, 144277693, 467347863, 876690880, 876942954, 38802526, 766241120, 653184502, 881565716, 42151934, 719770386, 404381511, 223787885, 156231964, 817789767, 313054723, 147698786, 377830980, 168609306, 203924215, 83184227, 436843715, 933163331, 297207872, 152666623, 310805377, 473604811, 714883846, 535845900, 93068527, 758430549, 614602695, 816512676, 495109154, 140869195, 575261796, 242852997, 742951228, 686171318, 766527572, 897071602, 104732835, 193865551, 227301981, 819994501, 393120268, 841858412, 499729667, 845998947, 272645956, 382815332, 616323132, 481815183, 352426479, 438387279, 305924902, 966710238, 693906471, 945505000, 4855351, 410367088, 316120999, 201232728, 21834133, 995094674, 491460629, 722969139, 651532013, 306333297, 343056125, 321685019, 684759746, 71364803, 266053561, 993416007, 551244302, 890389546, 139972939, 810080465, 802540911, 100452028, 849779206, 722099742, 770408901, 444637071, 752540713, 688349236, 450768879, 436645440, 494389838, 288927864, 724036928, 171627941, 757380341, 182699906, 884990728, 160080347, 453519441, 105016871, 381172504, 966258398, 928936028, 689022443, 80650416, 16324704, 593523173, 739977998, 352204507, 963349059, 594137490, 316379162, 96160944, 91546351, 96174755, 591829233, 46279788, 965740578, 168199537, 164650875, 672206738, 662446128, 658825937, 706091835, 182821818, 957499466, 76269573, 456338032, 856091063, 672247206, 887495804, 757409494, 699599504, 492248644, 162840027, 847546912, 498768829, 117105589, 242914221, 482651238, 181187723, 113383701, 756147819, 853606535, 627278625, 496387525, 689552707, 166661932, 601957860, 567742525, 222941840, 193167024, 310466488, 230862517, 932352482, 83860573, 322267462, 396179661, 872534762, 599992024, 236727806, 108218251, 365739267, 871920832, 832247509, 402196822, 609817174, 470475438, 472204461, 181886928, 417451317, 174109771, 433334283, 552120166, 868635383, 395839442, 814978397, 175606255, 885352158, 85247393, 134003325, 741212882, 590145318, 439180710, 862806501, 210841140, 809174154, 585449043, 723796245, 171349284, 651289188, 397248469, 848964078, 100232483, 477504819, 672560334, 694342667, 226434392, 256006766, 583883549, 657556292, 745125395, 992684767, 636433153, 222299434, 395936605, 781638014, 115008918, 494193815, 357167017, 197894999, 286159652, 653566309, 637928090, 115804922, 819756721, 823451320, 151749718, 109272389, 730509043, 259857227, 604777007, 244898704, 595140457, 497270335, 478333176, 647794714, 741065, 779803426, 871882197, 861826929, 227816140, 532838801, 433187886, 20947397, 81993714, 964279245, 947986458, 238011356, 100692121, 202850461, 759011131, 920262281, 44166458, 75318496, 461712156, 931441535, 299056366, 965515981, 418873985, 432509712, 556374576, 613354457, 386323936, 620927594, 854518125, 595332866, 135671905, 828696550, 956599741, 452992601, 581217596, 606584283, 657775453, 310958165, 127514163, 28126222, 820122229, 445076544, 217460081, 727615667, 399013075, 7819900, 884425803, 192926176, 524742658, 208000619, 669494422, 441799248, 694917332, 318025240, 680720370, 202628297, 75934137, 204357123, 231657529, 815107813, 589722945, 275795682, 738126501, 128190383, 562554798, 187005153, 365026865, 934303641, 485139295, 99607230, 702977284, 101234825, 957946616, 719493858, 773682237, 351754698, 257758509, 98502160, 187579012, 689187787, 902185300, 938838549, 815646837, 369424215, 424012203, 257214345, 123405209, 1875966, 353961013, 58115919, 826551109, 732618410, 70922975, 727928362, 466417199, 736019622, 770907021, 897619232, 198940293, 909523650, 348644837, 82945777, 936889854, 355102304, 551626643, 601129579, 356333513, 57092708, 581631607, 258729193, 716043689, 991529720, 651970480, 269736848, 987960005, 793562908, 816163454, 198527931, 189379674, 946354993, 535163687, 507087390, 535959075, 701553325, 886390268, 718210219, 852848414, 968586019, 26388273, 702635082, 189691575, 737805450, 690178573, 620667461, 19315296, 170001611, 985391834, 443865652, 132203802, 742831257, 104727163, 944691470, 436136778, 590525736, 17705002, 284765999, 114826915, 57400045, 620795409, 718468828, 546232581, 447042722, 487653493, 654230632, 5645784, 859327139, 222617138, 449558581, 567000767, 816973427, 510671249, 914779508, 654562057, 375057624, 533887984, 253936778, 357472638, 193488807, 962050633, 323432047, 679662057, 717659117, 358623577, 777969315, 494839682, 21048884, 575716553, 980355362, 11532130, 381372965, 430759304, 18113229, 627816838, 652790050, 660547757, 493497323, 722331639, 89987189, 201122599, 125619737, 461493358, 841041809, 936886620, 543289171, 153979304, 655124591, 97080778, 373395714, 628042148, 873154642, 471284766, 72623388, 680164037, 392731422, 932467921, 377899307, 530015687, 485025508, 490272340, 551325748, 295117866, 466465194, 906754535, 837640342, 101848302, 267344394, 236642119, 405041730, 265858377, 564530579, 460551842, 770019318, 833065247, 82851459, 567309849, 382897305, 913221984, 346839883, 638698066, 691367804, 568381408, 282986353, 324550737, 554938063, 922114137, 322881749, 810015197, 970460708, 825583410, 368617509, 31194454, 187455284, 130218478, 664150932, 936204756, 180926005, 898171517, 582200362, 306198607, 732331861, 272463263, 973332055, 862102559, 663464489, 758515009, 782576170, 145735132, 366329355, 33204291, 141926468, 303106313, 925704351, 576512088, 180692342, 180868612, 786684583, 73457257, 459145016, 306058842, 131404771, 799570142, 83924835, 396743544, 509767264, 282403730, 86913816, 875369074, 766561850, 822795068, 730262120, 385454012, 85658903, 956411906, 628899213, 761610209, 565940680, 2683515, 406962205, 971939645, 364991803, 557383344, 789489156, 930796691, 707603571, 435813139, 152306853, 773585682, 273878070, 162824176, 710208162, 645291475, 402728329, 413233888, 466580769, 389730373, 12581345, 281536576, 944085324, 464790108, 593114578, 971797549, 739376635, 867913125, 503965734, 977666716, 796596398, 245835419, 789074338, 619227194, 297183559, 362685530, 549834808, 853730671, 782288268, 594766671, 729629676, 324309896, 573324579, 648689823, 225960550, 346880094, 995109026, 880479088, 204020383, 528385920, 352830981, 192602467, 430701406, 687182540, 468164663, 844064793, 125098581, 411593524, 948744873, 304949003, 24445789, 300672201, 123556282, 253882866, 126895472, 339449364, 206184070, 585406918, 657874877, 451948118, 758902095, 752521863, 737769422, 362515876, 426826118, 450522906, 23595820, 741555942, 850595047, 125417227, 559771978, 367154019, 600305091, 320569053, 933083748, 665674296, 692089370, 730412895, 540544113, 770073210, 880060694, 655506456, 492204879, 49832384, 360335439, 854541102, 5479602, 65899752, 150841639, 620648340, 617514299, 685916728, 41189396, 755795696, 303556245, 143460973, 30016163, 980595946, 890306542, 544067365, 617745219, 383989941, 679493998, 395116078, 403635595, 440883774, 873504166, 353717791, 577900966, 517116314, 892668432, 941814616, 60749991, 137045872, 326310456, 296348094, 259719526, 104600211, 652479290, 805459349, 318012936, 237232802, 549744597, 27145242, 987680668, 390585976, 142412746, 32611126, 517802871, 953828808, 725838352, 844746653, 798001175, 419903167, 14162516, 361070376, 348355427, 957510669, 235971579, 11153190, 65925285, 311377885, 735025254, 286147167, 222676627, 154829455, 149206355, 291058794, 959085390, 772690322, 198638020, 5456040, 600356403, 495544219, 589541792, 508769519, 166234167, 551196509, 566602852, 43726829, 949847903, 113008542, 386103127, 103699030, 862903189, 408733313, 639174225, 558361797, 516180407, 309484205, 583571081, 90621889, 655996759, 177633580, 137869740, 734178020, 646957814, 918326463, 874978368, 994501537, 562282664, 219267945, 809904846, 605723735, 958378567, 534910443, 372385582, 487969202, 886719817, 803886188, 107605599, 683607551, 696479354, 196678706, 185343762, 254569819, 124335591, 649559981, 259765195, 48171378, 853017431, 576213738, 825807287, 75356760, 98465520, 82920954, 807046965, 845016674, 9360695, 683507093, 128404529, 352635471, 397751283, 527223630, 54239602, 592231287, 540871911, 732665764, 657930801, 658301809, 379575329, 427823322, 846497480, 504413474, 637845504, 998068853, 638343769, 418987238, 977491063, 65603416, 532751032, 892940483, 572775183, 946616238, 490015382, 305543974, 148819153, 13292322, 90628218, 481976034, 762079403, 852940254, 622194541, 975290250, 602285447, 121651578, 35496108, 296395513, 121039308, 230931665, 856909162, 355243170, 785365318, 419470471, 254721750, 585810791, 200677716, 544939393, 546225674, 604498735, 448053740, 343704756, 312824194, 725938065, 185333187, 927202813, 525893351, 453256560, 650404739, 397270000, 538493192, 548410790, 896228741, 268319210, 429886494, 525894080, 814981542, 856939395, 674588867, 497617365, 232620786, 845396278, 233920358, 543934154, 430136555, 698250032, 958150714, 311583563, 159951055, 852279441, 654999175, 444308042, 115939974, 665874980, 666883813, 943475829, 894003182, 315840899, 688426986, 822257270, 51438847, 266321407, 240162053, 777965730, 834505747, 91936311, 461677620, 610340158, 377891621, 719893813, 41396112, 89632686, 499357082, 399968213, 921565459, 106207199, 6688303, 704770037, 920941954, 477569980, 30109766, 267167808, 410143994, 33436459, 502902973, 621863714, 240948055, 7220212, 32047713, 486174180, 664771605, 29750974, 639580194, 322620343, 527615551, 528194775, 571253806, 789299485, 68606583, 996703692, 451711242, 229946776, 177244764, 979706127, 778894706, 47324279, 369161301, 626100086, 73829937, 291475614, 751018837, 707795844, 400654914, 949598807, 670087311, 889920019, 234239306, 182420235, 225434192, 554432398, 748652096, 948238315, 852683450, 566263221, 144636841, 898124458, 924225000, 103545148, 194440, 748387120, 325057864, 460503687, 40064509, 272232510, 444537790, 378371105, 670595023, 347738860, 723913711, 244109823, 894462251, 352267162, 54744465, 539494216, 695881249, 235830769, 688348364, 982840246, 369981200, 578734710, 270164491, 106504061, 411391422, 645869380, 839292032, 299819513, 972958723, 908344969, 125809395, 813841533, 959155016, 402393586, 535390887, 357427661, 654939410, 392826738, 230386888, 958467087, 348035662, 456252926, 705688058, 318199732, 13703865, 959377043, 197978349, 216973899, 442688067, 219413802, 186602303, 297627880, 652374382, 114299846, 200829319, 760842629, 476623910, 270401091, 400730512, 756334440, 7677372, 713855184, 58671268, 783661916, 86527286, 389465456, 298295811, 870898635, 286816495, 850037039, 595159898, 161090893, 778495430, 777157688, 671723932, 939017593, 901514496, 289059978, 824547969, 806276497, 770873803, 301397502, 269049504, 541610309, 949307011, 682664513, 333799046, 458892675, 577286423, 285267660, 388591162, 960558955, 336176225, 365335508, 337758161, 456706381, 904788611, 665720416, 947971484, 896887840, 3977841, 714607853, 206672828, 737803470, 316801867, 425426197, 283820990, 340321459, 303797238, 439435739, 492102603, 356149042, 877894854, 372872901, 391171325, 633621208, 948480679, 679357565, 888110783, 720826641, 436449972, 271546078, 521651156, 25340937, 819675389, 842747882, 761954383, 974452306, 588274587, 1196359, 81048409, 467643263, 628078786, 31975978, 412854443, 660059262, 488181862, 627434319, 432548134, 827153808, 107519013, 72493839, 771016867, 270251728, 2185090, 733106454, 894682602, 130422755, 940998464, 718361871, 500437999, 962364052, 599834354, 373210544, 35480784, 556982336, 161422076, 342235352, 984485138, 406501321, 687073912, 230895414, 856480141, 855576059, 794961493, 783270593, 915175400, 910841091, 15285687, 525894477, 541055059, 789521752, 871018840, 561532527, 870935207, 305004227, 291581906, 563767847, 343744807, 263069066, 70377815, 903738064, 715239910, 155772141, 360377467, 795430273, 529064586, 466172811, 390027774, 929956995, 573745272, 569215425, 954537851, 158301372, 796474826, 423231753, 521670976, 403851602, 177723682, 992920985, 768972530, 616514122, 979118118, 90519179, 451228213, 787189364, 14483636, 598826263, 341398336, 877886259, 926418624, 83756612, 214431898, 309193676, 219621798, 272283907, 662495413, 42581841, 836962130, 915832941, 68965951, 947671634, 879696575, 491293751, 367326864, 405791562, 345708050, 213095458, 739823120, 841997454, 956351750, 873976611, 951513463, 777369254, 515427020, 597653543, 968425969, 483224592, 794326279, 306451820, 232268172, 659442160, 802949335, 933829717, 149708345, 673009855, 88622745, 902708424, 398930759, 508779892, 656290573, 281698864, 465649645, 674113331, 359127427, 259779038, 445378770, 325636257, 989853583, 680906151, 50869682, 882670783, 721320704, 99269649, 695720900, 218424307, 27901112, 645961048, 600640814, 581955125, 435011928, 628160186, 304561915, 375578463, 310152750, 883671098, 707725924, 545255943, 736163311, 947522223, 375426509, 111780558, 119301357, 621850804, 845622317, 946251397, 251451631, 402905521, 384087647, 731052319, 354683639, 772305422, 816471202, 300665279, 392253406, 154150600, 522447858, 584259118, 952710152, 57945949, 905096240, 761951113, 569835297, 185322791, 388789280, 755206099, 273068911, 535453978, 712834713, 184044363, 126468051, 137083916, 408661771, 380149060, 666932634, 684393294, 73819676, 586661439, 376238744, 279066543, 15131714, 369674874, 874289905, 916044171, 156361068, 360265411, 429579685, 961115805, 859034462, 230392695, 844594882, 532988373, 462553062, 143770449, 159146172, 311192512, 443658546, 890002681, 417797661, 215269416, 381590374, 917384549, 354167894, 848220108, 738765906, 905240607, 735680953, 953668491, 380892333, 406585239, 323673419, 724458288, 504522685, 243767907, 419494393, 525106733, 672295733, 246751778, 323612167, 848937983, 364088966, 967668845, 180096293, 819302036, 983594806, 495909285, 194461777, 301406165, 981146019, 547224611, 308948166, 99936292, 701481857, 499041082, 847424579, 125174746, 519896889, 677850622, 804011110, 749313368, 990575311, 251146725, 428003028, 173635066, 445001913, 297800531, 664804228, 485593924, 840466347, 159945957, 39619755, 78775728, 859378044, 513106286, 75363812, 230630505, 299921556, 974433966, 954319767, 171535929, 705225807, 770764627, 431837033, 203842854, 735051745, 520177816, 439237262, 557839590, 818448589, 848443424, 394186687, 904885426, 243534225, 910124200, 356850650, 813239234, 971261461, 451929944, 247196977, 145048009, 197789174, 9728566, 152174068, 629786130, 709359943, 857579977, 284874277, 9505202, 86593579, 385034967, 784238937, 158042899, 273264629, 417108400, 913738514, 658621824, 640534062, 245756211, 611293117, 624550468, 967575404, 950686348, 240394948, 74623996, 404888179, 333355952, 350183407, 374992655, 896474133, 158894433, 938552130, 558376811, 200015490, 874432585, 330647460, 776789402, 839122935, 940607456, 616717275, 938135055, 181490864, 103335496, 868327000, 478005916, 477129743, 8776978, 319212776, 988314368, 62306238, 742282233, 237664304, 40400979, 359229326, 880781966, 299197053, 197217624, 122745178, 693132621, 735963507, 256775878, 201065997, 174625982, 600586662, 806563798, 419307966, 486560226, 688580460, 351439726, 942725420, 711471101, 497150589, 974225777, 617208217, 298208534, 405461010, 707301528, 132419347, 702426166, 97650185, 958685017, 135970861, 265022074, 398913808, 310750070, 45999514, 938628189, 787106173, 274668276, 711196588, 635821885, 259636997, 37843129, 86057869, 542872475, 660153987, 159136591, 839306642, 120584565, 396081096, 553511710, 128513463, 807929789, 207853656, 218519830, 552757759, 92466427, 760396773, 287845380, 594164169, 812366121, 240694859, 586235102, 459501866, 600723496, 503504299, 555844139, 320892244, 863603994, 677279092, 489540128, 643700475, 16676514, 951552209, 247323388, 88184708, 808605890, 346174111, 168497807, 435429921, 69215708, 521732195, 720366101, 820211927, 736044449, 821865554, 474454494, 444090554, 304094415, 338535120, 109779886, 319899924, 123379653, 710098032, 534899613, 163788730, 293892023, 968373076, 523246993, 97402901, 890742210, 257072469, 572238559, 393227780, 69697227, 184093920, 36779091, 802282344, 455265269, 553863447, 578225490, 362717824, 645190820, 998179937, 874311786, 563999445, 389767637, 964370206, 201387669, 779789039, 333444611, 593463966, 370001898, 197983313, 402690157, 313375069, 898262723, 553331298, 24188727, 837733205, 339626468, 63259735, 651683562, 189245338, 220707297, 442628224, 514388206, 214519326, 19564133, 15099996, 770559988, 78612200, 468017505, 750530896, 77892510, 353249407, 554518374, 960445374, 70006142, 334280988, 373851272, 672079553, 633008852, 552103159, 671216742, 414769437, 640534063, 649548795, 987185149, 218624178, 955563551, 978630772, 201392852, 716460005, 305446345, 311177784, 582246929, 26519225, 333379590, 931795048, 268720551, 848712297, 239769303, 51947751, 74442950, 302321591, 832558, 180691972, 573760021, 439040331, 595703238, 407038140, 493042359, 569952991, 40725296, 582489599, 840167147, 337249322, 866853052, 848046294, 341056030, 800165373, 634755169, 684607727, 956253490, 99903567, 575183472, 141434303, 274612191, 166786298, 649125272, 133451819, 816414528, 479612121, 637750522, 909780825, 533657727, 924642939, 61733359, 7906278, 867903765, 484753328, 327961433, 886943307, 706291714, 29243187, 425779143, 664536784, 959787803, 109304422, 524758149, 189596649, 282871059, 124748503, 97863224, 915774538, 805820743, 412592369, 848414468, 556700278, 747162497, 662993731, 741151909, 381519648, 1534607, 448251696, 714614940, 147375568, 203697615, 696471703, 373412389, 550314861, 570139603, 470219255, 489033952, 475179920, 924524260, 252302808, 219776327, 471144732, 781930992, 191612011, 178777790, 902239111, 478598048, 833974319, 288068991, 896065578, 583745502, 280868915, 710881345, 915578463, 371157546, 842076056, 799225324, 32168554, 129097287, 123737513, 365115426, 754865440, 969085300, 962022477, 421072236, 439544430, 534671263, 604940740, 109340936, 801902913, 897832115, 204268605, 792890408, 780757556, 882406224, 514664724, 204301922, 64478834, 427940833, 622195311, 547564931, 21535192, 634464111, 748760184, 871168931, 943880567, 874491881, 141991829, 262452459, 288509686, 669764173, 727797184, 712130694, 465313844, 932784021, 191796783, 530738217, 991779359, 150446905, 576429675, 763005721, 648555575, 944060994, 724510849, 161558853, 906750721, 55005295, 410023611, 560163888, 25340592, 128531682, 759933693, 801136899, 274960529, 860331044, 473936835, 756316375, 920897986, 611754978, 24242086, 992973524, 864910484, 225013966, 709111801, 760778849, 29723222, 586227903, 489621226, 751831988, 906432034, 786746869, 24550173, 363001859, 526024363, 467615207, 282323657, 433612358, 105029490, 864087136, 20298125, 307658610, 483994809, 447213889, 997390984, 715628756, 872333369, 885101486, 973866985, 217859130, 349899531, 342903775, 354881898, 122640803, 518859201, 631466256, 400982036, 231000428, 15967015, 755191758, 40008359, 446084854, 952984204, 244402821, 640817245, 428613762, 181349743, 759930930, 380453220, 293438540, 121716802, 673934618, 810674541, 465113259, 908018220, 72699075, 73434891, 218301519, 566020694, 788867689, 98418852, 569135772, 254454349, 387716923, 458723173, 804002243, 548876940, 304162262, 464456321, 736855962, 566929511, 927097233, 146083143, 112180874, 40953531, 39540480, 551294639, 101548969, 253676383, 298524911, 990935157, 950545851, 943136168, 526593479, 393581995, 409606111, 538779845, 681640519, 788148683, 803765607, 140232347, 272517552, 842008226, 964293229, 493320907, 670373830, 910751533, 62506574, 966778231, 281756336, 35133537, 896611315, 19992827, 306034344, 915201645, 510659048, 137999012, 531580699, 795840918, 475735132, 286683924, 438300848, 490610179, 381661098, 391006573, 943848904, 445197996, 572870653, 732145950, 663063547, 94827174, 970523276, 788902493, 255139725, 842269867, 212705007, 37415430, 760110941, 114863539, 866866494, 722666644, 406621100, 945411602, 912317678, 692735520, 371269799, 50896086, 795086777, 350056249, 461883008, 108025011, 419921443, 407357734, 380119047, 974156087, 159129763, 906468164, 369158496, 102151752, 792546286, 89593129, 905378760, 190965463, 479663437, 332629693, 28135111, 825807715, 645825579, 916438251, 923871888, 28831065, 159035553, 701782112, 302475340, 3502716, 351227577, 141714112, 598128888, 392308700, 461448349, 323398252, 17712330, 945295494, 998021558, 686801917, 518440140, 79438982, 153895036, 720051270, 598798675, 579623743, 543421964, 624758836, 572464124, 572543480, 441851756, 210621274, 933420989, 186649494, 912878631, 801319186, 64229194, 246563180, 111055113, 995464090, 223186994, 354772096, 745624766, 484725546, 658769272, 758704650, 341836933, 276930966, 245777743, 605695315, 716392470, 560456956, 107430733, 469502913, 876570059, 896877776, 748491528, 832868512, 197827089, 412852972, 456532229, 557251854, 496408001, 403901397, 82576438, 451519994, 188072914, 622950443, 332642559, 824941199, 198682430, 954725522, 258346108, 698618159, 15023741, 579472075, 624080760, 496707030, 212129351, 114020006, 982294619, 643915666, 60853473, 480478267, 219638464, 186012366, 878915981, 33764021, 435000476, 453019698, 99222912, 480322533, 886891567, 161932774, 441877144, 164275101, 329365655, 924710851, 875275634, 974071045, 245768728, 602271443, 265896121, 927612209, 997022339, 870185423, 313926668, 375066093, 953029985, 715692768, 897855615, 271407115, 742834127, 784334136, 866568161, 191129457, 774318066, 330794452, 52280747, 504474260, 640139474, 164294441, 873729664, 681925845, 606670101, 862749765, 863494048, 972627087, 333166904, 16312072, 811210003, 561515473, 579280783, 81548857, 476763946, 863974711, 222646398, 797855398, 698694264, 912878638, 528822180, 525805541, 334009020, 471115336, 153899934, 257785008, 664096811, 70238072, 67710099, 563693336, 483234708, 990740616, 757185772, 650790929, 980125939, 440567272, 110759249, 497861888, 715972649, 88374768, 390402221, 284060992, 613302892, 506841652, 390085312, 518449453, 820330918, 779924507, 464727679, 607141383, 668078839, 585551048, 327062818, 718081008, 602327757, 404439657, 962934836, 510160286, 522518903, 207780940, 640863630, 239640928, 74142402, 278819494, 182204774, 134924172, 317641430, 351301117, 119275588, 745227920, 756448431, 772175713, 732619261, 375476108, 761539311, 905403331, 885423228, 153075130, 74682232, 643525209, 149918060, 618209919, 983548459, 96772667, 783630280, 207814689, 162748802, 17120805, 917258406, 360133424, 236166612, 28615467, 846380962, 13691441, 346810059, 992283101, 430486724, 31742228, 649794521, 599634582, 841643728, 817733948, 924519095, 1713554, 235516499, 485393054, 39610387, 157301330, 669079858, 576794920, 5643878, 106196065, 562013010, 622283908, 500478905, 308537431, 127418924, 504733460, 177954640, 290869048, 941162109, 591183839, 887622047, 524767369, 789345580, 207376863, 968631217, 879705848, 667016378, 867049341, 933742340, 253655784, 904853508, 389365978, 553503600, 281869105, 131218755, 990254355, 36331576, 885980789, 737330069, 275523662, 754854372, 177942702, 488882336, 130467693, 583876601, 954895141, 945212408, 111439216, 763639120, 170349221, 570387579, 749456650, 581569979, 85431900, 760351311, 182342418, 358692566, 720791171, 16942396, 988279010, 298412574, 92558951, 503100068, 438040047, 321665742, 617553309, 97562332, 179760104, 19911211, 333037122, 524760437, 113137085, 490249272, 255918728, 327592550, 890043654, 838677658, 371579418, 555626495, 709540909, 454176930, 532182662, 85309167, 529199728, 228350749, 666748248, 683693014, 439928666, 863790560, 687497372, 269679165, 431422354, 535966609, 45845074, 406441912, 25412980, 62641644, 489432632, 250759867, 139242165, 221339821, 487521951, 293239920, 104679120, 61116100, 35561788, 505774755, 510279461, 391700108, 89430693, 399516448, 699051268, 956307626, 485056025, 315633906, 602183166, 268139032, 571667683, 725399896, 754609701, 542254609, 358888434, 671637994, 755242073, 816838944, 789379235, 265823075, 367177264, 537503680, 546116233, 842929645, 515295831, 573458623, 284333863, 741250994, 295417810, 274983217, 198617969, 406593144, 919481416, 146952905, 331709787, 409815298, 363334034, 4589475, 15221831, 662479246, 522458938, 49386903, 175270586, 960845806, 168893864, 109946417, 83104094, 987334844, 598236819, 918800815, 155177695, 683866659, 231126277, 905364850, 303327406, 369935934, 646522437, 376441085, 277587394, 300167251, 184268364, 62382656, 351955507, 670848541, 960730643, 256484516, 273731051, 591016259, 997121808, 61001745, 493991431, 764313242, 198826868, 325173643, 374923853, 924540532, 757720766, 358967509, 329246138, 622267325, 153093689, 91788627, 445837978, 482210349, 822855419, 348371605, 768686585, 829366730, 688020656, 491686151, 728382894, 390694264, 553819247, 234671523, 155241237, 905394222, 558424963, 218774849, 771617744, 9488009, 758719900, 471117326, 190381089, 184360358, 587193427, 683925443, 218411870, 578339486, 966305648, 95226273, 220235971, 660992806, 474310680, 959932433, 432439687, 195797722, 874385664, 256878839, 159418196, 80336534, 836781277, 525227559, 681799858, 623782025, 321566227, 65407001, 432079726, 407063397, 933570348, 611974138, 981704054, 909729586, 299934321, 571632471, 210291095, 705655608, 379366101, 646014144, 404381238, 885404284, 436206512, 757317286, 639133006, 230049416, 587594508, 58705714, 860393356, 356463742, 124137391, 399753227, 33663762, 269091564, 870951080, 461023152, 706993145, 284193525, 580641177, 521968303, 430719573, 509564677, 346096340, 95516352, 439625543, 624239615, 120492986, 135488946, 246990449, 246009577, 619894686, 499280536, 976897364, 557298603, 131619560, 153708672, 663701610, 928820767, 544483297, 516471237, 905396685, 731229365, 295527436, 137560387, 518345024, 534168541, 131982666, 552760628, 389811200, 213294662, 725801762, 608881777, 444750110, 200094011, 610831863, 301892794, 245773958, 503287272, 418056619, 925537935, 635689342, 695464128, 356267402, 442973344, 875252523, 260653594, 115313354, 411324615, 439934229, 365008837, 443770339, 124493798, 337997121, 819569973, 28744860, 371064291, 342145842, 24566071, 802925016, 501509375, 755714647, 602127104, 586345035, 100606537, 52282426, 470947369, 49390522, 755222257, 348539848, 570421677, 866035798, 422963737, 353372604, 720402743, 893799322, 548003810, 5875305, 633724317, 661516213, 928246200, 242386683, 488181177, 325535776, 254825492, 651371890, 867055548, 396639511, 665619318, 608935698, 867257501, 93629896, 786130227, 291318311, 654900170, 686510429, 661987505, 210724198, 751165320, 68422439, 996812367, 777589543, 398475806, 221702961, 572199994, 664296236, 888886430, 68347684, 67780035, 556051675, 223620594, 890186742, 324381240, 466450209, 854792642, 422069081, 780071589, 675106, 894657597, 446239234, 919597951, 262903322, 962537655, 445686475, 469363119, 691043281, 155126384, 12849484, 710301126, 234072715, 282601182, 523625872, 396454292, 478609037, 184310525, 857451990, 519382956, 523163585, 845330556, 633002054, 454361542, 23561548, 631776179, 843282224, 390897733, 113213468, 821505554, 144095800, 158308751, 333381897, 332692462, 341180637, 925013695, 771677638, 520552305, 953339245, 604038532, 400645676, 412234330, 22398781, 940675979, 955456883, 74007008, 456250696, 73549193, 117374309, 373894028, 479417511, 745240429, 203693798, 859026012, 687087010, 301642988, 208062630, 805766196, 527132828, 244184900, 796799222, 838800804, 510027815, 116940724, 11824133, 667504872, 197877556, 722815582, 211936038, 845315241, 351551627, 432008417, 505445614, 997806431, 362080799, 560967391, 84580270, 942578230, 467442822, 680346866, 248284441, 134252134, 872564877, 1443973, 618791803, 760761715, 232671973, 39605102, 988394609, 830505955, 103942328, 140049559, 605679282, 503015692, 609988293, 577713640, 595699960, 573232434, 975161739, 210269609, 7964332, 814457585, 323072367, 447024434, 423352888, 456310893, 603549177, 84023306, 684592233, 844619492, 590196187, 845787995, 363690943, 888655092, 323939989, 749566123, 415783764, 548762076, 868664650, 983189512, 498183941, 501760705, 847363993, 111916938, 326286165, 34906435, 479703084, 855673309, 779068312, 621145601, 844848791, 368581127, 646530957, 952668720, 977966831, 375869240, 730496759, 848084680, 393651242, 545113918, 976259457, 753440819, 152391907, 497757369, 626662237, 848414166, 273390376, 800525442, 625153503, 105403290, 851090853, 497736415, 538606207, 92704654, 97208515, 665132611, 281746182, 472834857, 638517224, 633809825, 83688247, 84888850, 82138310, 718621048, 908684851, 887224855, 863570471, 672276706, 391901218, 488513172, 280151139, 823951589, 360416932, 492006602, 396214958, 676138704, 642265743, 837519036, 222922006, 917787379, 986559292, 2544450, 49134348, 68989491, 836025273, 459863463, 620718037, 347853251, 794708721, 477264341, 555635654, 806557344, 712618680, 429685069, 363471925, 301647210, 683726554, 631333455, 710514283, 239557795, 102796155, 552828970, 166925668, 614696695, 554474067, 58485087, 202292249, 551663586, 97665383, 466908548, 256948720, 192439287, 317505170, 880710587, 64608408, 652485525, 277562629, 655858517, 895974596, 444287495, 16932148, 776768132, 680110990, 184470134, 871635133, 746565817, 497002156, 265017936, 665499415, 190338603, 392608186, 634226827, 771449015, 646892135, 2963954, 644920695, 281655596, 60688775, 7332853, 161334459, 553280954, 75383576, 833711732, 618083985, 364413904, 240868879, 66630942, 785518085, 274911926, 451789744, 83384144, 440319190, 351481831, 210054854, 349449361, 735046635, 549466157, 660909406, 78957733, 300198400, 785167834, 703134858, 382583104, 964969456, 801235416, 618635278, 202508266, 339660919, 331543768, 778419175, 894906438, 232145772, 436226673, 194385207, 368171854, 207243561, 699821526, 85221406, 726744496, 919841752, 354486927, 140087575, 735206495, 42979000, 146500777, 633307581, 579576128, 926435935, 102749725, 301056664, 406879679, 81017824, 227193459, 294703073, 662747140, 485166873, 613163686, 967600395, 632043401, 418890365, 821702474, 20625696, 226719606, 785492487, 978890224, 846905922, 500828396, 623281564, 939773115, 896473091, 503469423, 633822384, 301412409, 351543520, 156072556, 277625149, 513147548, 54295462, 149264808, 315401732, 522801715, 633703214, 111475197, 576881969, 594874407, 962541154, 718455053, 17952818, 736560918, 675753897, 60098158, 993310962, 483085192, 913515551, 767728098, 16226945, 836045083, 219139903, 728897397, 719095285, 268421111, 418829819, 30798184, 288670512, 848432411, 919477205, 770333403, 196071527, 698062714, 706146333, 370619893, 253049894, 632008437, 928298263, 465562981, 259458356, 401616862, 751369297, 832553322, 453307687, 358677207, 653889687, 804643138, 89298917, 585809831, 890469336, 73015001, 864072885, 356379296, 211248846, 475264653, 397582767, 978384400, 461247123, 169950658, 894456078, 568864142, 965776016, 885747340, 550579896, 824703374, 358050921, 178224004, 447302957, 937416727, 783974346, 412768767, 670808061, 131887455, 726637491, 196883139, 863842790, 183314422, 463278233, 435991811, 105066330, 902661793, 507914695, 539902076, 910771013, 985474998, 448610993, 984174998, 472949912, 768292326, 678485678, 630383493, 685694214, 819617807, 788916507, 888012694, 46044967, 348714957, 778224691, 826754112, 783855687, 420125389, 960083865, 589886999, 788665994, 24515658, 534859343, 18557001, 335764737, 327725035, 629465176, 327370042, 521789187, 579738188, 191951447, 967115010, 169037461, 408225877, 357422967, 910438414, 682974964, 603408950, 949991077, 882128327, 338466288, 720995663, 231985463, 739557990, 980634918, 819098066, 478320961, 323469818, 76608997, 150202791, 960746214, 802383954, 250854943, 956127681, 763200827, 313029197, 139728329, 536319529, 18638610, 830697629, 883027341, 933157426, 901206492, 215536119, 925138563, 988706812, 192178014, 501259506, 291779472, 309013583, 668065251, 723876645, 599357096, 157527465, 958132710, 84568336, 228251235, 948993073, 965719169, 414889803, 986093880, 123339648, 584646483, 589183964, 669378102, 573690529, 502290786, 515857198, 478877108, 136954242, 668730855, 369168286, 285406098, 76190478, 61847085, 476803336, 760025371, 179197594, 375050228, 121154250, 415511120, 125048263, 543920459, 507871897, 693911671, 745742200, 245456533, 992756039, 124892364, 918423062, 813822499, 714220207, 882876666, 761527904, 67404075, 973120311, 598244583, 578609110, 973311389, 674990879, 407371639, 862461254, 515046479, 900267282, 584752400, 897012686, 69585188, 74605515, 508625815, 969796949, 78062785, 316801988, 816085103, 275627053, 41696269, 299548794, 329625759, 377313745, 925003833, 843865629, 336832116, 219820972, 777804955, 520932492, 573004457, 747985067, 824833746, 52508321, 872424946, 988684140, 494767118, 695591499, 412409416, 471668177, 295716726, 208160221, 101223757, 561841470, 795339250, 149429087, 707326119, 628592510, 704523512, 456874078, 464246252, 645392451, 501929449, 123843245, 223753242, 249594926, 295930943, 116145542, 58181657, 607730413, 170783695, 439537623, 665576157, 562539516, 274445771, 14525746, 821853386, 230074294, 323022804, 246559793, 921197041, 349241289, 964099757, 63612254, 421194517, 540763683, 151151292, 615968781, 759330147, 977215927, 873981688, 702420846, 580926253, 948346805, 553115038, 851626414, 651176260, 286088746, 135729974, 901668436, 745139620, 554493977, 763842310, 13510134, 10450804, 557353049, 931154740, 12137000, 250825140, 950871911, 690692306, 862045023, 618721030, 889811450, 220978637, 145795738, 115769279, 179008066, 205065021, 829046694, 210416387, 599818528, 214912856, 776266427, 700640828, 759490930, 522456087, 611118650, 885199719, 20168637, 838488410, 911257612, 775253061, 373953507, 919700489, 483036981, 661402735, 546678713, 256303712, 371871372, 552350903, 672629127, 68450035, 304063899, 809095671, 232852188, 553388441, 587011410, 205211105, 857031201, 216040002, 68648913, 165735014, 89637305, 719814508, 908974118, 715122793, 229460388, 840744291, 494077542, 514570018, 130236779, 903128149, 915121274, 716257089, 285829834, 284105445, 281610987, 455193962, 784076101, 713939712, 272562331, 235225985, 860247895, 461067088, 285876882, 994915853, 721697259, 851602630, 588326700, 702879851, 93068756, 263959120, 237049412, 398907633, 798593315, 471980459, 349151830, 321495235, 541019517, 335213040, 255156728, 359571151, 432390646, 800395629, 52262928, 659638575, 526927509, 370692809, 556498630, 873286969, 993887302, 13623045, 369005530, 922484893, 267653437, 568261786, 899819102, 262842279, 421986753, 827094823, 790231819, 910387041, 559333161, 844216831, 315927856, 496601721, 816610825, 36749671, 267660672, 505724913, 609628668, 707289414, 687801576, 44569860, 660899120, 275093921, 883543425, 1062897, 908156333, 649374731, 498536125, 551077069, 259864206, 751688633, 614665962, 7656819, 180722351, 639165030, 203169886, 619474798, 622236129, 438936590, 930476812, 787313273, 961025431, 211733453, 228021234, 59294360, 398274600, 79327436, 790265632, 409182618, 901314525, 955165584, 924733674, 769816644, 129036500, 404676784, 543483623, 785355437, 959898368, 242709240, 459621168, 898008038, 521436583, 799458760, 595071647, 88464878, 245747067, 466050146, 140348673, 902260799, 388370521, 874400441, 948865239, 556011675, 73769572, 677246593, 271509594, 837351890, 936608756, 773984941, 459747347, 768409266, 952701939, 778051295, 38857946, 525593917, 918501395, 767353855, 619488064, 226010491, 242352927, 959522574, 185621558, 393266961, 261911315, 443986079, 474417595, 335099884, 688673597, 55889289, 397045251, 269771738, 529251815, 456773454, 185762400, 694894732, 569937234, 899219412, 219211927, 579284975, 303754230, 585640630, 932417030, 327923687, 811374934, 572663571, 674825212, 77891306, 841941105, 155173964, 987870768, 613616007, 320565860, 233044430, 3228038, 263959627, 766960395, 853354509, 389715566, 924545800, 384662504, 122931740, 228037753, 346633189, 491659468, 74891848, 203123651, 389082679, 642383719, 509947846, 572844956, 511467455, 450374873, 553233367, 478676868, 109041939, 301047459, 980038001, 324637994, 966581363, 13794452, 93368524, 207462011, 735835520, 972813352, 507336677, 454903987, 280607119, 659207136, 111049277, 398459083, 92540150, 543130437, 160603177, 866600079, 23440272, 377159832, 14986769, 322688065, 408990641, 588573074, 349918028, 956406916, 340217859, 794507050, 340017287, 25412092, 863971300, 231809299, 343977445, 376944740, 937795736, 235040396, 588137121, 843182855, 731503824, 754036815, 788942205, 453531685, 421829702, 759360021, 748838961, 627128020, 330472193, 948413674, 622961819, 320481499, 498233171, 193606355, 939176863, 954726404, 448793830, 137208384, 767260748, 108373725, 982462153, 437651463, 176192435, 155633754, 820736058, 831549876, 88659573, 698161559, 266974163, 285392609, 132505454, 868257883, 638405982, 23533516, 420487127, 569822148, 633945119, 909601200, 811508335, 710212977, 826598462, 464077842, 877750752, 651732256, 5507738, 979953981, 415870390, 254571550, 396534243, 114498737, 607760418, 367156855, 8531374, 506569244, 967355366, 958578617, 211735691, 187695075, 674388711, 560541357, 80210899, 410309505, 835782229, 182884308, 597028548, 123437945, 761007237, 143357172, 77586445, 985492613, 39465313, 10444105, 579576592, 556140822, 605024812, 460247688, 675377058, 14945352, 673240458, 869388140, 153010201, 752741633, 992309189, 382163817, 83799060, 6354974, 791800548, 791255690, 236782434, 992188895, 447067378, 940576537, 805728560, 7138858, 310055346, 893545218, 848527732, 580715592, 188371935, 757282658, 823196419, 12960288, 291652678, 514850869, 922359603, 560597611, 348345253, 854986422, 63196214, 64798524, 25681924, 948671797, 542154855, 525475418, 42592377, 866633775, 391772890, 443292814, 790709218, 907402055, 711588663, 351157172, 228641619, 635732820, 48785923, 287427561, 124989701, 985966272, 389859023, 509586133, 303544733, 347307562, 584267458, 805809375, 906824388, 178186467, 335971086, 439281429, 254302793, 508945359, 834535959, 449329259, 426717512, 564798605, 580757863, 546843520, 723767935, 711186786, 463505894, 890897092, 689215785, 423969156, 622997197, 215444946, 872133394, 512933669, 2152636, 122731916, 95856504, 989161250, 762830034, 114143994, 986575945, 281533542, 919376657, 321335591, 397300690, 886790005, 801134929, 95715218, 365987608, 249776848, 944550396, 212887510, 994898025, 842530395, 405049115, 714954022, 380811988, 522872061, 621611908, 466261719, 258651441, 175671850, 255412245, 519267384, 598452451, 731192350, 797820382, 823200339, 842838117, 822477520, 130860908, 723675651, 67500858, 197997080, 44003452, 616858383, 616107229, 984015043, 355125358, 818001857, 378404211, 333588830, 417665949, 783242054, 674149844, 341824385, 744051420, 742848555, 462890375, 347500178, 172807750, 84326212, 6947838, 901797089, 187469124, 525785362, 677805988, 419611277, 948420949, 358826522, 171527776, 882406094, 952429901, 649635238, 39137973, 558542282, 630053870, 815280670, 93423904, 919861934, 698460479, 907009055, 101131928, 51011223, 853749333, 398118602, 270066117, 374899095, 718435060, 733294599, 611776431, 505709523, 462907004, 936983563, 430460412, 516734416, 191502371, 627625137, 265282339, 526578270, 449518192, 712140726, 282615038, 278500232, 18774660, 517013709, 845277268, 101762052, 326880127, 660625156, 685710711, 136911027, 155738765, 629154182, 18273394, 92198734, 978300601, 466873157, 584349640, 413532164, 786162240, 831385374, 297513069, 966090131, 448916051, 83938740, 195971336, 485141380, 750109423, 204217937, 849794923, 54572665, 610363458, 189680264, 947370178, 913405747, 551099517, 789836465, 132001992, 950562100, 454158557, 157141904, 62573993, 133731376, 109239251, 213639840, 645754347, 562534016, 959624377, 562883485, 871071543, 584242820, 5946241, 864340587, 839543350, 817321180, 754376407, 556877904, 654039902, 863173388, 610264276, 739112199, 726867451, 76346179, 99424183, 448814391, 201817141, 341061602, 515887097, 811986671, 841535639, 683813892, 498997571, 20204997, 446892476, 188213374, 263074111, 433340042, 313069877, 885914635, 263907230, 162422794, 754177278, 372532354, 817916764, 106849142, 536816795, 436823112, 124926459, 312684068, 976683959, 667006071, 302815127, 503787062, 695221300, 354471685, 139345719, 664923353, 266531205, 602090739, 298500204, 549323563, 955048624, 691309734, 695615384, 579115163, 54967279, 268340822, 410011851, 883576456, 472511998, 163026422, 328377061, 589393111, 803262068, 861878852, 891229460, 353295059, 611780802, 951004426, 479401177, 620112229, 563092319, 932636462, 19806101, 234339608, 703714556, 897547753, 317075050, 591424637, 873644121, 542824532, 626698328, 321346698, 733177141, 635775978, 301017766, 124832010, 711560007, 436431924, 232160005, 686904113, 217706081, 371981820, 744651097, 54384517, 70172591, 191430148, 352161670, 831800296, 230028513, 468494914, 498093407, 333609240, 258906459, 804143948, 119354381, 982508603, 600140318, 376784300, 142890651, 202131889, 753862248, 135024420, 651874528, 186366076, 618505846, 585216400, 323874769, 73306054, 200184746, 604115795, 871452782, 434783207, 765445255, 525510404, 66510829, 822246978, 7526362, 970072510, 757193177, 591770293, 26593501, 537875513, 544321577, 460167422, 260092894, 340249925, 233888104, 609662249, 159668964, 695369107, 108626018, 501233684, 129807049, 627448727, 775475428, 595697346, 463291469, 204387534, 623578882, 96933760, 14132999, 431773976, 519348947, 41301867, 627608205, 511667664, 663996895, 439528348, 401718922, 344359959, 223117187, 90666066, 683744762, 513163276, 821067531, 371335945, 639320206, 717640143, 171989490, 58280351, 896014107, 857912548, 550566261, 432001223, 647911847, 336043802, 753846227, 541913562, 325372123, 505378779, 2684055, 301584761, 569452264, 577275248, 585591841, 773123767, 83702566, 378567758, 810806103, 94616060, 42363467, 916420954, 247794204, 223597165, 683582209, 74007833, 913434706, 612271796, 3529544, 346750273, 513541684, 145310012, 226329059, 994278607, 936737719, 171821863, 676470533, 833826882, 718352590, 165162077, 496509583, 911086736, 841774466, 625724182, 942708489, 956887697, 496019292, 930547945, 242150425, 872551706, 272038665, 93465441, 857065526, 935915615, 839092457, 762248989, 254462589, 408032391, 384574978, 342663214, 411968287, 257051790, 338516676, 836274101, 561417455, 111217289, 321015844, 195944067, 798454860, 562695272, 954666728, 459878566, 924395799, 199473842, 349757974, 558564438, 453569905, 318551303, 597530589, 290934394, 261005055, 203578476, 237672105, 143525500, 693841372, 648846888, 139872616, 426223943, 409536848, 635746268, 562544417, 879888883, 656165231, 119498917, 319472714, 408655865, 109761696, 435449497, 846762171, 318784336, 34946318, 83496325, 454783214, 734056540, 426115847, 728967922, 70930353, 16768688, 29478707, 453594706, 55014968, 858400834, 867975609, 752611064, 64595167, 974858963, 160412219, 455087252, 626293858, 776975777, 768394385, 55925173, 399567743, 314367379, 804563593, 823451220, 2307013, 220801876, 676666538, 146643136, 187846211, 236683752, 382195669, 828144532, 241193010, 101280997, 139800231, 754021397, 182160838, 143851370, 928573820, 773044848, 59459860, 751656657, 499641056, 165392734, 438308341, 24987358, 734004517, 617640345, 117089477, 882862475, 995620920, 738924867, 193254834, 753418793, 650629896, 712253893, 293263088, 513150554, 131768625, 707522155, 859395355, 35904827, 711819656, 699472061, 68864432, 553792558, 418252087, 451488095, 780428953, 108203254, 777659480, 976248066, 342486737, 943135338, 660056949, 501278584, 356222008, 303820844, 720529393, 241916347, 845475727, 357652419, 155168566, 916958457, 950633291, 241270304, 268248418, 206788363, 327944176, 363705024, 262781892, 814805433, 814758713, 212806250, 613204648, 76449365, 429700605, 620179826, 211215996, 171604626, 491305000, 629555816, 788617850, 206923633, 897496306, 994810556, 346860176, 994247550, 299236041, 881444506, 699111772, 615111568, 643357209, 283580559, 660390832, 793607713, 461694548, 75737531, 653551593, 279644003, 822171780, 213174010, 540492939, 364063446, 687589658, 696340255, 471438470, 838500325, 207767876, 416916378, 11298981, 278559136, 154132196, 684063865, 709756211, 930291369, 758844663, 94577019, 832742042, 447273826, 385535092, 147684133, 145167038, 685388981, 856408395, 227018343, 968991648, 84365506, 779836909, 443530906, 435829418, 367473752, 958727279, 746066868, 25926192, 966643796, 154740063, 363066528, 939406354, 478798493, 845990147, 136106899, 467513205, 712796799, 512510232, 91633765, 339025354, 825180291, 450110021, 22475262, 471295186, 57616612, 787132622, 982602644, 995887198, 644598494, 49972463, 202282761, 661265871, 739736511, 74280744, 812674000, 979354956, 456357245, 458546271, 530836532, 367885753, 841271317, 493649737, 436205068, 401423581, 213338152, 541381977, 342224694, 26501570, 459791722, 217489454, 91290382, 532510096, 560497981, 848554400, 798332362, 337483554, 660438077, 269616894, 780391567, 362979095, 720195686, 480491535, 388521806, 525666227, 12496289, 373501689, 159266671, 260638167, 248240771, 244263410, 156118776, 620606733, 263894436, 441876387, 949539344, 710729743, 753428977, 402989863, 91219547, 513442781, 895505774, 618726492, 653470496, 695647372, 55254849, 929943087, 113254312, 675370230, 364684747, 471753990, 365764613, 554255748, 923961501, 147413112, 183272999, 655426337, 658695758, 367424696, 626371245, 635661883, 91583942, 631801290, 705579794, 440480509, 687510587, 516255401, 528551535, 587618450, 307885920, 883638391, 747569047, 625287671, 918372972, 601891315, 514450116, 349981845, 646544530, 285282077, 686479628, 768595193, 434905744, 250919468, 457435215, 326291967, 532884728, 330627695, 215380805, 970696677, 90226011, 877177495, 955626986, 722464980, 811393415, 953785524, 882330053, 694151516, 876681689, 885272020, 303771936, 262338972, 917012183, 753291205, 400597149, 603401354, 450927179, 108963777, 678253166, 563305319, 156449044, 386412728, 623613015, 867699549, 40899671, 337493156, 667661035, 768418351, 22852273, 713454437, 379303163, 131482400, 844597714, 634521702, 956324263, 43841541, 627234376, 957791929, 761343152, 304652980, 66650579, 573665531, 6758900, 261346954, 614299150, 200781379, 382882903, 255902961, 477211610, 405594212, 646664365, 339986886, 723701730, 586875947, 139765660, 338526421, 326530260, 297374104, 577579081, 794859298, 194327037, 92398121, 997620710, 555834522, 513567310, 15588709, 822133875, 179232807, 142043579, 76270357, 588833945, 185442440, 111823314, 628414548, 793696929, 334729561, 383396653, 524302962, 547344953, 136718089, 834632693, 439575094, 80304109, 901040118, 375612660, 969124378, 211997029, 388453185, 731543887, 528040286, 834695492, 602094950, 431687056, 182491440, 164120016, 12105220, 195194113, 805408196, 710421819, 901749101, 935072991, 706459715, 164159674, 42667042, 97051273, 944951693, 317030470, 696429833, 781839970, 252627603, 205326962, 784048561, 847081882, 409245980, 334906526, 176889604, 789764596, 202668956, 321077350, 454434120, 361838340, 331783499, 985451653, 624288167, 762229970, 833801075, 94419237, 70561307, 331036567, 549169306, 786785761, 193176841, 568905574, 779634181, 453453636, 441839312, 516420551, 220893761, 723682806, 50761629, 446102374, 201474509, 303495916, 131445433, 537558054, 416277140, 948674560, 474068991, 824133496, 925466762, 839255656, 377190365, 836605786, 465780898, 872832003, 950416131, 295960122, 239197292, 818983832, 78180788, 579506944, 442088179, 914721222, 915375598, 414531242, 349315336, 196966202, 172725109, 308291302, 286744598, 464787386, 832466335, 235350615, 309297150, 541791442, 304158112, 877228149, 465956077, 663730887, 376328682, 102390303, 49707724, 584844567, 194834321, 310656886, 225158004, 799836945, 821199478, 63043059, 411949262, 597280995, 868200381, 906535704, 224650302, 571813872, 756963772, 283905985, 981737541, 820708987, 541974154, 360420921, 614915831, 645611566, 879578336, 44245868, 99976386, 365269611, 877283685, 321089980, 207903315, 201545153, 627218091, 925497718, 957160195, 200277587, 402101936, 73976739, 228299247, 4238592, 857638898, 23413937, 229387318, 836033062, 123921006, 905807278, 964062294, 202280561, 967452882, 79371202, 709049810, 554866152, 208875733, 936039369, 677996034, 124954582, 584672265, 790129244, 904875016, 522636522, 819176564, 202036570, 154467418, 110346094, 259161877, 112339418, 218209033, 741006833, 611976369, 203938656, 86685423, 2829377, 524588907, 173773443, 72147293, 370827600, 149176849, 844051742, 819836595, 728967381, 327299495, 411152789, 4580485, 73566702, 632011767, 395900191, 888290039, 583172447, 605223781, 564546817, 741068072, 225426786, 417621692, 583946575, 477517987, 730179200, 721625169, 291119896, 581110129, 571710731, 336976901, 251582952, 668125961, 435410668, 399288405, 213019661, 153760870, 311151205, 832138031, 196060976, 671621139, 27199692, 591942123, 294270118, 254086069, 146939041, 492756932, 601226590, 377558243, 698477980, 211770594, 398639455, 800799469, 905920193, 875831425, 330418130, 882165181, 804335972, 801950710, 494012365, 833154971, 900254250, 638850711, 135405557, 940138736, 9111740, 865156626, 64679365, 18983036, 946885739, 222976951, 376850196, 520227145, 596695108, 818422287, 594227206, 436538427, 297666886, 332597489, 743243870, 384067239, 953079398, 132490936, 886748625, 861960678, 284099948, 640729023, 80341935, 130735510, 432740713, 123362673, 712669135, 581978098, 484882077, 556158004, 557053310, 520679985, 113038899, 216337756, 925887251, 454288369, 248885032, 885627778, 978012260, 544280508, 557912382, 230390334, 780820520, 788735389, 472815700, 116933179, 212088719, 401168746, 159562236, 381139438, 454224784, 209781690, 675118001, 972620522, 55357115, 221798291, 172065449, 780772483, 955130695, 250649924, 33492544, 851534196, 98187505, 350244090, 389156879, 601325005, 113373433, 894737619, 691011705, 287422304, 563295923, 68749410, 412850866, 367925585, 316914995, 220800708, 922217911, 779772475, 831024578, 663460168, 498974869, 103850713, 344470565, 944194046, 575637912, 179538673, 166217018, 145304329, 286548516, 873963533, 964511267, 611058858, 328023599, 680795549, 120067508, 597989334, 472711914, 927960473, 988416567, 919193710, 974509394, 357552085, 260998610, 368831944, 898538361, 840083646, 705408144, 641751590, 261041462, 309235339, 881187094, 748520624, 226433712, 527934852, 32574127, 68082025, 780897588, 408377686, 5763340, 48456367, 944428905, 965224851, 562133375, 661306181, 626133775, 940540612, 334048570, 194695271, 615729050, 366624880, 866605805, 965240578, 462977847, 777679239, 461155637, 893323426, 768943360, 135739900, 472500397, 562119052, 362849902, 892081958, 357620566, 810636792, 168013307, 328872413, 530767273, 280413140, 570361941, 73790733, 721486032, 320360575, 366651617, 550495476, 449359521, 683063735, 670790498, 886640621, 721954327, 423049354, 176671948, 903143976, 757528967, 720359454, 985259103, 344796751, 677814437, 333327384, 33358556, 524125840, 858109016, 836343663, 609724202, 762081061, 877514221, 881906803, 83985175, 658004455, 771020745, 44959913, 977428391, 301887706, 176777664, 488654075, 2578760, 659427674, 843218989};
const ll N = 1e5 + 9, B = 12;
int main()
{
	int t, n;
	//ofstream fout("a.txt");
	for (scanf("%d", &t); t--;)
	{
		scanf("%d", &n);
		vector<ll> p(n + 1, 1);
		ll pos = n / B, ans = a[pos];
		//ll pos = 0, ans = 0;
		for (ll i = pos * B + 1; i <= n; ++i)
		{
			for (ll j = 1, t = M.pow(2, e.phi[i]); j <= i; ++j)
				p[j] = M.mul(p[j - 1], t);
			for (int j = 1; j <= i; ++j)
			{
				ll tmp = M.mul(p[e.phi[j]], M.mul(e.phi[i], e.phi[j]));
				M.qadd(ans, tmp);
				if (j != i)
					M.qadd(ans, tmp);
			}
			//if (i % B == 0)
			//fout << ',' << ans, clog << i << '\n';
		}
		printf("%lld\n", ans);
	}
}