1000
409765073 484696827 858877697 801607781 694677629 99733509 549942947 686998469 889014593 565048241 975212997 528093631 958353313 124371361 569943761 38751681 714191870 369374143 739492641 952699729 411541531 549259601 767021081 901269651 641006953 377254209 979398236 980746923 794876431 786341951 777975901 576532201 242642775 385392481 162869918 730420609 817086913 797056633 83444529 775310703 145288239 726118541 375561201 87603231 50470566 844043162 246828725 655041685 937438721 441675801 317918149 421575832 31349665 977257601 675225861 679025981 311950274 120844841 363736409 647396671 976833223 245465393 110649321 567323101 569549449 884416261 555197397 939411233 332714896 849226096 421141701 710503086 583341185 473303601 993307649 835490801 437812158 197142322 996970763 470270057 327921489 275072961 439547473 432360753 209601601 125431861 31293649 559062401 605585307 314052097 183696054 606819675 282168901 729111225 296738627 390801263 141531041 548602221 342639127 398035581 612418173 691785841 324112277 253442925 252082009 581634437 958508485 883705189 327014476 767141251 551447003 275707201 481007281 558600129 612412029 463870777 544028467 850071301 623568501 216533748 521403352 844776977 325136271 529976801 48037361 40292724 290730153 668489701 696251181 878260481 613542353 417216653 404979921 65759851 719699471 144724509 671023329 328040449 955217557 618075527 464291593 553216773 225909189 278350081 149107967 731856281 958361257 932791281 797371427 749980376 332197569 611290355 247160667 110940611 63926177 396561903 453514644 644057601 927030505 529805969 809151545 898011829 327102439 259656977 261970881 174430911 390807633 12051389 26262271 519939201 850397151 733177377 283688775 464351903 371197441 171996271 662856158 174425321 148993601 943464179 800259673 816734163 252204511 820890056 6630177 363725241 434643201 93097969 590354401 755957297 32385481 203875329 692832889 740056501 108353001 627644571 956930979 697872365 786089001 450916487 802603748 933595251 557276717 848547161 34582553 213484713 990111041 1607059 78292801 877511645 449717366 235782529 900318343 549125149 412556465 56172751 424779201 418881120 515432568 714086597 420840752 775163523 679153901 499084747 575987233 432677505 200786841 979699917 480135201 455572581 45956721 390342049 332461857 97193501 805423649 596041021 107275217 873445313 249682389 737491825 292786217 620244705 141659677 426988121 950761411 644415641 147718451 1844737 761920116 420409548 17936997 97404397 685479571 355261181 311524521 716445913 24136641 883957793 720815121 692002961 421212001 911747153 854402897 84243201 393285947 373380321 831054241 714339830 791011545 207618335 234110501 762885841 251007953 36771711 808292031 867400385 809632025 88367656 472175029 439528801 632786126 296153345 489921861 606657987 711989953 971431201 415936481 372838081 436328161 789636501 925934113 932201561 387437421 616055425 621976733 421562441 788659403 20801401 673670981 974123163 784745491 10867265 668972573 621356703 655891072 545140545 342508833 73314405 937411209 544175681 9370686 169877217 793532751 113629991 881507595 751135905 576384001 293420751 695547329 243866781 9408049 62338082 430048891 809150851 123239321 192747681 871779969 929540741 789334141 613717561 627676657 243003301 341355521 677949521 265244113 244189626 755999429 469086301 630351301 381029181 306751251 825199101 875264461 919576167 433328245 624841057 24523181 43298957 857824121 601790090 13620001 744742242 295834961 581632959 315233501 287342033 499430832 679317165 826359025 995137501 834082161 690731001 42131841 694174801 603748871 79285329 32187809 212299441 629294881 135305857 647974433 849182385 792182481 471630337 506625001 958417321 686829305 330084055 138382877 536578801 459129001 168061381 223339481 269601324 743347681 960031841 37277665 827153151 812387101 927933697 446605653 214049537 14468721 128493173 145661599 3345717 632889819 999564041 880682129 405149073 721179041 614204159 863109477 426590441 369961910 638556001 68034689 215150069 160765001 561878609 448638455 809249201 36604016 763421489 707104521 425920801 603279297 393247009 111847685 707374049 572971161 160377531 135315708 191066181 323422661 352314617 949110751 432671251 85726451 982383662 895588321 451202459 399116801 368240105 460186456 423291007 919597741 474432131 104880349 429368001 900781849 275997116 877097314 713594481 957919665 110392574 94245121 718769281 200526001 532658981 783105241 219785697 560550065 131447561 291862349 585280461 350792401 21607109 834761801 306270001 526960833 654924226 659120021 887900443 888521473 347658177 189130163 850529693 980792193 960746801 16728077 187630051 830540177 406545229 671289031 973012931 821568217 995707439 437818641 524507645 258078081 858317386 233302881 824123177 335622981 986606023 758767971 536212861 673863645 640321473 224344731 329762501 451819009 742062989 809771366 806085661 45239801 10643191 574118751 684604939 530668571 76172921 803619585 856755237 336304957 666594865 936955671 93389302 73034799 213576079 419363489 614728961 948656149 452892481 15339413 442826601 810431009 640062689 453397017 572819457 999687651 900379121 415727569 45802393 620678697 757433161 532360623 407346201 729792165 343342765 822238121 507561985 406394185 756986561 93943781 280127651 335539281 30380117 661068624 979242706 65545209 96405001 604850153 89009601 244544951 588099181 522199127 553337469 760600207 765037683 707475937 322515001 949385041 529733641 92032231 202093993 815041431 873451601 893171001 194348609 791069681 227409921 9650744 329806801 303024517 138747991 771759190 635853171 32174176 700516821 203488913 449725737 81643697 258818241 383531481 834879905 863875713 547133363 448034204 316553751 185800623 163209351 838865626 999299809 854695796 541882226 55974945 574031086 341287583 341731666 853431041 466409601 676142621 907818101 986475357 993457519 61492051 5958245 932831831 545158899 721533853 766271041 555358989 873696797 23856521 464329041 142812673 892347781 273657401 576441201 656627357 540533569 261310996 969994801 999027357 137366879 123742205 376986121 375230721 909940172 107654098 398526291 164040595 522473843 131314921 493262495 982768577 313744529 888196321 663897359 322467176 259943091 218355843 346386511 437962113 552775809 763028401 497766133 849743340 378191381 739394741 213896817 154613985 8104761 831745815 498615617 801548001 957915861 873431717 929356097 106321145 27522151 642152601 327084241 21288800 775139456 697710989 99923711 17281781 738734593 143835641 779057182 113573351 140832257 967774901 128692381 238210593 201189601 705751425 664172321 46520961 347370651 980631126 779638973 600269007 22344765 820442440 732994946 378207675 35233293 830695626 370916406 769065853 470972491 530484337 845269669 529306593 160975051 821775041 753900589 529831881 943019221 229664897 483455251 209775463 641173281 673962707 337808081 102113126 790661425 197753623 316367011 550643585 846787153 69715041 661183121 714214141 154321451 423112567 234201446 898718601 254931677 307258966 507698966 604446209 525728001 492273297 111259041 593480161 999565873 505317385 325970601 765027537 712968841 178650151 914904045 344072105 217469652 474943761 396026497 633050881 45084931 767221121 779479553 600945075 689799809 535464801 665217543 142056551 898855247 282220923 150961811 512950925 370661021 112728971 869834667 889446081 741873009 686715731 394702193 76064576 132340461 799345486 55977745 717150581 767969511 777101764 92094411 463370311 891391151 102045857 863055331 581415173 961353653 180211335 204679001 616463233 962157105 336404063 548023495 564424217 68025601 719290961 587617242 972099761 161076161 752079661 988978601 488192966 686743781 22065109 500719971 310669985 397396461 471862721 441570745 301251121 521838337 333450313 405153866 697657601 509751134 960318121 13374185 997613505 61175341 349991341 158085966 266472279 787599937 697212545 86572437 666562369 408402306 816937561 257698713 292894481 399443601 798021931 469029241 897468825 665503845 717095931 960996401 2943493 237145245 648652731 581215681 866176305 898091845 596694161 716908001 616925226 367252279 428376776 345949351 408199041 124345041 897855521 383495641 394831617 138149905 706876936 220942829 892612577 101515713 210148751 72506499 434725141 600031166 673764992 924933761 343969281 513123457 8411137 606512001 514351105 128591921 828400841 782181825 70711893 194648761 735700161 96552455 598580935 439455885 195924795 674860353 173455107 920144655 832173951 997375201 956476969 128433745 510836641 445691604 311804181 523868641 543662009 821458354 859848665 283526017 730346610 640893681 797587561 404712181 545388213 304339201 204448669 628016883 328265745 863006184 293031329 541163221 852015798 754288129 205217905 430970217 178492781 332548037 44167753 540502905 532751593 357621857 405030833 482607319 924674315 576748881 773616684 951063373 838777439 573249593 239753803 473617152 391995351 951675461 112413001 971011375 711970501 198007846 780843591 955066485 104690291 933941901 306356977 130583943 517292161 268661241 243282735 325984241 280128181 226830183 535367751 567757185 70548977 492109893 807118081 465162231 869517733 402939909 22431105 280102187 622228677 918262193 523093501 861035941 823864321 368496701 244187863 873401763 528971537 350357376 668422949 749063431 758346011 612557867 967633281 492380856 205538097 173631921 167501876 193099989 286267713 420518521 976366145 275925396 903873209 432850551 691948981 305616473 883592247 34480289 804524793 991035105 141674156 413565184 480417921 404714849 605469925 227715713 265930470 33790592 288765761 708909866 379390001 212931126 353741297 941867521 703862765 707531001 194250801 585216401 700060731 59085666 754888369 855135821 523808331 219211117 176416961 850352175 694242561 146255961 51876301 347360824 340697043 182944889 184025617 813341985 380684113 365647539