1000 917996225
281788142 51049435 803888966 741533676 469563058 868944569 179147001 970110453 156283100 329830678 253264055 961112934 909208003 242657512 805486529 214426954 248959632 486340542 429284388 225103750 252517841 456223329 603434521 700523716 191677464 203146090 626289115 188214072 638145933 231482736 475491818 530892423 678426305 552974479 800402344 21826598 472869308 930837058 406459121 727136194 567591080 189463434 567796923 364192640 608826022 584518467 660075118 249384956 185916194 883144113 311955605 994089487 603311395 230876316 651588223 539957171 214877046 685690705 239080538 205324170 442734781 989705547 13647146 665409035 754016159 768677673 398165052 519022344 689045944 35402395 11647472 340627043 140565650 711508100 228519494 23423312 186237660 825553845 45954303 517322482 845387045 386174386 659101260 112249155 941951534 270840523 613369981 685006719 456385494 126777406 517465115 141449034 217572934 552972777 990039286 293790029 566393478 246018106 881160978 188018464 992165014 67374719 761180106 777637196 765852540 994030385 398991347 259128293 66843236 743065264 597307718 731611816 384589644 116387008 730424279 337274714 914262116 277499593 226237744 926742390 354365657 5952217 573838788 881978 997649990 825397642 530780692 907672863 906152722 140860702 281484844 168340748 653277289 388439707 783246349 669594681 769276132 202101878 365936533 643984396 591211399 722940515 211082717 81942211 365642900 261923896 690594593 761751189 221812640 195985419 284992219 655409987 775968020 488408484 949734516 290390761 993387808 697683660 68113273 164307494 186644425 246046864 804575367 114647178 339834489 64920135 830336579 811880335 560835966 788387216 804651028 461716582 589655216 30518598 41361791 592922941 473782281 738402879 426602394 383048979 350677268 756957814 338207990 581515555 311114953 300207644 152900962 390976121 909257077 359500048 776607776 327621729 643578917 41684815 984478980 249910927 404830801 352940990 947134059 91695662 386161659 787966718 46506410 37828320 788094372 169457734 16180184 303310047 566953057 727208041 158544550 192271163 890159016 449419776 29086492 513394887 323231573 128342259 749277655 929658588 953589372 399640647 599421356 746351869 862233149 944239150 686024567 931119367 746760675 729758566 580828079 805757322 150028628 92275793 489925575 527358346 321282830 24285720 984651939 372229429 618608379 746783046 523340639 610444506 440950977 20466059 99477743 163104034 658588720 601388965 715090030 951637984 961235377 661088676 92385226 423505260 411379717 558683226 147403628 51908915 414586082 738792705 50091627 232157384 192764859 963982316 896909765 389697726 593338644 737544810 713292425 639137925 35516750 326902815 557093499 588180151 898981075 265837572 43782027 216070275 904939505 590543815 604766908 420639612 765852028 235709705 61309246 298687562 28710022 593922151 798023199 242190339 466040757 674428892 906811407 980193181 855262887 526440586 378087107 910257595 809017762 593892122 625124685 776497137 128220691 993924622 882448699 425072722 51544955 265912223 330817528 728232980 423559899 135051790 921464257 277461614 382636139 692733931 494710695 426993742 127211369 641766184 868650752 216642438 719855171 857940294 203982438 796624519 320531937 2682596 305145149 852127467 494328919 661443869 809486629 69713856 657661693 749845084 10598785 59779411 404828010 978125804 809242783 393698663 134647306 462760610 517132275 43436901 187188260 650422696 976087270 596295288 246402944 564791557 564525300 65875612 675917371 859993622 921381518 542997217 102626400 114432467 81423817 167176083 791665501 720690996 177145267 463718361 246605314 149366422 879602778 944520395 449839832 226523726 827444799 569474057 633825404 368947889 759914013 594781448 2861736 142133892 213392210 463609745 225760208 55378650 607180123 534207759 316224943 12736051 62341907 822140830 655462573 213091047 71733818 455862750 38560860 125158733 567076349 321669290 106602052 745717008 70454317 584248649 129874546 571157610 171855285 884711801 685225548 135253679 665609948 845550299 66608014 504610185 631548695 28334028 126829073 200320579 456038149 310576121 772598427 545273758 964283328 449472341 506704807 208322890 893981260 857072402 486253122 762616231 176464299 135366047 824503173 403736548 246106975 424764019 687629217 388755559 953303243 246962842 208816602 801708359 640997390 125040373 24400046 434791389 476514810 832023353 166292057 936111359 146752217 449924075 570231396 667533240 351167656 882047888 775599806 895088757 269575140 300158295 872284537 805529934 188650640 761817954 649169209 53777504 897337800 827282600 122988092 504468561 509285446 644972993 462205572 417889004 712512201 598750778 929917399 863444035 753148972 3358193 148108398 83213394 634430259 328657891 933408397 252428984 992879041 735242877 919078579 142209046 597267273 390124359 483195198 669407082 846193993 736242104 216258950 163423344 928088846 122375048 652579259 80146281 517544298 272296478 409636954 934643200 112052979 126039711 841107241 174427533 157514496 548869812 20602296 70438643 310365130 184208656 506619764 96722606 767452168 810293176 389242769 58350559 444636924 556634089 891109843 126962942 432501679 39944781 694109695 392352379 66912401 988913205 890893051 781335787 330559667 413520466 785237122 96143989 755575758 92319757 514098873 717186356 583989676 248675058 433502311 150812557 625236013 174901187 521678740 745139272 458658687 234283169 618026701 199397979 395239009 916333503 915595220 34341552 394297077 570330847 461534062 683143112 447289754 985839936 25898434 294412856 72410415 755537668 275844564 795091301 146297827 711594482 263780628 571079139 994619965 771728863 50560587 732745406 746464023 383707864 88128619 633429742 179474348 249032564 10087129 517419609 475318520 846749422 52358014 512993334 146268299 177008603 265205220 461656719 43575357 970178214 202349354 873409585 658961046 445520499 103931669 279593850 812145911 388633377 400709758 470627320 962865 358412723 254656628 377096911 123068398 363420756 507257290 558227234 242570293 471594085 951211866 34557899 302774104 167383204 178953980 231788537 487830535 454855263 869253183 907137793 536022531 844491480 748452408 16748615 268947544 848755942 288112465 401410654 162010271 347917008 91838297 748199804 746330752 338712358 285826768 962715717 748818493 559677728 234038065 903239083 782400261 312514150 912303578 720261299 434992650 715370158 480135224 866429188 64390529 198947392 146571446 805343634 915753714 628933082 348479871 297685211 606601355 128315238 623911879 252137713 917038430 463016149 549948434 864260003 710711151 924076546 209714153 72317021 337127623 287032607 625008523 850830316 701962307 951736829 447538482 336512806 333232168 284825630 360942514 384823286 335145662 723764785 616615280 149604872 398371408 798134462 225641335 496494666 699665935 104124509 41302030 18345044 301359834 630125452 797582071 601709424 856275930 299393065 920361208 320131970 913627630 590688255 461352585 313552302 224043950 318686744 550962166 139743178 111135855 141544140 765894285 792951179 907156618 124619531 877034523 211525942 310441676 602446897 65303458 449352418 989884066 833120229 471425285 534458044 69844675 196872716 852715853 716425059 86788961 193368141 275502138 546046650 737505709 987745586 31817602 317053325 943512816 193858952 801279648 869549365 509837384 227296155 409947008 524628981 68949743 118283269 869706738 933122926 273562501 581224464 56667958 438286970 780898231 341235122 179046661 12678214 196229441 639997377 512230457 469188477 276254147 251170335 587245557 206962713 289591854 484422610 504235457 686087166 478430679 385103850 298217993 324108686 989602026 375293679 88463721 240562028 215161823 929474184 328779637 717357085 735096801 957341519 968767705 426926673 361404088 639416067 510695809 146039007 241139584 17992222 73578692 845797873 896800435 237775194 213055951 567123006 351744533 865685009 484270435 663581104 205447485 248978043 793270016 384309630 832158258 559334943 881375982 681849171 141107562 345696075 644483820 768604438 787735061 318489231 983489067 593691253 867514340 717913031 96077156 10908478 6620265 490390691 521170176 327237993 624337243 716809475 383390225 256048511 911219925 470514541 616382104 337111504 490690341 801720455 124597921 595033487 82549505 996201607 218574224 756324812 672547978 594791051 221456404 265662920 858208510 620181101 62231600 497393213 172674116 939703021 909563938 255486373 10908753 253893991 26039159 928313347 100323875 994550370 259969421 436804914 465023422 310806622 242381261 940418040 680019039 65956982 546102118 591762674 968956682 872094487 981601795 509452906 33801457 867226199 222011918 172749937 881026644 272365996 75022425 268627327 330688307 963109592 47469025 760153666 432192499 987481854 852789055 876756139 745871146 707747923 533276219 373236341 769044674 237237948 923430997 247600883 804285155 507323416 378221519 122851628 195399590 229252712 186577185 160688550 868603621 163094025 487799420 143883787 827220148 217885868 681510457 51549937 168363243 932762529 559852460 842311926 444179089 28925336 743979616 314847803 379242761 970438469 630746925 379222060 765249947 731803804 899170406 422502484 843726195 6905370 333466796 555205281 327062004 748343157 289898482 222972627 288105543 343585369 258810863 669704578 923153660 172639658 796800805 444861537 914161393 656953953 500853496 485272690 956261551 637668464 790556493 397468651 229356161 594225661 271717462 75695047 943473350 316054062 124815993 152482191 644435132 1841465 385509908 467341404 98507434 689873558 423707104 329364535 956490812 47576624 368925352 808975281 871285334 593929155 566701928 492348810 17033801 700842836 101390939 834794019 618674833 360902105 852267333 866337010 366137599 136288675 14291740 880367527 742652103 180656308 781017294 357085259 170537237 544005023