1000 163995040
552309002 654583773 832530162 964609024 586228955 783677305 924203476 116332663 440201052 9246063 445977180 55298922 824637990 872642916 896010471 146401450 857043274 928659615 690662684 113173779 483083193 72389748 73603917 738658836 793193302 608857298 317791041 241379390 620551946 970176729 435496532 498003417 315547653 766381810 208422182 704932115 898155716 875570421 129550249 951416011 652817296 688979538 433646059 788540147 136141498 114872436 603139698 13437342 382626504 636500954 858850834 13980823 324800907 685589606 895866259 260979542 907167489 514538231 24427180 737705381 257281317 808725883 701401297 915276400 697749510 191177636 49024309 83458780 269925586 840242045 805395084 828334536 840171513 195927269 308817530 108994778 89418270 163284841 394213179 492902661 417405116 334496818 239149208 647367188 824643780 368992944 397469191 381797201 880278938 674683341 175314732 406335182 121893463 793722712 253020002 318578359 916472350 430297449 190254903 905791222 693895051 17597784 349187287 476648075 595821666 989463276 476798479 766803815 920594991 583379207 516366355 664183782 692598655 93750448 110929573 604855705 267782470 133469317 632587955 263151776 64660664 104822736 122383335 594054737 248896432 299201451 312003471 719406858 87693487 835595726 181094716 756241855 455274633 210186445 86837746 665376861 839303681 331236804 773220529 727213786 639844285 408714560 272543210 294794608 225208732 380239186 603562812 36545019 97905177 416450752 713004672 659785810 937342104 148077904 782713391 899713605 690803891 776421828 281625326 340950905 488181805 150197361 424081791 410123976 918523530 494676045 656424164 131940465 131525779 653336730 269185867 498149497 280009174 107428406 838989403 160263086 358465218 535692757 50495073 174151014 952733522 969592322 260211290 759243853 95809311 380494280 125461786 164040280 449377805 260785675 857591125 203330146 830182089 976537091 638913333 200615641 791452600 912332243 991106386 766729413 620492204 219784676 463774329 837180295 622946950 378055818 545177023 313841215 707469103 954353661 779836221 494951788 384692406 8687261 499044649 23439440 639128627 328939534 842016655 67230668 451751612 247364940 574934205 843749194 490650486 285831122 78007686 699277570 470683783 152138827 485751791 575901006 184903593 492547160 565274231 458688121 891617837 121083336 89249300 124608437 561504739 147478601 382046716 799778382 119262902 338010631 866816132 619561700 70122574 95569598 586234110 960461063 935644934 60839468 936475098 107049227 532876083 909800518 422389149 719029504 244836290 842833181 102712483 514002872 653435361 366707699 288329709 641376799 354739836 263119196 305984051 665731993 524946067 463996069 216812861 991470282 276007540 578166133 129586795 65871710 6676550 800135860 102207068 100946491 507299675 21247645 375195279 924331023 325202228 60850361 766278193 176088227 298108875 97024193 220397775 79086185 924081510 733237632 157072094 188978265 929986778 517171432 279404047 33765412 870990213 505061422 296271070 674417980 808072418 933127840 225033269 775937113 615529496 101112522 589528828 733157269 222087216 443350664 669835370 164962387 250548329 136603534 870209144 922657008 412391533 286252327 221876394 244474295 81873777 473115279 464272032 137284203 693781065 704924718 264274655 60973836 431930480 748803368 635677489 283618173 714668432 989648238 952072888 316517765 856176944 917129332 136520153 808012489 463666111 639722882 1622723 434461521 401537662 168479178 787742792 179094023 125126372 894853024 118911503 482597193 66626193 536500032 771976869 617716810 51652353 141315797 947033234 711013632 878413105 442383939 86209141 600328275 44230630 831571165 518042640 708016051 784814909 463831685 445413383 533348612 166796339 785580983 431336565 931012387 827209442 903916754 267154775 673465134 527027701 110235951 208694196 243682848 255903254 118785457 649668935 968297308 8812193 700227204 29548555 437339805 800706963 708407913 237026902 482528188 535759775 346816145 869696381 946880773 666610118 605359998 92336123 294183721 92537983 209959033 162941930 500002013 546377091 926268071 717196402 927727476 605911804 24916304 864727609 73452519 21751248 331992241 677109914 519701868 497092796 966961375 534215841 86638172 592437869 824779518 130319351 99833890 124232033 771819858 778872603 840551586 591893696 767528691 224963283 369036342 936117561 185459042 183726349 281071131 71630692 353181903 915536131 570691230 468336640 928076267 114235338 730965725 358204104 516350754 72717257 224873215 191497282 391859847 898191299 531929516 384168003 100561356 351427388 303047333 340605227 624358180 903366647 556620143 23459213 115160239 826250455 961100461 522012700 143480258 401976102 46129208 70635367 916598145 185570557 58594983 116301816 70883500 656442540 288138859 152533269 796138017 150315158 14933185 940408868 822113712 281724243 246577546 864002947 820932539 555364117 20729546 943227328 50267312 632091972 119195801 753433519 704712745 240020177 579355977 694099824 73809248 805604259 89528049 115598682 663268784 199660232 856874346 113363382 514725613 439269492 821328790 456035226 532656672 57415216 219846689 835428810 932026348 51549130 770616680 659562498 787945335 488524376 501455994 619367614 94822101 257824439 677361637 837044166 369852665 747859810 882426054 966005324 962375287 55780645 834166033 91344300 301310355 687987654 679363342 824168218 76725337 609368575 411491395 424939648 99984035 677020766 159696223 15662907 874634323 781914102 183537258 637888887 983103537 447682978 926154534 201293800 140533833 987227051 976308098 296834011 938536420 820865036 117218678 399758322 925164105 891955587 971017891 185293291 818147926 614707523 227033345 198916368 407026904 370843786 198355454 261605596 809482637 684725402 431275717 109659772 997381789 856810869 292394805 157417976 123027645 236917115 354295838 675510040 789684210 375342354 180870617 592295961 366353600 886801712 230482781 884398876 104166867 436385180 496488980 585544715 519401782 741017975 720520222 252453229 409133317 529633555 645271258 350895523 436352672 332318810 81989368 51381379 274796417 293361375 300466425 860016063 552244979 920151982 407250178 831519289 711697958 718043560 280714038 183577125 24986921 374084801 755834766 87792783 387381286 262405306 336312823 804162319 321301412 378853405 207470221 204077244 15473676 337024978 917449368 546948242 813661653 694762082 974552546 981137273 251019979 38876797 674389206 541565345 908617830 425843311 709718149 444478950 309873834 789014409 490281255 821458655 17361301 145341135 298289066 335976236 229644521 31624176 815820686 582780942 134536224 957004645 721593381 314110428 445632420 181582976 134711693 343127664 597044589 923735294 568128948 730331334 439700309 341428944 478649442 523453463 514219486 487445621 817614495 521721586 46672473 131299380 256369933 540521671 329128175 666939576 789832185 103013576 710453699 2215065 998346523 951125241 155451382 6742297 994068688 923318829 915750977 140583488 176637472 959661387 816281252 557320476 878892360 33006965 671576893 691025878 252006896 404390599 105707436 600666125 145699333 810075507 863582277 934793261 83377667 891461962 994850826 262291953 76881095 521997094 917529899 143114728 112147428 336432022 27305315 11904826 713583955 877477005 935375043 704113829 291510728 963704481 935934004 916445610 546800607 853683307 989689644 148984643 253679265 869186847 654736956 63704612 826640453 677843885 316832755 585156816 171739290 932883239 824305146 9376769 456338143 49617124 868722835 252452962 857439964 966791661 101808798 941825898 142519763 534711403 637228625 668547983 958664216 565027371 352091207 214609671 808552219 504901375 102428894 814720083 833267052 832307395 244918662 379216475 824040561 670771206 905986448 659418441 688885145 441420478 716336837 861010234 820444964 305230156 15686601 53457261 259376212 378353661 133434482 457232982 389976211 579024554 104555167 775987207 73663699 674642692 10583468 711014038 858135379 231407032 256911 848623901 646330395 802441419 500150726 694957684 140806134 900056880 269944026 78991215 244905880 376200480 29375142 40339503 426453303 138760857 812180949 399589440 796132130 413621343 931223699 143656018 906437497 235610202 984968803 586042772 746278122 109119449 159347978 739024093 483876479 993315219 250148225 385315601 348612771 748064804 79544813 577742039 738521345 920945199 658826346 977606864 299079873 310262633 90294335 16302246 766887870 834479946 389134142 467931382 517710613 337630006 462731916 282684126 759310661 743370298 105486450 221339867 540573214 395065080 432026267 246795067 675146998 970158358 693021314 650015449 551148953 262186180 299540464 62391970 273793199 39049867 785642562 538794397 85505301 805409884 635918013 843650747 965296770 880807287 599107771 864614586 185687449 31838144 962738807 95385335 207531614 119826866 971644756 173210943 574603073 140449090 74077321 683228419 642210352 260880782 797176126 702045597 959250790 319671640 738696210 30375899 738364768 539167353 364048900 184292273 623094316 693584872 654050641 256625476 633300355 257698073 469529827 729714226 968801685 851507495 515179695 555883914 550813103 990530002 252316385 963171424 524877594 249104413 344457957 130384653 88390938 527014584 384941803 587290419 283905907 557947909 468609781 781017192 78265556 672733261 312160143 155724176 741770333 522132243 3675501 393827301 380228204 197679331 186533019 944524410 284180031 222646687 730953404 72049761 25276362 560927628 21807451 606780931 945626731 447281107 850971776 772607477 564589503 446659486 564957401 867796065 367501342 26430064 786082850 104946760 342915884 559029421 602373150 333974756 410810468 531294895 160958756 187490365 399753341 18142835 81838870 407014069 82030379 208550450 874745344 884316311 909406775 757291863 973998830 641398865 351086714