#include #include using namespace std; long long a[10005]; int main() { ifstream cin("intpairs.in"); ofstream cout("intpairs.out"); ;a[1] = 0 ;a[2] = 1539 ;a[3] = 289665 ;a[4] = 39235977 ;a[5] = 523696753 ;a[6] = 265004938 ;a[7] = 932157465 ;a[8] = 37486185 ;a[9] = 902095969 ;a[10] = 529184385 ;a[11] = 348731024 ;a[12] = 894425387 ;a[13] = 969730300 ;a[14] = 312595267 ;a[15] = 935662133 ;a[16] = 322621748 ;a[17] = 27508701 ;a[18] = 224267169 ;a[19] = 69294363 ;a[20] = 490164511 ;a[21] = 264490220 ;a[22] = 182602060 ;a[23] = 742957748 ;a[24] = 393433594 ;a[25] = 518062619 ;a[26] = 541227229 ;a[27] = 67470640 ;a[28] = 911058660 ;a[29] = 368264996 ;a[30] = 97198220 ;a[31] = 408186204 ;a[32] = 649472633 ;a[33] = 862336620 ;a[34] = 203595333 ;a[35] = 228233630 ;a[36] = 612447392 ;a[37] = 669613321 ;a[38] = 408258609 ;a[39] = 426977059 ;a[40] = 243144357 ;a[41] = 607498526 ;a[42] = 356974061 ;a[43] = 222263941 ;a[44] = 539021133 ;a[45] = 379275365 ;a[46] = 369640904 ;a[47] = 416792997 ;a[48] = 998160796 ;a[49] = 504492152 ;a[50] = 590827834 ;a[51] = 18478185 ;a[52] = 413134452 ;a[53] = 195752608 ;a[54] = 83250746 ;a[55] = 383297776 ;a[56] = 947158955 ;a[57] = 929143107 ;a[58] = 765947143 ;a[59] = 411262887 ;a[60] = 346181282 ;a[61] = 628490240 ;a[62] = 284003370 ;a[63] = 171195556 ;a[64] = 622602681 ;a[65] = 710796947 ;a[66] = 967308324 ;a[67] = 403998000 ;a[68] = 589676616 ;a[69] = 919424285 ;a[70] = 851262197 ;a[71] = 92870901 ;a[72] = 287706263 ;a[73] = 174349775 ;a[74] = 491068276 ;a[75] = 734631835 ;a[76] = 147268330 ;a[77] = 389843174 ;a[78] = 937754771 ;a[79] = 712831612 ;a[80] = 8904499 ;a[81] = 867684421 ;a[82] = 649152439 ;a[83] = 245696770 ;a[84] = 922152058 ;a[85] = 378860545 ;a[86] = 55206341 ;a[87] = 294342116 ;a[88] = 619728247 ;a[89] = 641421732 ;a[90] = 906715788 ;a[91] = 128648468 ;a[92] = 863480198 ;a[93] = 343750208 ;a[94] = 569177083 ;a[95] = 605083661 ;a[96] = 775537786 ;a[97] = 358381195 ;a[98] = 705889220 ;a[99] = 488727490 ;a[100] = 798564824 ;a[101] = 487454551 ;a[102] = 345008005 ;a[103] = 975913268 ;a[104] = 777395286 ;a[105] = 25945704 ;a[106] = 961270104 ;a[107] = 264617823 ;a[108] = 576155610 ;a[109] = 38077795 ;a[110] = 660278422 ;a[111] = 229568536 ;a[112] = 933702326 ;a[113] = 464677222 ;a[114] = 650804774 ;a[115] = 532314699 ;a[116] = 221661 ;a[117] = 389478289 ;a[118] = 881464875 ;a[119] = 397823414 ;a[120] = 62091462 ;a[121] = 370824883 ;a[122] = 334821450 ;a[123] = 98907197 ;a[124] = 887334548 ;a[125] = 666837272 ;a[126] = 851665494 ;a[127] = 825976268 ;a[128] = 897593106 ;a[129] = 234555689 ;a[130] = 155640253 ;a[131] = 693331784 ;a[132] = 279405083 ;a[133] = 806659449 ;a[134] = 396102673 ;a[135] = 347378587 ;a[136] = 781277928 ;a[137] = 115641560 ;a[138] = 15601977 ;a[139] = 923151838 ;a[140] = 316175079 ;a[141] = 666824868 ;a[142] = 272250462 ;a[143] = 158137873 ;a[144] = 262827811 ;a[145] = 335788989 ;a[146] = 226877988 ;a[147] = 537054524 ;a[148] = 279329909 ;a[149] = 440156619 ;a[150] = 538687232 ;a[151] = 780812049 ;a[152] = 343395821 ;a[153] = 283335222 ;a[154] = 887694305 ;a[155] = 925400473 ;a[156] = 824567439 ;a[157] = 261007857 ;a[158] = 159726707 ;a[159] = 96353571 ;a[160] = 40084389 ;a[161] = 678813557 ;a[162] = 833272115 ;a[163] = 278192188 ;a[164] = 241081129 ;a[165] = 837227264 ;a[166] = 765004335 ;a[167] = 428422173 ;a[168] = 399087460 ;a[169] = 59774288 ;a[170] = 668262954 ;a[171] = 585338413 ;a[172] = 426549426 ;a[173] = 407758349 ;a[174] = 583888103 ;a[175] = 247319029 ;a[176] = 887247132 ;a[177] = 910171513 ;a[178] = 98506641 ;a[179] = 582504250 ;a[180] = 827944938 ;a[181] = 446024004 ;a[182] = 892286523 ;a[183] = 530347892 ;a[184] = 447247092 ;a[185] = 996561797 ;a[186] = 839488641 ;a[187] = 367756776 ;a[188] = 421855768 ;a[189] = 981653812 ;a[190] = 665348824 ;a[191] = 229212785 ;a[192] = 611483354 ;a[193] = 765850358 ;a[194] = 182788549 ;a[195] = 397732870 ;a[196] = 357439836 ;a[197] = 509137223 ;a[198] = 815508340 ;a[199] = 628201801 ;a[200] = 369387403 ;a[201] = 899134361 ;a[202] = 953458817 ;a[203] = 824796454 ;a[204] = 724569723 ;a[205] = 210012820 ;a[206] = 325988243 ;a[207] = 121026869 ;a[208] = 129652049 ;a[209] = 318421749 ;a[210] = 2487791 ;a[211] = 988133980 ;a[212] = 996390243 ;a[213] = 486470155 ;a[214] = 21109357 ;a[215] = 763730681 ;a[216] = 618284353 ;a[217] = 120324753 ;a[218] = 817480267 ;a[219] = 866201734 ;a[220] = 934979488 ;a[221] = 234265193 ;a[222] = 1001047867 ;a[223] = 44836819 ;a[224] = 319380903 ;a[225] = 7845261 ;a[226] = 528859349 ;a[227] = 403922840 ;a[228] = 454168338 ;a[229] = 313423769 ;a[230] = 278063402 ;a[231] = 16170162 ;a[232] = 148835929 ;a[233] = 584800366 ;a[234] = 151774624 ;a[235] = 867077752 ;a[236] = 657645785 ;a[237] = 264537500 ;a[238] = 437892546 ;a[239] = 949905295 ;a[240] = 128067656 ;a[241] = 69431290 ;a[242] = 787254905 ;a[243] = 896244142 ;a[244] = 488560895 ;a[245] = 311453547 ;a[246] = 216794528 ;a[247] = 35541706 ;a[248] = 111054901 ;a[249] = 961482059 ;a[250] = 301163863 ;a[251] = 653430018 ;a[252] = 589113252 ;a[253] = 882493887 ;a[254] = 264574693 ;a[255] = 868777247 ;a[256] = 529453132 ;a[257] = 437183796 ;a[258] = 655511048 ;a[259] = 438431173 ;a[260] = 370607744 ;a[261] = 983409238 ;a[262] = 117736877 ;a[263] = 186596351 ;a[264] = 421365614 ;a[265] = 759999001 ;a[266] = 969564883 ;a[267] = 862381285 ;a[268] = 804435138 ;a[269] = 814738423 ;a[270] = 608736071 ;a[271] = 578914712 ;a[272] = 74911231 ;a[273] = 44307015 ;a[274] = 327336947 ;a[275] = 937704600 ;a[276] = 694247371 ;a[277] = 156386202 ;a[278] = 71287337 ;a[279] = 279430361 ;a[280] = 633927615 ;a[281] = 85743865 ;a[282] = 466019406 ;a[283] = 991075072 ;a[284] = 444449412 ;a[285] = 17671293 ;a[286] = 677706919 ;a[287] = 850597618 ;a[288] = 359211409 ;a[289] = 414058118 ;a[290] = 608584282 ;a[291] = 238469540 ;a[292] = 201283256 ;a[293] = 846740050 ;a[294] = 431584570 ;a[295] = 134665329 ;a[296] = 142785016 ;a[297] = 693958202 ;a[298] = 656469124 ;a[299] = 555848765 ;a[300] = 699167413 ;a[301] = 940873310 ;a[302] = 158964813 ;a[303] = 395297671 ;a[304] = 445772530 ;a[305] = 764380903 ;a[306] = 309490373 ;a[307] = 208522470 ;a[308] = 487351430 ;a[309] = 952045252 ;a[310] = 447006182 ;a[311] = 895782846 ;a[312] = 14519483 ;a[313] = 254429521 ;a[314] = 832153726 ;a[315] = 801140121 ;a[316] = 114146185 ;a[317] = 39177989 ;a[318] = 732531098 ;a[319] = 558942458 ;a[320] = 719301398 ;a[321] = 693688586 ;a[322] = 65258639 ;a[323] = 912971265 ;a[324] = 345183803 ;a[325] = 576008319 ;a[326] = 687807466 ;a[327] = 436867224 ;a[328] = 27528383 ;a[329] = 757152951 ;a[330] = 357394422 ;a[331] = 860182176 ;a[332] = 19713180 ;a[333] = 730349854 ;a[334] = 897140976 ;a[335] = 249329290 ;a[336] = 559317257 ;a[337] = 205394393 ;a[338] = 827671038 ;a[339] = 790644249 ;a[340] = 487830925 ;a[341] = 662519044 ;a[342] = 69464378 ;a[343] = 907758863 ;a[344] = 826383648 ;a[345] = 96942604 ;a[346] = 629781884 ;a[347] = 325977471 ;a[348] = 88254275 ;a[349] = 128259448 ;a[350] = 704433647 ;a[351] = 694727326 ;a[352] = 321927097 ;a[353] = 673311691 ;a[354] = 683009384 ;a[355] = 574952549 ;a[356] = 19037530 ;a[357] = 248248899 ;a[358] = 491207670 ;a[359] = 965783177 ;a[360] = 379580331 ;a[361] = 483981825 ;a[362] = 420720417 ;a[363] = 916215203 ;a[364] = 350875033 ;a[365] = 803499959 ;a[366] = 493965360 ;a[367] = 422458135 ;a[368] = 686735141 ;a[369] = 271226785 ;a[370] = 210877542 ;a[371] = 206813889 ;a[372] = 380772909 ;a[373] = 895618363 ;a[374] = 934476681 ;a[375] = 571067091 ;a[376] = 579393294 ;a[377] = 213568244 ;a[378] = 983746195 ;a[379] = 745850117 ;a[380] = 258305250 ;a[381] = 38835247 ;a[382] = 418762652 ;a[383] = 780980485 ;a[384] = 457457628 ;a[385] = 411205949 ;a[386] = 489792130 ;a[387] = 198976489 ;a[388] = 735740584 ;a[389] = 809396020 ;a[390] = 274979981 ;a[391] = 779340848 ;a[392] = 671353544 ;a[393] = 559009783 ;a[394] = 276785881 ;a[395] = 387265430 ;a[396] = 259775451 ;a[397] = 810078422 ;a[398] = 97295169 ;a[399] = 41493843 ;a[400] = 419300690 ;a[401] = 664926941 ;a[402] = 843113215 ;a[403] = 10843579 ;a[404] = 862112842 ;a[405] = 418701973 ;a[406] = 233378231 ;a[407] = 775371029 ;a[408] = 332057909 ;a[409] = 214728253 ;a[410] = 279428717 ;a[411] = 287474765 ;a[412] = 318222627 ;a[413] = 408369176 ;a[414] = 728604497 ;a[415] = 152299223 ;a[416] = 696722653 ;a[417] = 518967389 ;a[418] = 37042065 ;a[419] = 688896756 ;a[420] = 361032011 ;a[421] = 18984594 ;a[422] = 487369553 ;a[423] = 253221605 ;a[424] = 315101174 ;a[425] = 748402301 ;a[426] = 740454670 ;a[427] = 255736711 ;a[428] = 14986282 ;a[429] = 172722454 ;a[430] = 638505034 ;a[431] = 994448730 ;a[432] = 846395001 ;a[433] = 151824471 ;a[434] = 568295376 ;a[435] = 77627616 ;a[436] = 456329162 ;a[437] = 894760500 ;a[438] = 626043462 ;a[439] = 741544204 ;a[440] = 403787161 ;a[441] = 533813083 ;a[442] = 787640286 ;a[443] = 305950383 ;a[444] = 924763139 ;a[445] = 697452629 ;a[446] = 203719313 ;a[447] = 39337442 ;a[448] = 134487591 ;a[449] = 298337739 ;a[450] = 222111771 ;a[451] = 144201291 ;a[452] = 949378964 ;a[453] = 984829280 ;a[454] = 903007046 ;a[455] = 246275393 ;a[456] = 888073157 ;a[457] = 924790874 ;a[458] = 845934463 ;a[459] = 335704415 ;a[460] = 315872583 ;a[461] = 74530242 ;a[462] = 552219604 ;a[463] = 527169830 ;a[464] = 172392734 ;a[465] = 887222368 ;a[466] = 558183263 ;a[467] = 599324089 ;a[468] = 905077241 ;a[469] = 904298891 ;a[470] = 219435691 ;a[471] = 569162450 ;a[472] = 86069041 ;a[473] = 458437190 ;a[474] = 841906143 ;a[475] = 424037740 ;a[476] = 747486012 ;a[477] = 475693869 ;a[478] = 696338887 ;a[479] = 199675992 ;a[480] = 492515162 ;a[481] = 669671278 ;a[482] = 44986924 ;a[483] = 157925057 ;a[484] = 385187526 ;a[485] = 196209418 ;a[486] = 360575455 ;a[487] = 17212010 ;a[488] = 938533379 ;a[489] = 178110490 ;a[490] = 948542668 ;a[491] = 202185882 ;a[492] = 186972025 ;a[493] = 808930507 ;a[494] = 220959534 ;a[495] = 976479931 ;a[496] = 493257124 ;a[497] = 405375403 ;a[498] = 889478054 ;a[499] = 594105138 ;a[500] = 554660608 ;a[501] = 974772746 ;a[502] = 348356192 ;a[503] = 421361677 ;a[504] = 198940216 ;a[505] = 322907189 ;a[506] = 665769743 ;a[507] = 656050003 ;a[508] = 830646693 ;a[509] = 300793536 ;a[510] = 962533082 ;a[511] = 479457223 ;a[512] = 873671846 ;a[513] = 799289825 ;a[514] = 482375171 ;a[515] = 233855326 ;a[516] = 341741211 ;a[517] = 638141782 ;a[518] = 652574806 ;a[519] = 483890322 ;a[520] = 168277700 ;a[521] = 455039462 ;a[522] = 50587246 ;a[523] = 925633168 ;a[524] = 398297228 ;a[525] = 759968172 ;a[526] = 176064873 ;a[527] = 721383949 ;a[528] = 852533287 ;a[529] = 477617089 ;a[530] = 260167752 ;a[531] = 934998113 ;a[532] = 918098473 ;a[533] = 74869245 ;a[534] = 994798378 ;a[535] = 551099267 ;a[536] = 195157817 ;a[537] = 803536409 ;a[538] = 196458943 ;a[539] = 228551568 ;a[540] = 261661705 ;a[541] = 819354331 ;a[542] = 415404897 ;a[543] = 559025868 ;a[544] = 276918593 ;a[545] = 64132772 ;a[546] = 907254921 ;a[547] = 312599385 ;a[548] = 615075107 ;a[549] = 522251056 ;a[550] = 182992348 ;a[551] = 658056095 ;a[552] = 947169530 ;a[553] = 820882838 ;a[554] = 695244074 ;a[555] = 698157677 ;a[556] = 655197256 ;a[557] = 437939445 ;a[558] = 815089835 ;a[559] = 993997905 ;a[560] = 476641459 ;a[561] = 167016362 ;a[562] = 978669556 ;a[563] = 82401006 ;a[564] = 960065914 ;a[565] = 168828704 ;a[566] = 319959680 ;a[567] = 948002806 ;a[568] = 338278403 ;a[569] = 999634522 ;a[570] = 226237357 ;a[571] = 950401850 ;a[572] = 174569768 ;a[573] = 999767260 ;a[574] = 857289504 ;a[575] = 132162712 ;a[576] = 815076025 ;a[577] = 674636849 ;a[578] = 291702746 ;a[579] = 640224380 ;a[580] = 241671374 ;a[581] = 190336860 ;a[582] = 47059983 ;a[583] = 233623054 ;a[584] = 848406526 ;a[585] = 792176632 ;a[586] = 778822533 ;a[587] = 210534468 ;a[588] = 443579342 ;a[589] = 806538320 ;a[590] = 24245699 ;a[591] = 699223653 ;a[592] = 521018736 ;a[593] = 687713460 ;a[594] = 480104454 ;a[595] = 250142200 ;a[596] = 668695095 ;a[597] = 276719511 ;a[598] = 286857808 ;a[599] = 207197598 ;a[600] = 985459598 ;a[601] = 127854873 ;a[602] = 671924325 ;a[603] = 358618953 ;a[604] = 835245408 ;a[605] = 257153698 ;a[606] = 936706980 ;a[607] = 399112737 ;a[608] = 286163569 ;a[609] = 701866830 ;a[610] = 275437785 ;a[611] = 762680507 ;a[612] = 754591440 ;a[613] = 656769916 ;a[614] = 162652224 ;a[615] = 304829995 ;a[616] = 813982811 ;a[617] = 897973016 ;a[618] = 576336264 ;a[619] = 529195233 ;a[620] = 674697971 ;a[621] = 376265903 ;a[622] = 764365464 ;a[623] = 115726706 ;a[624] = 728195766 ;a[625] = 537376716 ;a[626] = 57372086 ;a[627] = 369378468 ;a[628] = 811826852 ;a[629] = 83279386 ;a[630] = 702762946 ;a[631] = 736991397 ;a[632] = 615207182 ;a[633] = 840002846 ;a[634] = 271619350 ;a[635] = 1000543431 ;a[636] = 716302443 ;a[637] = 867305073 ;a[638] = 552950311 ;a[639] = 738126647 ;a[640] = 27282990 ;a[641] = 527492469 ;a[642] = 818173387 ;a[643] = 448937035 ;a[644] = 945253880 ;a[645] = 70076450 ;a[646] = 415461326 ;a[647] = 894638223 ;a[648] = 284132874 ;a[649] = 727014025 ;a[650] = 891788316 ;a[651] = 329688672 ;a[652] = 308294022 ;a[653] = 152424181 ;a[654] = 923973106 ;a[655] = 579198050 ;a[656] = 11042864 ;a[657] = 182516169 ;a[658] = 248499893 ;a[659] = 272713462 ;a[660] = 601837279 ;a[661] = 816830137 ;a[662] = 919034297 ;a[663] = 982698843 ;a[664] = 665904347 ;a[665] = 646075504 ;a[666] = 204252270 ;a[667] = 817875923 ;a[668] = 47321929 ;a[669] = 883236919 ;a[670] = 814099489 ;a[671] = 974772814 ;a[672] = 154705125 ;a[673] = 176368412 ;a[674] = 810847334 ;a[675] = 485000541 ;a[676] = 238800158 ;a[677] = 93209433 ;a[678] = 83015730 ;a[679] = 770904262 ;a[680] = 55147306 ;a[681] = 794511366 ;a[682] = 704828047 ;a[683] = 42025246 ;a[684] = 472513029 ;a[685] = 351311226 ;a[686] = 274344607 ;a[687] = 248756594 ;a[688] = 349662162 ;a[689] = 420612495 ;a[690] = 52216792 ;a[691] = 584886285 ;a[692] = 746764238 ;a[693] = 712857121 ;a[694] = 707190076 ;a[695] = 589965969 ;a[696] = 625576407 ;a[697] = 637575340 ;a[698] = 143617004 ;a[699] = 897043130 ;a[700] = 428013267 ;a[701] = 701548781 ;a[702] = 443361201 ;a[703] = 103597254 ;a[704] = 299908088 ;a[705] = 179548207 ;a[706] = 733914374 ;a[707] = 554325483 ;a[708] = 397833794 ;a[709] = 122239717 ;a[710] = 939145297 ;a[711] = 305209420 ;a[712] = 265356042 ;a[713] = 941687470 ;a[714] = 86951881 ;a[715] = 187963617 ;a[716] = 580870462 ;a[717] = 276661132 ;a[718] = 99950497 ;a[719] = 750150095 ;a[720] = 304338093 ;a[721] = 301377050 ;a[722] = 507722022 ;a[723] = 593156416 ;a[724] = 353180362 ;a[725] = 618088093 ;a[726] = 688530949 ;a[727] = 849365557 ;a[728] = 981843321 ;a[729] = 598091266 ;a[730] = 636802299 ;a[731] = 361580540 ;a[732] = 413170468 ;a[733] = 572321998 ;a[734] = 931681092 ;a[735] = 513505774 ;a[736] = 264552607 ;a[737] = 472611000 ;a[738] = 570726594 ;a[739] = 917771931 ;a[740] = 736432158 ;a[741] = 833364793 ;a[742] = 223670136 ;a[743] = 353395594 ;a[744] = 403703365 ;a[745] = 745245023 ;a[746] = 525684009 ;a[747] = 128180569 ;a[748] = 280105165 ;a[749] = 660823257 ;a[750] = 665862205 ;a[751] = 17499096 ;a[752] = 584371381 ;a[753] = 986818297 ;a[754] = 810369169 ;a[755] = 459780848 ;a[756] = 950951691 ;a[757] = 138759754 ;a[758] = 486873640 ;a[759] = 618655078 ;a[760] = 20826187 ;a[761] = 23343289 ;a[762] = 376174513 ;a[763] = 996782559 ;a[764] = 882892678 ;a[765] = 365523026 ;a[766] = 566824313 ;a[767] = 907926411 ;a[768] = 439380520 ;a[769] = 704003642 ;a[770] = 262149188 ;a[771] = 872879910 ;a[772] = 198703949 ;a[773] = 324162142 ;a[774] = 710651743 ;a[775] = 284742214 ;a[776] = 999584983 ;a[777] = 461963738 ;a[778] = 34407100 ;a[779] = 61082507 ;a[780] = 614111267 ;a[781] = 547763280 ;a[782] = 281126893 ;a[783] = 371237569 ;a[784] = 864240824 ;a[785] = 61115706 ;a[786] = 536516635 ;a[787] = 603652705 ;a[788] = 174291755 ;a[789] = 867246209 ;a[790] = 303570671 ;a[791] = 580255077 ;a[792] = 517164518 ;a[793] = 807670938 ;a[794] = 725177370 ;a[795] = 486090586 ;a[796] = 919942415 ;a[797] = 43484965 ;a[798] = 358664508 ;a[799] = 368827409 ;a[800] = 729042244 ;a[801] = 1312041 ;a[802] = 23290449 ;a[803] = 189021538 ;a[804] = 123895635 ;a[805] = 896964000 ;a[806] = 737414910 ;a[807] = 603509502 ;a[808] = 591507394 ;a[809] = 404947082 ;a[810] = 503011528 ;a[811] = 115799000 ;a[812] = 631879103 ;a[813] = 248271274 ;a[814] = 830338806 ;a[815] = 756207627 ;a[816] = 401418671 ;a[817] = 493772361 ;a[818] = 660320860 ;a[819] = 191817972 ;a[820] = 247467770 ;a[821] = 479956416 ;a[822] = 254025012 ;a[823] = 897072304 ;a[824] = 933261065 ;a[825] = 718490801 ;a[826] = 562469229 ;a[827] = 277297432 ;a[828] = 331659835 ;a[829] = 365633430 ;a[830] = 888419182 ;a[831] = 383102021 ;a[832] = 873072653 ;a[833] = 857464902 ;a[834] = 932248761 ;a[835] = 681887629 ;a[836] = 24621789 ;a[837] = 630564293 ;a[838] = 519203879 ;a[839] = 100001445 ;a[840] = 606318933 ;a[841] = 618692436 ;a[842] = 622047609 ;a[843] = 674484302 ;a[844] = 344839235 ;a[845] = 323064172 ;a[846] = 611516254 ;a[847] = 672493942 ;a[848] = 369395593 ;a[849] = 207252568 ;a[850] = 202853572 ;a[851] = 868396901 ;a[852] = 176012869 ;a[853] = 138032212 ;a[854] = 500169874 ;a[855] = 546221281 ;a[856] = 419162425 ;a[857] = 127302722 ;a[858] = 789466420 ;a[859] = 172169905 ;a[860] = 983708085 ;a[861] = 193027139 ;a[862] = 698932162 ;a[863] = 327474368 ;a[864] = 957829979 ;a[865] = 869426596 ;a[866] = 608183491 ;a[867] = 440910913 ;a[868] = 275196554 ;a[869] = 460038484 ;a[870] = 729233508 ;a[871] = 129572827 ;a[872] = 253870973 ;a[873] = 153361401 ;a[874] = 985922570 ;a[875] = 659022910 ;a[876] = 172757805 ;a[877] = 153618343 ;a[878] = 909048456 ;a[879] = 185001273 ;a[880] = 114970084 ;a[881] = 329704275 ;a[882] = 254152578 ;a[883] = 783990194 ;a[884] = 246550928 ;a[885] = 466200443 ;a[886] = 467494881 ;a[887] = 445477336 ;a[888] = 578193865 ;a[889] = 527004711 ;a[890] = 454732714 ;a[891] = 640889415 ;a[892] = 784235091 ;a[893] = 299665739 ;a[894] = 822767944 ;a[895] = 51524574 ;a[896] = 922870586 ;a[897] = 613237261 ;a[898] = 500354601 ;a[899] = 837477157 ;a[900] = 19726149 ;a[901] = 546720823 ;a[902] = 351226117 ;a[903] = 61659886 ;a[904] = 635217168 ;a[905] = 404609539 ;a[906] = 385357187 ;a[907] = 308833355 ;a[908] = 455858499 ;a[909] = 454199021 ;a[910] = 98893877 ;a[911] = 303325178 ;a[912] = 569826566 ;a[913] = 913968429 ;a[914] = 964518261 ;a[915] = 170321655 ;a[916] = 916183098 ;a[917] = 575770078 ;a[918] = 270621241 ;a[919] = 496293968 ;a[920] = 846866993 ;a[921] = 950172991 ;a[922] = 171535937 ;a[923] = 246286230 ;a[924] = 962650474 ;a[925] = 607732087 ;a[926] = 793530236 ;a[927] = 727698405 ;a[928] = 480921419 ;a[929] = 718237169 ;a[930] = 357471134 ;a[931] = 702087970 ;a[932] = 100503675 ;a[933] = 78549139 ;a[934] = 604979629 ;a[935] = 699336264 ;a[936] = 944640665 ;a[937] = 311397694 ;a[938] = 849733923 ;a[939] = 724508302 ;a[940] = 428514408 ;a[941] = 989496235 ;a[942] = 150124777 ;a[943] = 160783030 ;a[944] = 279570907 ;a[945] = 950616701 ;a[946] = 419778654 ;a[947] = 88384744 ;a[948] = 722761717 ;a[949] = 252448382 ;a[950] = 555578109 ;a[951] = 908779158 ;a[952] = 606019964 ;a[953] = 2321549 ;a[954] = 143019731 ;a[955] = 510844480 ;a[956] = 560498008 ;a[957] = 767375125 ;a[958] = 118175739 ;a[959] = 280406157 ;a[960] = 810221538 ;a[961] = 565488399 ;a[962] = 529636003 ;a[963] = 578499436 ;a[964] = 647743437 ;a[965] = 80620083 ;a[966] = 702626494 ;a[967] = 50331620 ;a[968] = 620386273 ;a[969] = 936672269 ;a[970] = 910759684 ;a[971] = 656623367 ;a[972] = 316047629 ;a[973] = 488905420 ;a[974] = 886103574 ;a[975] = 773442304 ;a[976] = 242243901 ;a[977] = 125004574 ;a[978] = 483430288 ;a[979] = 770977512 ;a[980] = 871261439 ;a[981] = 743175206 ;a[982] = 508832015 ;a[983] = 494694140 ;a[984] = 942430648 ;a[985] = 862350187 ;a[986] = 1000485403 ;a[987] = 329925330 ;a[988] = 409157933 ;a[989] = 315121184 ;a[990] = 595336838 ;a[991] = 362628652 ;a[992] = 998292305 ;a[993] = 937005350 ;a[994] = 115960082 ;a[995] = 171360763 ;a[996] = 990331828 ;a[997] = 312848027 ;a[998] = 492384252 ;a[999] = 101698128 ;a[1000] = 551713588; int n; cin >> n; cout << a[n] << '\n';