1133
424466629 746613070 168655216 626669543 993891318 238748425 184809223 142125785 904096008 542026824 189770649 374439848 122041493 578718376 396578184 596964913 275200954 140551183 293813966 781089499 560101442 7246310 892928348 243375610 652532508 129332528 334278213 216875197 529958014 848258060 902409405 268247160 19358745 112228102 531698162 900945281 134911836 423233884 743124365 789686180 407904759 941617897 334023385 630177826 483592401 543998477 87633424 612182994 46653295 55211636 262164678 418435989 488328459 470796968 932294103 143653576 551062315 780303933 705615690 62199408 222632226 626309568 418761124 135827338 441487942 430547122 647944626 833643137 436640471 358006199 747934532 696821931 791420003 887253194 990072855 134310928 823647629 387788101 645194812 699792682 648786130 304119345 44155422 815912758 366047035 519110061 589285304 232477089 906443012 717360352 790504157 447628484 518223729 724112864 926264743 970434490 635432510 748023321 668667178 731187550 646598824 995014565 107101533 446238009 90883935 60871492 149963288 215079177 469575630 894367771 297513835 330154555 132960058 899204371 478731395 380364441 965385362 620084442 803711017 598859203 201507102 492899962 252242241 177508647 209898295 96828497 341624775 150665400 578527944 298777565 870979000 511758712 954569581 686238589 872666012 134003662 55567603 443974729 692526674 97322638 801497772 233750084 844641976 209846141 408821806 829440547 709625238 237315347 145987477 75270570 508933033 944927584 869394660 31635834 806182154 48003908 367766868 609216289 475884394 62575480 184309073 836036996 452088630 943657738 48865519 531112894 256284572 116293943 825292740 719761322 449464200 686104372 945252673 274609860 162478573 714945477 394775867 597844590 412148061 589031231 643713075 856295363 129956493 783327853 63594741 802056369 579404666 632470935 708003509 914438499 16987254 878314276 352507345 260803395 822033163 750970090 930381464 862769972 877965856 550013964 548759755 986013528 922772134 682227996 642075974 660755443 729943592 763827410 68191435 723689380 773936334 54637298 919966623 53572151 615529605 980205093 294950164 312923438 785200856 246700294 519647275 949459962 361441142 13133686 85693201 416947879 452545020 325106581 428449463 192964726 912729243 941677305 674142573 784205529 434328771 602589921 823792489 484212991 649993965 427492777 59385542 167267139 103999922 189316561 733775557 15277704 825473753 32087080 561298602 272598313 637300509 604114779 841117208 935642718 530753905 936627590 205749522 589713346 868149059 956596905 249406629 199679628 25554754 730919462 725824010 712522607 672977654 928528668 517303432 97410020 736705592 698399358 603735330 197977934 520217039 454516314 387598741 672526858 885854667 885617421 960848135 84656694 26770316 999389173 277433566 385534380 67425497 810964219 414527433 250386662 191968974 873033495 712064271 220759108 416626809 975390469 703685001 598153316 936929150 179988379 136858049 153363503 24818065 947574205 438524610 567998418 836365387 660525806 209604489 458563112 555188304 730183649 109821449 274710467 390330128 896780061 17088340 438457747 424217175 377504781 850836659 883252664 757884040 669400966 281510524 629456672 780537656 885644100 352256239 619803403 680949438 953017849 918794934 350419020 297116203 400402745 124744411 403331860 69055058 897958155 352029318 711261780 956639473 354409420 533631966 36414334 845063745 849565257 529244545 622900041 592657635 80850806 71182361 787795718 498365224 609846657 895708775 115970501 943565486 786915987 637206029 630995915 787451126 595552959 854590524 190800298 902146752 342119948 839580914 629278648 102863692 596497701 167655131 923460496 622550176 380124603 955718043 591307634 536383357 397712113 186571858 533667989 109593761 261654104 272787006 62668874 896950182 807743496 201033159 961620323 516998435 205741476 948682022 973620093 773386909 82270077 198853294 23711543 299053151 602126849 881183744 633418674 44619161 716264761 522392843 590065730 73848972 806230892 128444547 34047491 18320961 246466712 459361410 134651578 529884735 802828571 576763253 206713128 311483703 422847881 348216244 330880586 474432696 947931382 40129127 686350181 145440491 445122045 293328281 521781460 460274532 147233616 416774281 323229936 914007061 48636125 53678907 27850343 778981333 275838596 62871160 244889843 344410981 432938110 957767355 221740240 599212112 831851911 459069493 540563789 366000580 555437003 225421423 115888999 28310391 567452178 868008144 880999817 359125571 445516195 298164780 755521058 61387972 440936019 439635786 377800419 183657211 984275244 606576497 102666622 134802285 184732108 537534978 419107158 960522733 787965167 423288299 26727333 430911512 703949369 999320606 617468574 275285497 516652825 492744297 398455988 995211003 446444033 777744249 972337169 721690728 356222005 125936535 800279527 340951339 125557930 891166499 302867375 962221836 429781255 823703307 100617566 751725103 747436382 269234888 675697641 947491041 788653716 824880616 661666278 654875217 447791409 327983314 994757979 248511048 19225615 832669075 251119158 737098119 463973688 439366021 814120562 819613140 976892070 360873646 805813372 349926128 48435822 953539885 508181385 162712460 136064672 279386054 506893793 851347322 694032461 610325698 227291195 593318692 885643082 861440756 121367584 316094814 700372143 114134810 238288567 17366562 503922164 256514611 774629288 563033773 986389326 14576394 950298334 31554886 629487666 833747342 137513588 475991331 852360640 231978407 596176833 254934942 66038875 796477093 663334498 698540173 560537352 135062021 294324115 278939135 443060820 220961065 460320288 966720428 142390144 341312131 544661756 462127463 886156147 150033794 968760325 250288945 506693123 784072578 387760933 500896264 334379663 765196910 661746150 501837835 637075976 504593613 406117508 191564422 343735997 112981493 425295242 584270904 50751601 566290769 204708973 523721243 293564682 826752576 22555571 450765170 724919764 129510617 971431543 815662283 284358701 551634106 77219707 301609597 770622141 961553608 447213470 151496340 546654103 928225457 560661928 768213164 16236113 398544530 356989662 328606233 668914311 83168296 493852666 917347846 789745058 452653652 976257791 499786273 689842959 786501695 327583869 365353389 343423989 631896136 447615369 634670406 442691158 476702896 610321268 953236058 485365856 320324560 757740014 664242471 497015674 877757164 193188633 472068275 869693744 895280546 732430823 439027802 512283896 211174681 9682021 409741599 680733339 6539310 781714767 856260784 448658012 379455297 842677355 351458553 656501494 916600591 176652212 800361364 663914743 242692675 706786249 897977942 933272931 796129837 903413666 984181787 715722960 355004070 386398526 843870039 868509464 952555223 83557975 955660456 230976233 803005336 73838170 596434034 882463577 997321885 597507300 434650274 591155337 251410634 599975336 414638826 329508331 13628597 978792916 777162740 624978241 340175232 647962502 728120178 402057435 54538809 390380092 481153437 515243860 999795490 891428045 282455701 823407978 277528337 69647450 185045070 825433197 110445322 608152025 58557219 456704737 502974914 718602894 342555795 800513029 841373678 393450471 473895634 634061166 642282682 259278029 789259065 765939022 635691401 982970766 728549148 248129314 455208293 956308502 892203725 529249089 907391593 438670773 619596117 175699738 461194060 198116495 280243416 419893332 143265022 179918395 298923524 515580673 382762814 718063762 835748356 203706392 18761339 720675200 851701028 544182152 159655644 256502590 50778499 378281982 217549989 409889536 422698170 243427994 807284663 314710949 462486891 427486833 702660904 874970921 743606780 965470040 123637512 456490296 141866209 449240132 642380102 802421144 926278445 263750217 445576335 63391744 520743278 261751070 830717501 959868657 348622280 870919934 237727021 695775124 784655994 489499990 770368770 454597649 491785858 887888698 214249783 567464834 807762749 62398506 358092029 750369057 147708132 189786041 528718361 432697355 676165767 523484451 477393659 564659272 685776913 250357553 834031801 799608311 123382115 834615194 765827693 792557953 370782258 41727883 813754407 33950809 19358079 505667684 981308368 621289457 346672933 670329459 8982100 93063652 339099302 550472173 606800019 781179273 111664015 697709530 888077227 153326770 527598450 549632011 760175852 574298355 6648829 525709897 95100108 790175158 697055366 39729931 652545023 983838790 927875108 464077072 101245513 709149717 79306186 741402183 616085870 753806701 939296460 900786075 657649509 475764070 200591442 755436559 902652169 480217095 300217900 523198081 423426961 862733749 39422104 118249149 609305121 645367136 12560479 909552026 705728894 36289651 146193798 8056842 124111051 741071347 972444776 712062201 504498226 55279395 253056035 131363938 55881123 889147195 427741214 214718654 631921229 967094155 876180221 774733481 800445680 188400962 203194665 368071630 249910225 705506975 598254459 88240507 109558854 24408623 783793757 669058672 694298367 73566937 256715587 541365844 670568525 302516449 980320074 967634010 459612057 200871503 95378856 306689704 897872764 800040921 539702029 609602779 482665578 572924290 334218386 378487947 373318191 413621408 32235782 563975194 364672591 400605691 355387119 168602696 948027772 974587553 468820248 804698340 121193185 804727222 677715991 383381323 966269996 738029097 243370649 949552727 584275210 234207532 622631540 857756717 526118988 423206702 416552831 568042334 354817884 100989544 292323370 177946983 389490444 461677089 182755841 455224432 905464321 499143579 797793303 703742000 261758393 351910471 461764064 586772553 252146714 21203157 851910170 796874027 471684655 281623231 99912086 90448954 898727509 297548894 908105391 193628096 372211762 791250883 954579452 586529187 623402493 732238003 475744227 353560910 959385111 868348252 391553070 815323129 280061683 146073217 761505854 337617550 187259811 219503110 392788261 749958207 497221865 102382993 451823518 46579213 197452193 561139781 753745397 337065642 101628438 138926785 499410506 391703580 241711162 857698457 870153898 604330474 299289 162498861 175289374 569482356 273979140 636698341 578710975 579508198 696722814 950734821 986065507 742192200 599452114 730302081 805787502 970147511 279043872 56074990 103069682 535396912 982227115 167783176 316378497 249928050 721082827 566936285 991064249 936572402 22924612 78887394 861319 200112063 422026308 626490044 823663225 586461692 241585675 30822428 859726666 436601066 499546570 864199782 783738818 389998330 559180012 777834622 833275724 503067034 409461402 74201604 973033870 970387011 699151120 593028586 373540130 339927306 719947448 482926010 46685676 591367191 414087753 684930933 875912976 816539031 651585430 563303360 1979251 549580626 407422052 134725548 267696086 737402235 628532937 638870943 839114053 51769065 158549710 919620267 599987587 425005817 684474312 327245832 145495186 978801483 700602116 181138869 878963801 498036900 545307103 323984234 10251682 855219465 197778494 386346723 149770551 659006873 849301630 127648858 265236412 262892872 963946261