10
718957750 550906139 217860902 970086047 76748716 854495062 818874278 458393404 789480835 504356659 887279288 184285105 500751370 976512588 760063183 536201582 98905565 284456613 520222320 640100261 910414987 236764367 377027608 133845795 849811937 950899274 50714336 444057633 842573794 666219806 580044104 414047903 217125938 797905007 236650309 146391020 504916428 55524580 604784424 146913622 412397605 344580072 331198727 913148975 321092653 91261903 301866916 272514584 228234883 822089236 912614845 138649863 911369970 142158812 125012024 761181900 93058079 28242726 57755893 788148239 694462533 637799997 54712502 911588471 288221363 291362811 57979485 645654158 199403758 515280275 792567780 611801363 859860347 123766501 377466698 33469359 67544770 531849980 305983943 295779653 206455576 218598782 286945883 117825539 360757594 264474273 731523805 306332040 292717000 789279698 946996645 987179533 279596055 1709140 751284363 567817418 145588318 661780214 65987935 197508442 29576849 858555716 809309805 889437196 982322217 39292862 922906556 902383353 571142843 228890492 50679366 777598419 300005640 337625249 747940324 660763235 454615888 479464122 819611641 747332888 121260180 766608279 587028780 400856235 620833786 190829503 968673653 618938470 705126083 34661582 816446912 734702932 745733664 478273076 624140122 580572240 517565939 399563037 482955586 941225148 628453529 533634952 571339926 928459170 723776567 319280243 441738764 178392449 651260731 113866764 778241703 772520911 880475043 217786843 173377139 353825188 408616346 994567159 972763658 113742422 881745107 641726929 700961721 627478764 119999999 177618202 60567363 490082304 577181239 543522949 431307445 58151127 929674268 2647364 986610297 653450828 174443973 280865420 684359643 825704704 394732184 462601340 450741975 127723587 680388183 624119114 334065141 941520895 471202632 159345159 907779683 352947732 801072088 608741397 832942862 921072087 786359599 893510225 263670750 216057197 289549534 694978195 274208325 219223795 550141925 113334981 725190989 577102264 394200402 409550626 255323328 641448952 724668332 706065303 769172539 257572874 182700776 103237674 199093762 653903409 115099199 106873438 6851134 916171287 568131202 692310363 689759734 207007160 585820581 953430484 423064358 875370115 500925039 697272683 947110276 51066957 810607664 672301259 480685588 57324425 934368251 736008916 698773378 659036576 442074212 320462276 916609450 624774988 276216316 968219578 131194756 391315515 927609382 138045891 160003162 348256943 682872620 849762896 555264104 121209560 803193373 830844828 996579676 156634771 380633870 796206311 60218095 43757893 321023929 540903683 101082319 255392173 276912592 652372063 766945115 571503170 972834339 536070924 48794517 101567015 504290495 179989274 345398896 284416237 170551531 505402058 632673180 853424151 355164947 40453643 974633711 10874680 871298471 823729746 167509451 251932334 619936051 227727546 295690228 940959980 768631229 249288913 48868513 898060187 901660976 815813628 469563350 727011674 204400912 518357868 828578689 708691407 698347142 26493945 993107644 868898673 531896003 478297184 574839183 887060951 518750827 549472887 750451997 390049292 225718993 917961448 494497992 845655044 998205361 790188220 639131383 619352949 39477126 540516262 517413130 793654468 208846250 839492846 520666136 413247162 210367073 201761184 121938562 908714215 228255129 967562573 630129247 760151133 298376116 57484789 499728443 817126943 606957677 102696799 59692594 832676670 20658240 554190587 530848073 871379967 196895166 22495815 490732910 88888659 563012078 860662406 882543127 771858328 700155245 255725622 37621849 910522319 457486807 12076777 671752893 538258302 979639350 154398500 150925794 130531825 211883289 650654237 947658769 671357332 753351036 7351356 356550361 626525643 561541943 887398434 350421969 758437110 762410616 841154879 847325769 177939053 554333644 582385255 949797381 107005249 838110878 987419230 17527561 148114044 999496007 541796820 686372346 831651717 548711686 837298141 962183542 760594976 340468737 762358670 284468667 93819767 769710027 641019029 572861776 183768329 380933822 923283745 794721805 143344431 616954984 494563933 321283484 23804987 76949182 123597224 130810236 915060060 963532820 854163 63174097 815545187 542650984 602062809 499713263 91362663 439360943 314413164 704474005 779829681 76771828 988942673 726165814 698998221 482478061 151543949 882766550 863411883 927344060 530004715 6756308 396815403 24568641 180556158 420620391 101517823 156669749 551430627 869094249 120202562 552284791 784784712 935747749 94935768 239363881 287977371 38814797 678724824 602390536 595805169 311070864 679162364 437264201 889753044 230676944 919742262 41296986 113443487 635670504 821157413 495964568 494943178 217972809 520533210 675499337 638593200 474567399 832169086 42540187 196178008 804888014 594824978 833479086 593152123 542277112 72842960 881129494 433608275 604084151 483520023 29413437 915155015 15198746 319194004 657424419 245875690 91452625 551237771 211835544 727123130 372395177 707800112 74582667 442884353 80849681 750082004 81477546 407933447 434767449 124017733 604111455 92171823 571359077 290106900 685323946 113636182 362949861 566453433 547244458 967034012 902489823 429174261 734705386 917688569 600884632 244646164 16080619 692337257 795883936 80432529 271976746 20795472 788232641 346559414 463679825 721598689 949157784 397673738 129532129 236441593 374207837 586159950 328613416 945566915 876266850 13937355 59203090 91733070 432907154 458963914 58767075 335396970 740654542 645988828 105601899 341539167 890634992 121682518 886392790 539035287 54631413 10885896 559830760 842864054 357445310 23510578 416979102 159119453 421184316 546511231 395561046 795392154 132671174 724174462 593475428 861454391 738111817 505194884 953187461 23535331 964158799 864470903 358932301 557329700 362976090 317050566 898868867 106127441 291249450 637778016 645162729 345880863 648663912 204993482 41261277 6109215 81020426 458240379 17745035 502204743 4751604 413306081 150113256 989939151 137480537 743588684 703909901 728108720 101299927 657097356 751644051 65458719 374084618 110576346 475304785 737060708 280143278 226690011 843188149 571392729 864468028 488350871 917273592 513131933 545860719 958534869 371757515 626881146 416775242 389502550 129085882 274043212 802808631 131715504 116498722 792805534 727820554 820408624 520914248 829120481 330022339 125074658 747095567 704106957 88167370 222400345 293684024 368310649 449090357 136872166 939703378 166074744 477739404 856976963 679206677 23600116 668028192 903480558 650481262 84803427 145499467 632083510 211363005 948308099 616315380 180378093 593629992 344135927 786710 114544233 25772768 183325415 92135258 772868335 739948738 180302628 995268680 33632755 548613277 296875396 23021288 488316648 462950140 500760692 197809971 994673184 524360808 865838163 898153735 27358430 803157956 43653196 511958306 867037327 844477661 128273680 47415413 290624012 324925973 900718497 257684612 350698741 84043905 349819870 123567069 676509010 530122498 971352116 710141765 78735769 120743871 733163053 419568783 583694012 86440104 617378754 430883555 610800913 335733276 181553649 490675709 991407598 77723211 2634008 858444918 922200872 130907688 758376698 65341244 308350028 659095188 323025856 659048769 595655459 672845726 782615839 124680828 202968217 606484314 834822594 134220352 727228185 420502006 553789136 163438556 506942111 23684249 594322111 970259390 359417526 775875761 460935092 203341483 853598972 316085466 61786395 628316204 299509521 672679459 693657448 607859549 184291006 16683297 266908311 779946465 689529023 902040516 904627294 745013606 508524823 591966247 879233959 88269368 864984619 433023088 251707924 224443089 456707337 846030036 194702472 668641229 621905790 508153930 871982713 328021121 824239397 786285474 956337325 123748911 458964926 649994766 731608460 643255932 519194429 851033137 275718756 61239811 753073647 32862409 806253418 114114829 477345022 685487370 202384197 342329635 971026824 454092122 566772724 280250520 152638517 613991563 948891750 774544307 122145486 820874456 102565421 946384883 459676289 911419113 922650160 918641215 413930238 506774979 414413506 933124668 357808110 542648628 994364479 963398123 575511038 800617890 77512945 52856053 338621619 132413509 247702054 162164802 439021997 666991145 442415323 591660514 280982701 391307066 218721180 255644553 64697881 173802967 54545796 524374170 85222073 977195956 295531744 499152312 483970929 562461616 284793339 694295405 105110237 279157811 657693521 533137641 932292068 587722832 438510061 123430046 572652707 686212115 285594849 11674697 205719619 728010172 603335211 486702320 119317231 822056391 742346874 36531478 995859359 796892670 413422014 933597798 626604985 708953758 285266469 110575907 123931733 570059808 657387678 229041970 849217620 167597558 762179612 634026047 755320391 53206032 757456093 180489457 739418147 43050935 192164155 945137767 771061107 648015732 284356446 742894704 322588483 879219686 631942548 170964201 528628715 45364555 104561992 155233694 606834679 389828462 118325967 730766412 959888270 775713646 959808383 661622249 943311204 574504354 148164655 551147954 627710386 905620749 731637412 219644892 948671684 776317933 17299018 572249151 424333658 154171831 167660214 746922141 33391510 799602763 917886342 562020226 697483684 874964701 569770286 304318357 117309522 688096253 35084762 77197785 316326258 847409511 591336401 112153822 274430224 739501056 515818142 754656976 497638164 99971913 974301869 298826208 876289846 844117253 871075359 153139864 998289084 891251939 900062005 31680588 543371061 670464707 446217180 240854739 397945767 15987459 397689462 515255289 556600078 285290590 444969440 725442703 132700095 36305834 837596525 259646685 628323257 205931026 14303655 125961414 305902940 841121890 277303988 182192779 537755502 895706 335332643 536044580 892147646 87911008 420241534 435518700 610892081 718975080 528889805 8837841 587478905 926579267 524093130 144078976 211869851 
969062570 722038045 197086312 857884771 412150929 309249363 338724387 618081956 176069384 317202167 923984896 17191267 594506156 106177668 407463136 595401862 294026678 943507716 340065867 234454052 216265609 775584568 845346133 935240689 156990732 854183974 375235953 83569993 230793463 371831295 147956210 52372392 93869334 345042522 762773529 506020263 654291885 101497909 124102212 830361270 271216443 900603474 700068903 718238965 859297509 107532032 166157186 5840546 903556114 506223054 240294598 972338089 134323981 85640724 760095137 291314713 792341064 135331083 374884706 23134520 507162379 522840916 928023285 453548079 720399804 690796808 959568342 227208049 644811083 936186921 57569312 768543892 689306754 610154581 486782850 548604256 570202980 652940037 554444802 326275453 11679450 794739400 151129902 146003431 732896490 911225039 437318144 525237547 46556116 812202851 400888433 406234861 187560126 181428078 859782940 907959931 872224886 671867641 135167973 369552328 460570921 45253651 138096214 2394035 507924598 477395430 550998291 930643944 982851833 957959460 109435757 994531283 605215219 260565659 140534707 338111703 171790691 577852852 715865616 70863173 242572062 116754043 329614400 282648554 150698487 41913699 43124844 22923366 713781341 30809183 244992060 26868621 76062834 235604640 29262656 436503799 565516437 432777314 219664102 548368263 390736767 329099859 395415906 995951986 589665518 535950613 186580048 761456210 966319831 902445665 684835749 61408252 871716074 14450143 344056807 22414554 56363842 387181651 897854293 622661549 417990835 995362719 649530171 346570035 83483719 531309193 783073834 649000156 964086507 2737930 49884778 207339633 184354155 445300684 55807979 774019674 981251298 242388027 387992243 800087488 997350058 72827985 861495741 721582491 87278128 205552541 596513411 996158344 592734192 346884063 618819886 10725020 342246776 120866416 209811422 425730495 652175610 992885256 74730644 468778476 848139552 124615422 676118110 32493701 422432473 731926089 659029741 256200130 974314116 47021977 56287611 824180534 119849962 917783352 545763018 59644457 975852259 142276423 908319167 421102811 341676852 379655412 284344197 683923628 500521829 494155619 962170489 5213798 339557235 889417499 473992274 40213146 866549288 2626743 72706847 288981754 734552832 584252954 545181884 561383308 631274931 453985861 385563835 603641260 224285573 783843219 515802083 200137825 778636008 276637609 621240636 120312854 656293021 905584834 656752848 9331209 252256812 618923331 14545007 591814047 360857189 341053648 632027194 227406470 343680391 557250407 368904590 78233217 141503355 914086474 639616525 625294652 220588695 877696726 81452271 444874268 661539938 597254354 645012093 292692306 873891963 118769089 413005160 382701344 876870289 69758001 392032553 129127094 541197698 406577561 720941142 902054888 747631209 205484695 981977724 91311593 762735102 350882308 22061176 904238457 117485141 514194067 382049469 338073836 391890786 463501740 782948104 905947091 60756088 280476557 198639390 787164417 251762012 464160916 22382120 128632294 386435283 414414674 110275754 927632982 820992235 831216896 682204229 421139803 36701584 516698312 364967762 651953053 867580620 239545305 408707869 837582128 753739372 790757338 28172323 145630152 254259072 811120428 904093609 167531526 944113351 102732992 807212309 195875356 419410274 829594430 177024016 805845557 244009097 287299770 585994898 917517698 118516660 120715486 191173860 7734610 637413799 556141622 512204029 357510778 795686927 920911899 195092899 401942659 711669230 223265223 400089177 818444668 886902017 304182779 985976194 831015361 259432137 645704863 879407083 678842411 475299286 56431092 337204327 571824749 343730862 923199226 489342440 314763888 43914705 680516300 175014865 681328504 89174281 687218894 38839276 737377575 460647152 86448541 139320227 24832742 162230130 539409404 843277410 49132140 696108549 681769964 732663867 955540686 327474820 612070943 486899456 655290472 521018401 824103783 227115214 864749264 599819368 568974020 32029511 643734074 102006679 59560742 177578937 191180960 746779637 68934579 928558535 59943148 7899487 920395128 84775890 170129617 312320891 928053301 219261758 8429433 609823258 951925625 816486485 789814444 416512928 155902300 445104909 937531329 980006084 524736489 654796952 432341811 93710502 539342830 76075878 195717181 598903572 106171182 239414507 198199568 27622127 20489402 258142717 35521614 940884530 342918607 205651232 253205415 270971901 424912990 114151214 733311525 229354974 930637700 523125962 498384268 86539993 820747237 288431957 919062443 345483719 943228909 351404248 291710587 335088098 279996492 487427768 933991671 238684040 726842276 132191232 266306168 747331678 390333949 301827782 540732567 733252557 507479014 793937982 856740824 932392004 908089197 590052343 14263338 691243256 965694671 512647606 777783249 786441902 801079563 549362052 984441987 596824832 900766300 276152568 931912930 33279151 616096702 718420960 271963192 195455337 850612193 538269360 942787015 93462501 840097142 336035942 679231424 200092516 129973917 535972242 132484513 890579480 978540951 999264224 434339095 944235615 364428190 64638704 583193876 18024112 614000756 420152223 614848944 367283415 696304791 399278234 400562566 164917852 117699187 525042124 360373190 820827746 63311477 155676564 766806614 755924986 491712506 446038031 956017502 474202790 834526639 941018381 217298629 813067583 792798965 651637725 609819558 157227148 716276429 45529793 175251260 330277178 465682016 642616571 697560593 14503166 41894798 950639525 179421019 12110351 475681643 539794209 685454464 391509486 695470773 304777437 999950838 39699639 750815468 808484699 513902429 437858467 602019440 731201058 103442409 394818398 382838776 713261967 404561912 99115198 611308127 579813172 281908742 76990136 74946102 831985701 944009676 116840900 782625220 123430688 981467625 110823222 515741263 519438448 354849074 63728395 824215885 354799906 103428034 427547712 15800964 617330463 865406179 617820404 201047881 968848589 12638795 583886657 534626915 269717073 535518222 145935035 849530246 669943330 75441538 924476348 501929025 871967580 893833615 137070604 847914634 727817599 100410192 216172256 99772406 455259266 279900651 776504657 810059172 235845052 56568728 825860137 853175515 921974908 296196900 54223389 743339856 161352062 490626413 130483130 431069135 878661001 128934532 133115740 548604324 56892436 57592082 903049715 928860016 803942063 40120312 629291009 384276021 140530504 845463265 336564793 448306137 125363909 113069443 110881668 213725327 169638171 936741805 66900836 944129445 85455065 973640598 539985660 246807127 316783370 670468791 677876262 47960730 651919689 810992003 596565055 708812125 721100451 352131129 490188500 377558873 244767808 119479502 761834894 237814678 817459133 98399680 686120815 795339408 63985489 797002484 9064729 86140026 586260648 928481938 30269465 671715713 754638895 570255125 918522840 71422259 93240275 596399096 119382989 745159964 259907458 568464410 306488448 981007909 920595540 649193314 358566775 17879707 621189182 972918035 255694385 438648308 923834081 941815201 86504076 987819570 738817678 95568805 73959589 177594685 24050736 956745427 849310399 631205997 379516912 767833232 555144622 472757187 216748687 527043978 70433511 476656145 95508381 229438325 310180413 868620287 878631640 668747188 886499994 499820815 494181582 142194373 790985490 418015656 936525940 877489566 258351585 527859977 973058371 184827541 705454662 849625473 141572961 554765054 333347829 373606239 175114646 888492452 846363427 244379699 415536423 769313304 721035845 363561170 998751629 31216251 84697817 877383262 552479806 823714177 229720437 46661381 818424916 20705920 317193404 754950849 750711852 428061355 135327185 576286582 612888896 840781848 278428414 606978224 248063261 611776243 980584463 423177907 500268688 679464249 667557607 768321477 301293912 241109811 131882641 300045535 124842428 69096824 29945156 529838600 892811001 112181959 429016348 563752277 132887879 746209752 171219485 736116097 26787466 306546671 312402672 639676363 147328512 590831086 99170946 395391773 55123689 932271775 671086047 555392377 464252384 191160013 176230214 765546296 432269824 160629221 65591824 409628618 229726045 948053354 939467219 975053412 60235306 368483560 538805682 45639552 967209678 710025168 781755649 993997144 16571832 946674688 486189866 16416710 390022133 585360812 264324849 445145822 370148947 935410896 538193 834401331 126570902 29284773 599947620 411357092 189913994 518055811 820985711 419640039 318625524 760452923 247209810 378860830 981452849 786015493 277016748 948662520 348557020 58772391 795176023 217645218 857963445 281365883 86578294 247985571 719243061 350903143 693131394 89392001 286314033 546185953 923793332 265401301 575470726 376257312 676758394 765384720 746829489 497744098 37541118 65455006 110713380 284750928 296832202 92166222 923282787 573848951 893345108 124356166 485137708 541037490 342001384 343101146 822403373 428579678 443603083 394162794 779482822 136734470 483554795 918313221 535436789 259864487 183714515 963423881 488638165 860472909 581324960 235467647 210733366 618866078 153439019 173963112 756133373 450271221 118645700 679416153 24120165 11990801 803772320 509257873 405544658 998290070 704875385 80464390 279386108 148478462 474627184 58868923 137729298 958181980 829698510 525682454 70562826 13413018 489106328 559200991 726402294 70431282 647185004 789652026 541813726 800624023 963615139 150463458 250895237 82260832 829879612 127531769 946768007 486168291 636789642 352312658 336974720 194181387 432777048 616360828 342659849 907404233 527746117 332905513 718102572 357444620 858587967 641181764 223374005 200210655 52899114 802292665 123158303 700084118 591944684 664972029 500708134 408076182 815435488 604119737 490337015 497831459 731651506 289621381 836516116 220957508 641934039 173490829 415138895 927227453 789851658 757798744 687148045 170114134 90704250 257766976 527558755 801808584 
898948740 603449126 2019232 951847854 405741784 125177535 651931965 850202834 642665930 5156458 258279010 310617777 609276196 601132391 808449236 193444061 890753772 497481711 414401569 385204170 670972541 829540464 312431616 313340558 439855567 999579662 483454692 383076184 109862997 863529813 184884761 8811731 466978932 39420359 960659585 725237082 164597894 465107910 575439910 807263824 322780734 686235286 117881595 932056930 287367670 778847197 125500985 30637801 128845268 392418920 415841971 799817809 221959378 728273587 965674733 661814945 580369608 301645784 44891122 690232606 165175591 82292249 551560703 484670889 121712608 364736647 209907965 138826868 829844557 637864241 946090693 5141651 324099520 916488654 937198581 463983556 547852210 915215932 494621357 676697478 160151212 910463328 329031646 382110590 491253274 147222738 896441901 71622876 448868523 793849390 614371848 614044114 876141639 18448910 98714996 850370614 383185557 161139327 989197482 65546474 799003568 787804534 70688125 975619454 556809547 7886699 439603003 104661751 775618998 934224360 633875595 935770210 697204047 815423608 170397159 188457315 962646346 66839053 112596557 411514862 713204809 579484771 878075342 441862808 597933681 829306705 292233415 981119238 990446032 133947256 46665705 641965960 921751791 117353830 470101773 478561331 977756903 909704777 435739448 605892260 696445496 922131410 394178829 246165903 737555011 564575988 434623218 552717716 483931407 399736141 964232579 49652576 979220912 694824280 491515384 577154586 524130978 783748799 410790183 367093370 917696055 457455889 861575696 691964205 427326085 331677462 23041896 405082981 93898598 458781344 10975234 642860461 233429113 257670429 889026364 970984124 822246417 176165941 376218200 158694184 575902082 192967138 208346760 555122987 887791418 699862144 984793939 264438756 336127302 395584115 631532126 106339716 705556370 345624181 798303922 132882449 677301643 821345818 390481796 623716608 132643521 253973397 266577062 366072635 511643826 8119785 189573118 186406603 184285726 565791318 345100787 760187808 758758456 405963913 167827154 499066234 105826050 152621086 763504990 294469718 400721567 247553475 253325800 106277931 593177656 51629715 91676746 122995658 725491899 482158542 746712266 710651787 736131939 13289321 76724415 247775759 21409106 118813899 434182362 58211198 537121584 631799515 818399006 148396399 37763421 986226160 647462633 996105844 138847239 410967616 143091921 392085173 658521091 396417721 498363104 104215106 300563803 590039850 227210765 26055695 72198385 973923031 589223848 660846691 839728719 518464629 908622450 713654191 637278529 195321171 771865390 26916472 827120686 590264389 175312871 717400473 429006909 822775505 713506310 420370514 86259480 856598231 812455687 744780572 105532311 163335150 848995678 406096114 753375000 76206436 284668176 678089752 902645834 873892024 191452802 742374546 392356647 100075245 308545096 882151542 147912782 80410479 909068014 827549834 523191235 84380878 544950300 952198144 907156383 110972969 372568651 993415864 820087566 37540698 590712795 925619877 200875848 292224832 331715985 954250849 220947635 616384161 484856960 123593462 342792544 676309762 718484374 735149191 628901373 27029463 469817092 629330521 959956316 378885099 456880348 483147544 315782344 854347014 287862047 75455086 965319983 660430698 68870943 637923908 697971396 512100104 563543778 898847245 656841303 747776129 705614453 877788938 216676649 42987772 853898766 559469194 571813900 424899499 147134744 53231632 304445328 616951837 682562153 116918003 995836936 139442494 600065547 164135639 846305874 887927594 239590726 664142216 400874652 160978035 302066117 951362414 673078140 718126261 702726018 182435802 465902384 260856830 60224733 682579033 303844602 766639865 94564586 875658502 44055723 241699331 928890134 201017417 858651168 463968646 317935421 707004463 455927506 918000968 871140103 302233373 658444922 110730822 966375589 911835940 271708857 120958065 863198347 797303363 839084327 418440725 979739165 157503070 679297555 892480264 692598469 983142158 511636488 787163056 711317019 555692211 28862380 492723513 756709629 887513548 956692159 74645043 447034370 265136025 845162377 318174466 567369398 356123658 281421654 386261347 120475957 553130512 359735778 983674305 202950234 51336464 254631389 182689393 208839534 933928944 75169650 901438004 769587461 439322505 541117419 333420840 995014716 569979799 826144353 604240704 310009706 635352871 531402113 757044076 900488896 229080850 927734909 320374654 437720874 209156556 559152367 558196832 614803434 918888145 394387496 817753669 970224610 649018885 443055 31580503 582947822 928129078 933018507 205051643 219967942 326652285 538472483 67499018 896632084 217133195 671739722 59158149 852486066 55658195 668718592 605491322 137255411 596453494 778382342 574976285 658126416 337534702 133173110 272929844 108939206 527560606 90683506 79163809 29095850 943642934 110744313 612043673 724288371 896279186 817095316 944256314 222931465 208084158 11755325 972079915 425217353 536011413 31238058 130219778 444185974 552473016 735711100 581441385 1442869 366609801 156417664 659569285 704144503 142107140 932499129 813083710 669667747 875699001 744763885 698763597 671858294 855508198 163323629 248663025 604303744 832935311 45435698 827235209 41019462 909707396 651831483 466236815 298235168 535585907 596456594 742421143 88058916 184684053 323862521 89501785 551293855 332796551 749071071 107954717 474903692 534086559 773554793 144571432 262301920 518318672 695851395 786676580 226343229 711691391 35339598 830646973 544626695 933291669 510398541 438162524 842999058 14746384 904399339 141234220 550332291 353372292 736171729 638391208 390572712 60034243 580409359 941866567 245347161 181996789 902337650 720250853 716083349 675892437 717338651 830901635 46727468 265706405 617578208 125587063 977397796 505434173 956234037 374540851 291242201 319148937 812703375 134241253 333895321 569619073 127991839 884227613 922991366 716679934 375135180 166080437 629230543 955544539 107946997 874577704 137541322 862801013 594828550 706141037 391209809 164683560 389559031 437937277 430389966 7137232 563524341 407787755 365087771 372274737 782328606 656329973 543940040 447548340 643087592 877835362 17167407 623595797 614579334 792675139 192792090 842230880 958755576 822022633 650291778 919218939 696600331 640349466 782019945 143945240 199006862 25746114 308628801 588565893 463683391 739018767 448219492 879724098 999322888 813307263 104515194 634167854 322153595 648455235 81716187 817757553 378806956 98883594 293869709 993386290 744075099 486661799 688133529 702830668 308684426 338425300 474565966 857801123 978774767 109102271 1746356 30297988 134848385 162891523 618863882 598531776 754426656 67083367 330772234 753749538 732906996 435287428 240433751 55060585 83742656 322149938 725334504 462549612 273549899 19204207 308452261 17624991 505866006 996585790 572972026 667066798 187527450 47537985 524867914 18818576 9156622 379130637 49116564 144005007 394538526 667980446 742536784 148965176 587580179 73309011 755231080 320487169 361112805 995664831 228064120 444855462 170331128 953398624 759921440 443881027 825119197 68373695 314022385 183501563 917475851 739510777 850568361 957519667 639565128 227952635 976338243 648721751 607083272 877971174 792726758 1621791 398467979 387779901 3103333 986048159 313605278 758334413 159051687 674718084 606515603 387115807 119573539 776846732 193030790 732011345 73244118 18149981 652901406 387266503 54167910 422893617 126777273 904736271 380413277 618858768 132688899 209267880 267580512 592288537 87239047 60307263 446426695 338223392 300603531 449530028 324271544 614208809 60380801 483323231 288926886 666896404 722955404 261016791 296259495 915986195 993028137 369503614 786652542 498445902 756770117 840820452 921339519 736063757 598073082 154269156 207438884 730761982 363537036 475019396 175566878 303292449 387843025 621993573 641515841 688446556 71523595 818303752 155171725 984420769 154143342 444098611 503833532 877098747 557631769 800093028 645601301 403176265 169596635 284770202 901622167 778883118 125590647 822961680 367463234 576180095 977230836 574902118 159458436 193284231 49921507 335025315 349093046 290280899 957018888 990608887 831243821 881058849 661428998 986415546 865479611 815572341 283030517 221829503 692671081 840662286 21922524 190788741 243838544 44035525 475558943 145460704 822918643 453665956 820938750 190381871 29846044 650685945 765283989 189304481 696486542 667721863 524329796 45579581 810519128 333865043 888704835 641762942 214923886 550133826 480694848 932919863 218222526 763725365 154749359 910893607 604387644 29188249 101682341 700742554 73223774 429757650 698719624 896142418 883423606 372174734 86524282 913269651 22860672 704324637 955090498 571863581 224562859 331936653 617443162 35081980 665801696 358664356 529361289 880725582 908798183 10056130 666161805 127020702 626297861 820911164 890430676 83201864 850099414 844629383 783944418 923323188 126903393 482664035 671981965 10326992 854838769 611022613 776113009 730215808 167863610 731203500 154595748 392426469 63140146 772038910 280024816 581458209 130703260 661902471 314700150 892017809 524474967 980861955 871554877 150772821 654289479 614501912 233974685 356905252 311647655 17919096 132744799 438551048 353099497 804726765 301394406 60454626 415749371 77507409 643186800 583612981 661227275 797782548 828555817 576883788 422337817 108580626 158341990 405557443 622999463 473042140 150091611 147474423 306420455 21646482 150763610 960709934 488664760 384738295 317615179 652828781 255173757 450359978 91379822 460789620 107603102 245290595 521244246 523352474 322798004 16947405 959481821 984025279 814729953 788037631 413425426 237067764 749134623 571767416 642625207 224650445 897325923 792716819 372124868 203746371 666879667 522888478 16972664 8060786 760143139 334587843 660889568 15316889 637464187 604785756 328622876 745067290 850076351 849867122 120936123 25390714 866814528 80417937 861932360 534060840 720971935 275357779