1000 478 940740782 714381689 937823318 988449258 169938905 386860064 348158864 158515947 916342924 899646172 90363606 119213309 110148887 117179379 457891103 52798329 691185021 470038836 566287798 638773193 995822296 105228128 246407075 177144805 120715016 83845466 972593383 49867823 390410800 53527288 98401432 214101573 238707832 601591387 118998411 606877048 457345885 229452782 227483032 772594517 689827212 961413736 720896670 698605178 31170096 760219300 547146727 914122139 447727004 513897990 114261214 861800089 110283908 203731206 879039919 962019686 352457340 787128788 709678602 903343360 791692683 181514262 3546918 51477774 467201479 692857381 815442640 251321824 71344422 904059411 111811100 43724858 304821105 927652645 398006628 429686733 507844736 418681296 759691262 476190176 685855443 212771690 959917123 266666883 323256848 700604154 846157587 832753767 762269229 586290611 119484654 529410597 842171255 843413724 835139157 210965766 767516708 726420464 142468428 668467229 810737428 223953679 381334009 123982052 610663839 417446972 38195603 846950054 663752954 470108427 113542602 281359176 936468418 565930745 486203198 356322250 561579093 37952886 63150782 575549915 976280824 813360317 70327876 643932435 147816779 464992636 201198035 617282020 565873875 791717344 33541807 565008555 929473850 788893557 673178264 648024421 523015521 891639077 264493871 207341324 161277501 605732821 920193445 50959936 854434938 844528583 665519147 380983018 393961004 281039068 991957204 842067559 209088942 525193555 22002887 212892173 618790383 518632286 972872929 676454324 434507576 655882526 28168372 394611515 554299536 974494251 654479930 110742150 839829199 822138848 168810214 645731304 798727016 44900127 216576412 62550615 457019867 547041979 288009638 580287351 837916017 381130036 458145912 271281649 17514797 693528811 518691918 568474820 40623399 465499356 732940841 350169383 322607215 898659014 535435154 330471310 381916784 112276631 628704405 628029089 387773231 898899571 126992179 398337527 521850500 993986566 128839222 217570763 942241910 954883075 708505289 601104806 910043301 213130010 48042241 411016822 336360487 978860239 658625440 55875818 131906803 18146399 944954242 253583006 270063616 38790114 381691557 52219248 743460097 664943286 27532674 318035671 41503617 117001863 142807513 542845759 378415690 514822132 407885842 370960155 592969768 809431605 539146293 890606646 374722517 614373994 750520660 81579594 601688317 920122109 271106945 594295303 296623214 822099346 358462464 952704084 342564629 942909451 842063871 589245885 571731987 797590324 465946220 154461627 382321430 875604272 198192637 883672319 997803345 321280629 278071323 486587300 269128748 833623414 839488490 572620293 818402929 357604614 305153367 801643726 909960951 208720605 593872332 818699331 518636596 561386314 706020534 651222734 24903987 608247820 388801866 733235059 821188507 674971181 431731789 734773972 710662373 752399006 271049963 104244671 157075468 785853743 468817779 962220731 618409939 350959018 530622491 762210295 417431405 240726203 7171530 355582197 952171687 100792326 32361773 920471133 638167510 479026839 791946012 340826235 330883741 206711633 242106383 237876007 297792022 279223032 538686187 548719207 667682723 945331195 229030134 55024304 667708962 822123945 892271493 705406952 576186363 10331025 669381915 872006545 613865144 338853004 725782878 171854304 947776194 920145761 199709305 614676554 582173566 492990342 838893171 55604350 426928902 210494966 391555053 270836168 760847372 922268667 940497319 84808511 125612888 208517736 744262111 58283104 622878946 25103327 834306320 417662999 753976040 900564888 692667872 740264182 840435484 858407416 748068885 563888405 991924805 802631112 498828118 342416335 19562503 759017353 114879403 597040400 793963898 892616889 798431767 271583638 492527898 896011571 242477136 304018770 397350040 136619536 240826117 904894798 211916997 295428155 815494429 49995756 568792492 466284550 882887917 113174075 397601687 938206781 753594533 628941947 983341757 320237862 462771935 395356740 259399370 987893615 990220349 517900669 331569088 206061905 86075592 152689423 898517646 540878081 814384082 223518508 754819625 755613716 747544312 695258705 886514441 719056444 631872600 369062770 62422644 681698850 419225824 451245312 113320465 746335675 282284666 663770463 943965793 990557435 907107520 239602890 117780130 479830457 801031602 431984677 784617165 481247767 383020963 965704247 912223448 531001711 838470090 135234420 608280132 985167983 670297331 413081500 660371194 545030129 943653131 22022894 828681607 957666666 257235187 6282624 288239705 310789195 391230546 778389336 14182657 188897445 404262459 394508282 674474360 153084130 532422458 392226152 821601616 731340696 645619648 130089884 108329057 6591934 319546839 926983210 548107753 380029200 812095167 936446001 273728995 510820385 958813407 596938636 114043954 726110467 727232356 718239019 128533515 981505770 837969679 196571818 381432989 916296962 5809542 661572232 897672767 639136649 367157244 970375410 635277278 742451092 548383615 906183530 482303594 963973511 947617257 740656052 332678111 180962562 440879430 66392562 89551233 382192234 465262455 562897334 737827622 555581472 609432203 550941849 457742575 151559373 661632989 455738763 358184625 710622436 648070803 477623519 166700654 233966044 689922452 794454452 94278242 686330438 101747330 418847389 925003186 509115677 114282247 293713980 843390104 947742792 886880839 409930762 464293865 616853429 863108909 745528804 642896920 224717401 593411220 879098871 135930433 299436214 537753552 498482109 255209618 824622691 993388338 81499330 892589127 97433913 552066066 365647079 472372704 255286051 241060312 706831294 548119943 726778962 533785992 187733520 407898170 98298254 483133390 468628170 709336707 456079808 78360675 667761268 846342861 280713513 459886318 181385444 363542617 227171860 572697369 297622752 128832444 119329576 972696354 968635111 796348456 262871005 798759632 768551439 242279246 546150253 271801721 255274043 877753986 893556779 987471456 769917987 275667204 564132031 186563927 168642754 749643128 878014043 52202850 852204348 690092147 956496812 69973007 493963141 818058425 998467976 68608884 331516122 726238277 270141024 795366681 599505126 606620543 732392235 62168840 4764948 882897390 58001358 30985822 75153150 43841728 978649974 371436034 775418549 309009106 956624962 275040413 602961329 399131750 917826405 900458194 385280653 669889571 747041506 455665213 599848355 965978487 217661050 680042480 923244956 17123651 211432030 1483975 946434875 586937891 881909551 216643000 191117096 944827746 735312843 567593629 897564247 301912451 28294884 806013081 552738981 637300618 944616862 712614610 120053430 577481788 386931709 34489635 816099389 192892264 985591606 774155917 199245333 140069921 656157363 78111119 186607234 51754079 438325808 672095452 385393922 742505886 333784995 138253477 379966048 306501210 606812292 943420820 105525195 67813318 777517750 723475289 576322091 767473648 938100402 719251430 549792492 2195759 862859225 814717911 732598991 781417838 540872932 852665982 921837828 86082879 270578107 851223326 450303960 760842265 936328714 550007138 421034568 537658246 29276250 98627151 722833822 168505312 911148091 894416603 51168180 448782277 725207844 292984258 676474047 400551502 149684850 409193057 552781297 778286191 757822942 424333073 32003212 200102293 511163419 299819306 893718338 430512995 348095392 2599070 530813917 324059345 266526709 688329928 75994959 221952463 796551022 981499235 341070295 308219453 476066499 152513890 588421859 213554155 890750936 209113793 310043946 946731094 137545066 299444174 901534793 347296574 950176974 951016135 713622765 826182311 170250579 7245344 916677105 523135193 538767423 498871884 73482691 377764058 475968856 726232235 440215867 801331417 619935808 123740899 648769155 938147797 620580393 841053302 416219640 74802958 69613714 31104663 352826053 692485244 66714977 362662969 952430072 529346556 751095231 455889673 575631785 642486349 743089106 251208003 970667895 34761138 418783300 342836901 293570096 734704114 686869144 573207294 2744306 72346557 918374626 134776520 772884592 758620570 712309357 82500129 523117763 398273650 460763016 851033908 429205018 663255318 368486884 814738364 168297441 307065725 555556995 647818395 909377605 890735847 920157827 483031665 372602285 686455077 311821057 512906330 464429793 981703663 526938192 779295105 714938325 564156574 915579927 266786034 587654565 445011466 218792783 494474791 324883983 194363939 511350555 354563639 178106331 445979284 954647343 866549483 814056818 725960739 141813086 90634920 436358985 590127495 803172408 980942708 651046743 988052000 514072800 302031461 817642195 774119693 732452053 81805837 215116728 520145852 188548673 518985538 194073274 925583549 61113309 938720217 75904172 624420612 559509099 549635602 884800275 170836118 575715055 825565769 560840009 826097859 118888337 927976494 617767606 669855107 917699515 804344113 655979661 356313835 542029450 910644905 927178808 282299924 535347186 958808613 561270340 567246503 237180238 866726575 999803228 303313295 206743360 690578675 248583677 160677880 753953947 938263691 448750457 251100826 760824122 329984341 492590421 942828204 814353316 99927150 270672614 627632778 556101517 342303312 138100863 882971207 802830370 316948873 390133808 949134376 268079285 98038589 865302994 353847412 751212774 655445054 583855299 888151083 467141831 981121331 278793307 948067154 614145152 713642635 916618916 584554358 79338912 518320092 57591353 220017390 42008291 920127958 604366958 796047761 578260276 145052357 68669241 35561646 747837682 316532164 931162895 845291043 287287019 829609836 622242489 785189685 426797039 825847242 459966283 28335151 744079045 408447497 955442718 101354302 937233717 666404576 597899609