1000
311334337 832166501 446815321 261868331 972924417 830844409 110802091 97975809 325862921 205264420 361931809 75123143 412089121 458104301 762426199 481903523 742078989 420604001 968020993 244907361 658007666 440634221 572616537 50115841 91992001 568477477 766056837 224987265 102709640 39024929 922643011 19219053 260015701 595086601 324060971 918486537 358583759 697388581 97034001 979278629 745275861 327588545 190520373 882423201 723886339 245577341 756132821 438678401 377881991 538605183 826977217 637822401 684220601 618126861 609191333 242442401 978250218 617092216 100867499 645038081 978255801 416069281 746653273 731848769 549208869 42860385 806329841 604455147 393748401 625856001 97668871 495746137 177043041 649176601 615693633 188028901 495400421 271473281 784185025 561648638 287610605 356053473 438488037 724382216 897587073 683785793 689162501 7453041 244742378 790865457 560989472 128203365 969367861 661773711 746708817 388315291 539733476 560067433 46915161 587563793 419259660 939950243 334196601 464455060 445044626 358257801 665957521 507636971 497325721 901982955 145706586 2806231 98975801 903907199 425544057 194180665 917369357 335263869 743030213 670280421 77057681 484811081 107271237 317929780 851860001 555064455 971617301 458121697 223349001 519671401 555109626 110526536 802391233 865044085 30943810 484367641 658577601 190764888 980553321 407738375 879768771 149790815 425478233 211276385 725602051 252221436 977928969 816558433 894264621 782704241 257363961 330579775 219279401 55981949 427800321 296697775 543606321 135085913 704499713 757216847 269641151 547628481 435408001 29202831 607753291 410652921 711976617 789837701 699684231 780567156 845260033 956659545 66966635 99015225 571671185 674123669 70101691 3869489 390533361 697443151 647704732 68627437 254349801 760691589 686543143 434921857 520271141 643049551 244175361 349702401 444352501 893489441 221052129 637363947 177403801 230916355 206054381 157346377 704620125 153510815 467260221 988204283 797358705 478358481 132774801 612633711 577285261 270066647 964201586 658829716 756602966 808939801 538406106 150912705 833646736 139886911 610770251 736550801 674759773 610245957 245923381 760356761 83765505 357020081 23763521 198842021 312577417 643316109 356826967 84513051 980392991 459087751 846830153 597238851 411380949 174003329 869517051 88761009 321433877 251454256 76158947 627641101 877822705 542647361 391256401 700356006 928580935 985690151 195900057 306649353 435793171 141838351 886894461 378290137 72397281 957088951 933446276 79512491 653146085 773207105 551511905 815711881 200718874 468923075 259871641 133933077 268137619 924839339 132258302 34618947 589079765 524788593 196521001 867211853 590521001 295371977 954171481 12031661 266209331 735939681 713223702 843990273 100733006 506441181 779755061 812725229 442329017 314476461 148470911 693748143 940477408 476182137 546260483 935414073 624994773 596099361 595336293 404759001 705806397 657513057 987833172 254317345 904311269 128643425 558553985 586737665 693253551 988668771 511049161 657002337 69106677 614429441 818645261 167498097 5109571 189650279 565505785 161169076 275942860 375932161 619964605 661208701 500119813 205078873 500990451 526555729 832172568 809771849 476541937 727803121 150614977 700909569 35315495 732699845 297344385 743876909 382556961 300866156 947698677 45735101 918395395 789967093 642308161 168076801 856576853 353038401 979206340 782092995 539190701 659917041 184931203 806105946 680508057 507956761 732542891 258689017 581572321 722796001 659125977 841985951 135110097 417970607 494823439 625403616 906769481 584518359 557160769 246671297 569962919 164253842 767601729 599343905 498238281 872245505 795541651 118001201 613180823 796854995 545303321 306220061 306835483 599793129 804526093 926411617 712487586 892908161 212312321 565708469 223870873 355916801 672678051 67968126 672716237 874761519 103687681 117270361 372441586 278927161 136467137 17252377 75986778 877743021 95130553 721544137 910718393 395499793 736305857 153021681 785308715 945589601 976911137 727288913 47538584 599157601 612780401 221250161 48419957 540873976 793811817 921355693 510178201 600327501 691007801 35855602 326370900 34233745 200036973 757851581 109309401 496238881 475426753 892220393 857301567 536497601 331443513 160552869 307325538 228741701 546343281 460801001 713871926 954552231 490354521 695499533 812524331 326368791 560720861 882586065 17674246 839046697 826796101 939858161 841445735 405735001 446341601 268084381 866222961 301268489 887875673 443236529 644088483 55610343 279990401 628575021 756824351 804601305 986328445 226000801 968520071 33526261 551973169 592059001 419926881 599753623 949993017 29248841 390232001 527097025 270668201 229468818 497262145 916017181 140803941 634200162 788085249 547433009 353139409 725373629 798050001 32250413 50727126 958881745 985807249 250175585 902381664 172169391 208378241 545045501 811283136 74646017 942939556 893152813 431024582 232880791 947864341 913097661 342003654 666722589 236001896 746110525 460062081 855605173 154850561 90412881 704262993 602209621 790084321 471541393 394877601 186781101 386007961 806237106 876488121 91209289 537847033 263342373 679661911 847879393 781590801 859040867 468162719 649993773 422359557 964355851 153634121 429624069 119412531 755742881 781453009 478577446 612236215 519514901 550048441 576906111 41574716 434741371 839906081 62398154 754025393 604176641 863302801 430547401 849737921 800976429 819792353 492363571 590178328 206192641 27646721 760330705 972646401 262709895 776182383 674332169 600845001 677360529 7769601 195016929 588075997 174028951 958063151 772334013 869998837 977524279 478989031 652872111 800628123 185054651 625781951 311144121 928286121 419478081 342730001 731178126 484004921 412889521 383555655 294963361 674685404 26179745 343300051 984968896 355361969 62934265 892916353 832597045 457040744 486746911 524621602 358031249 76740333 77539969 429990457 740835681 717386001 30504401 542590593 332496183 503981081 428610333 404060365 36355965 225666660 992386746 618813583 395612801 212881601 274767086 655717601 944548561 437828661 837082689 145696301 38073729 81210505 315325851 526608221 845074177 349614081 656690695 360549775 787587111 485614141 487316195 620295179 735114501 506536495 178979169 535542457 907368961 737807585 807519376 919108131 703842465 852095269 891237929 356964111 978647201 122051589 209789701 388341557 531646721 924384001 192131086 74748046 552781701 504067201 513037517 856305761 433054836 593395865 605418126 998340236 404093009 531260761 418864301 878023526 601466721 183669796 700856217 615838126 152049051 82473874 187250946 186165245 156593201 227636065 986822943 492249857 361305793 732730861 269088001 57775425 594142990 669101575 464152321 478129601 316612559 405220251 712954626 865059311 803198093 186869761 346600609 444262772 656704001 194577881 383267723 7053097 717549711 967242599 479796801 226460535 598830501 164816328 174971161 375067081 118759263 481400129 69146257 603903841 257111574 358014769 920930081 6374401 687974293 481169431 84084969 475388017 236566687 866229221 772518833 346832201 372387165 213750601 124364953 82732669 226958881 21511961 945447073 948042690 729856001 728140531 776130819 708994241 929258001 247929925 238904289 448551915 486056241 90483743 181780551 132386289 708792218 884456529 752623409 332732289 146700975 814327017 285693961 367622473 266514785 970301307 548252657 361191323 787169201 262989249 319611801 807527760 139597463 197184001 11875413 672972449 347445615 784479874 683289985 910383191 178356845 94126387 356512881 423050126 80871076 281244201 581677217 65471637 700343909 828253931 55569011 232785017 965982041 181507265 436052161 223547441 908407453 886777566 110759841 884670735 192008879 911568897 255535233 402069393 313621371 728137033 24859137 638223193 584512277 878093876 482592073 430231281 247099617 121319425 692528851 685704769 784216601 868131261 456293253 340230363 672246161 6259299 404193041 427779073 683437891 183087049 81560011 865295645 718099001 296005702 721437401 520464701 299993041 484142801 243403745 980365214 601231057 331283297 28601461 366604161 31381361 820528791 13763409 487825001 941240211 272302395 338260233 543899451 26673185 308989697 298358721 951142323 289622191 109802471 290693823 514331387 343383521 888324975 362611441 163615631 830273521 786570601 762577687 429950081 900810401 459478497 538982425 285977391 490683341 693165586 877451395 420709389 240803671 556393193 591123841 841182601 571089601 368441121 667870424 94634908 220314601 987207841 972376527 698565121 839741765 32940878 955135851 794643116 597277441 63989635 633362335 883427225 675718965 132326213 32041601 867664821 912110401 269449678 377739995 991703951 686571761 323356933 470337201 191526401 284387307 493952001 822871695 419958401 821753153 942723521 847392251 339219713 97869668 95950401 993564145 80830301 773705173 533417783 383667597 450003865 938454569 438636801 4862844 746473837 461226257 76665451 174141593 441199993 522273661 647851165 446290357 144092029 840400369 245661913 728196182 869865433 21100641 270985431 707542737 510933349 739215009 3906121 463279741 586746601 185760832 851224233 438361601 111735606 969521577 170461953 670596301 580351441 557241281 277624986 101342951 988094445 645176957 618120701 519771261 710095695 126175601 320621743 674277155 263026769 887639771 127424001 346672321 896159873 721960123 926130001 328188489 463254058 336797871 599117185 464087553 60381201 128287851 528579885 235423401 424624001 874743345 276859421 341062241 178566656 156046801 683186691 943915251 539849025 841818241 186467409 817310733 619399465 651191 302462205 911621921 534057316 823814441 389781181 505501405 785589596 156012721 492830765 285094045 461579489 435083001 25439059 340026192 199818801 300425025 379023761 811260801 450499169 485409109