15988
483406534 554587723 442840450 703433131 773390341 591418680 326530473 647228103 79741942 387100294 633145902 348346160 353063887 115050648 589370627 982062126 850267652 691920879 623645467 546542665 667631140 440983536 309120818 528694266 65626025 267788107 328287570 139559707 361793565 447438113 707470263 769127054 834024026 909226599 985686084 939281348 427189898 550439627 501822030 149779525 700531337 507212742 614389147 219375254 72784222 109476342 462255268 699949155 612286419 572813359 359369212 437799193 428387214 512456344 461008967 45934569 397680880 229266403 168748772 78556048 356970589 342312518 240367173 863158960 307602712 318950539 677024219 17336974 940914987 863803237 29176753 87960027 929441955 297913389 207312178 384622902 316772763 639172531 874111080 504931767 196194209 606297871 22350696 207351406 756878788 847625563 498121381 160094643 212813944 343028772 281945004 973702248 994806650 320933968 73149511 319789991 66774967 289085732 848296536 626351733 794137295 153950201 18714320 847179803 951146693 401760746 416906797 209234416 679253832 811424149 135161719 338370220 982924064 276240713 593985924 408576568 311352056 705479042 713912069 952524870 144698929 918223347 312833074 481605406 78826548 956411016 825928177 242978196 970422781 935816827 821409662 504767018 56768294 750094502 703729536 605022408 847970628 833097721 627111514 844442618 491368306 668193147 197317489 113328578 513583583 303493917 160779256 124046816 396399083 302026119 485896092 589765454 501811266 441629172 331075674 59268183 952069585 135717999 758291059 356335564 372617055 906839629 180574256 685533858 994255132 331954417 67676801 944511018 79837924 520950357 37804181 140785951 560266476 686523123 879680605 457534778 537569231 510543023 43911025 551771985 56834399 914780946 445421589 734001490 609786448 982063207 51682021 467093367 126070659 638714988 146149371 575436632 599324495 996593997 94231318 142352099 419941688 384065020 437400237 615295810 150788843 436091566 669542222 367676753 46812558 707840011 503876001 478951081 991043150 875545195 563297214 424874173 577673752 185494040 49312610 797613982 260681884 870444241 627627429 299181751 987461751 35196972 818259 967102369 954721060 725825317 443836574 550316266 189821079 466258237 856648233 428826477 439778918 538898965 533092972 213760910 485680646 508234074 387018895 61402678 681557557 811697148 304625704 782354469 550054126 279617431 892244263 492006687 627074297 790585496 528951148 472824091 896683162 301179851 293950542 758827609 179251745 584018029 26033914 876721350 540932524 419583563 905296668 96920110 737230477 501007931 81053788 682152139 45168061 206348619 43706512 773202849 459461768 248326680 321437952 490353027 195998058 59973879 978311941 773225656 148891985 265876751 782707402 584036126 392695121 129766610 616501008 400102021 451740885 211952718 243417797 211586021 157852884 590212610 653460403 468476515 892211082 764064406 571215757 358253944 395830300 91814820 406840444 577501713 321929653 431672567 863037489 943038432 812719104 555153522 121902761 607469705 32792072 998920312 381881500 769849909 434743737 470052809 620343795 954397968 727699069 640388071 556001623 550937046 833114254 597789408 195086852 26954871 436126600 593159707 683637187 216949189 490803191 365373770 58026525 777725855 649561102 558644632 904122028 326618112 456193143 128528355 319947137 529466620 890149410 77210037 110620720 755368916 76351160 947984576 967097659 828258128 196719633 131075166 858365736 475871490 833769099 554680218 574110895 131743780 626452436 549851909 87150154 788836543 692139084 800954754 885516035 281047193 148284268 623727574 185403204 282961659 454889627 269121171 148135478 901467207 494586652 644549067 128364862 140088993 615257073 631257183 627591812 633465091 91870466 18886632 507096182 604510959 303655012 682411248 913089345 584612126 263808389 426299365 756811972 456672296 473296936 495134945 475827624 686425728 293782779 417134104 485537434 873989215 563524608 783893702 663891203 337424672 373839232 912895483 103557037 546087391 991540263 519598822 531069170 699445348 13345262 991304515 988245269 117796468 666322752 618060009 891572824 686555214 869435127 681467632 125691573 91336950 75296767 501712684 578758306 69038801 978402504 735198677 412902294 840335685 458144869 16876505 386964128 893466061 392070999 59773132 466444041 153187071 761442511 534759121 352549686 908385458 133504961 671945019 894415060 742164129 728582121 312147708 764748419 219868947 557702435 641822122 595702783 458268845 416583915 110985449 240400988 902418876 849366709 728931316 368595889 528021509 972847533 889544528 18331157 657525024 673520950 507579584 791178936 944048340 754094574 80670261 821393953 4041639 179889364 683814334 757671325 40489026 456229377 275365874 99964380 15292149 51912053 376008606 422379979 858988639 204921256 733166496 337581228 999478294 887160209 133058459 909952283 742157768 111141666 765314958 720863283 437471802 991437085 470596264 348243441 299449455 556990998 415544343 398223147 252093079 368564943 144788669 335558525 431123790 639571127 314343531 651866498 3958092 594071978 932360329 934947222 205299604 580694328 813721338 692227654 775738279 305270948 333573692 616638271 595333288 595830714 738314579 21847008 355852306 410720044 690485757 385416589 173952493 923421157 50812447 891962546 16413812 216604937 523947487 209162776 345548822 540540982 783931725 758283159 766341285 310648398 512748950 721167528 918513357 643523696 186514534 656615567 613931736 460355909 550203078 582779562 734119125 350555824 608772594 868109831 818569609 178746835 692989383 2669410 96594637 253740910 980167293 892601019 27556153 562578713 648704465 221039425 717141003 392318492 179464405 999129672 265516469 173146838 42325005 907076725 442123718 942754332 879154364 200232363 367669303 757540585 678414377 246694659 519689006 303148198 176442706 81661792 884081512 635476774 804427593 543576975 669477908 850439477 147928079 992133324 120244625 406988431 744761470 898061582 986911340 64641332 605726593 365848646 294971483 820053453 601070089 470443467 113075875 189043459 119913890 950758901 550376136 209281037 527315776 311733572 701203692 581542776 842744996 59737355 697580853 551606662 897198202 516337011 149057395 920371482 797835997 304461153 253016034 895943950 923182291 769594835 827576232 807584678 374321566 736241999 405699615 817038184 966032316 286555269 121320119 223889537 373751647 995756855 612964870 700373528 269795220 893349499 370438320 477901055 571954664 585520554 519101845 770762861 853156667 13138525 331522739 433271029 19702735 336386319 149262383 69323448 233859231 196208046 324057967 756102927 278354083 901308212 298579080 400612395 725089132 551218757 841953264 367278630 395356639 324377860 211507638 261638509 726543071 311326788 377465521 124467547 456981026 597161068 290994046 152006827 788153930 266787355 539948627 69001934 222641761 19162715 592739545 959574635 212703150 765680151 439403171 922200852 941405797 698531534 649879865 627437065 357858936 766880968 260271199 718995139 500020001 868584758 480254305 864296950 935944296 504314921 289485917 190230306 675901521 505467379 533186619 345320846 331344377 139048978 417400230 564420874 852248348 528231091 507083752 330989304 519938326 306234849 863953120 353701185 267432895 970196625 107541982 629631334 271631806 4859126 119837991 321744271 962454140 161544370 958213263 339022302 456748242 932048280 875937011 307482443 135572784 128827818 62123307 673997260 65955730 945187946 457894359 1267262 711466683 6742675 467552319 731929036 331148577 540700236 264126976 30416344 572606316 617942515 314747023 409448681 909786120 264261320 512991820 195452065 416726716 885816758 221428236 875377719 320069664 27146173 809170854 322054352 286013120 79877915 167029792 832292113 781543590 42993035 237075310 960096191 927064843 896493294 646794900 598492822 247265749 809430931 906050596 224704102 671719481 302924425 223985780 80621275 727602974 803190471 674282058 20896661 365523178 877070546 8075359 604403353 410793734 429565950 144908205 977576473 307372644 567127782 38987686 573981023 836026086 883761356 915671026 729433068 358095027 969926904 354550783 689303178 353382502 636874585 227263622 499676403 996064304 357764602 927699597 183544956 255010454 512080786 239193457 187972527 280458720 465349598 624746882 715944734 774209092 547943244 364007425 308766218 675472391 292828815 214212611 308427317 140476127 679155591 212467694 851576442 925858438 320430071 609717620 953871213 332335210 394377698 399780409 696504080 315445863 334801545 884303286 456893442 99451474 239795418 97247955 760324825 33508726 916358759 209920041 805485923 790038694 430555188 626925531 76847380 450359966 37917444 809746395 489967456 19266175 668871728 639852032 561977069 18162361 514088365 242929881 603441248 836227991 641210611 381288309 715490453 566197434 880774802 223183175 876483128 105982213 554206249 255079220 86043218 370120116 178141213 559192243 162460994 327160272 797293967 631414771 600407470 698793954 104144065 855840183 472131998 254525221 308456690 670619255 906779789 455343560 934612848 242182911 394076041 719768464 331183976 506165169 434853443 305732863 280419462 316945740 144981042 682612249 953165245 619657107 568462874 418925440 294859223 582583305 767138080 133869232 775981623 608830856 743937237 165359980 871060216 684010808 753524745 845149637 983855951 42941131 154246012 857259312 244027968 376371776 52585007 785945891 577251786 361463189 445223654 945972282 336257267 501135801 349112392 356052630 790989203 331543927 249353275 602876220 434474586 839909656 181926471 956236230 215798295 177174800 57619505 72888993 758656310 296238358 565484569 972524906 710882081 373602255 290229471 351609554 216398705 61875699 752991222 751001482 1634123 119322006 342129016 369116542 474169105 756476967 642750297 448359862 927001530 733094379 289406657 121452048 915737620 130928659 133992103 752704055 543801458 784281034 530566134 669137553 33643763 75494842 827200419 271187403 632627157 606022801 503651022 926963723 543389436 308117624 588131998 446747464 979008224 809956934 234499777 73931381 724320047 581405576 382711367 69802810 822548504 705463400 717331793 331524076 811386421 602451863 885604257 29580420 82557307 639594476 988759675 137649499 965474513 947567591 581460559 29848687 871747060 923568401 428052906 311614419 871133913 188499012 433820799 919734201 171155126 289678979 525502222 606997952 379851966 185510493 545737890 790851950 650864891 93447017 71564487 119120718 348838388 850140242 789246049 198237967 524099590 815815859 157221821 319650681 79503010 13304256 954422311 867467960 751102118 537760969 198812609 312640050 94594788 264999015 286702578 826047887 355882166 444908885 384229196 533782561 876674646 481368322 886212329 386654494 628489613 356104605 186175818 556611319 223076920 20962715 916113964 841181277 72798128 259414034 864121708 187340210 151783704 590683363 733964413 698973796 415365396 924512437 478013483 911442120 969952396 980374035 312488011 314697200 984040129 482669439 964555823 12490319 152536370 495569989 395088462 167480836 489524431 553126159 975637340 661715191 655800134 698307766 491023907 369320484 20451581 224053055 697533672 699078844 508356956 8281360 703159293 383831608 282339354 281005407 668254113 953208566 561328442 161492130 326863538 482075724 543398508 106642937 660146398 687302798 743047087 19013162 333621700 87592748 254620028 968401139 299012979 912082160 91319562 672660194 894613267 799237633 525214481 548115194 352600255 747488517 361137737 937655730 149199655 295664161 489349699 765678466 200298317 712181193 152796816 448347048 290605480 596439820 604011745 140348410 834509445 635482634 376051561 672154696 580953669 646977294 359912131 787454251 223763859 386410440 758050335 453461783 660224971 5049600 232813919 74615405 923896900 507672716 683171942 477124596 551502775 873916438 989930016 172242039 51189452 323417759 740779633 424141677 606417758 851541493 481716506 287575772 196209049 75635702 349107209 154575277 350053142 69640801 66297450 872926877 632238943 223593781 672889777 2973595 429985621 984023534 483737538 785669647 667766677 791178279 811535788 488804568 925183696 428327139 230440061 289416570 667507346 942197151 554639728 81116534 355441602 849710674 163745061 769527252 556424914 983937131 53979897 144326908 484945376 158767265 887991820 479278906 669552171 441818640 239522061 874885684 555588335 504992573 750377894 637129483 386057868 637924634 442796573 392077796 684373955 916586646 564539767 233857152 78071920 360305364 563040911 397513111 401163064 424462283 50054647 809382941 70418454 617417989 810762702 100617670 909190740 701005418 762272243 894073341 91920288 950379859 386542044 173720901 524101022 977418489 899653846 868264847 981987687 762441634 475445972 832411559 464282817 587586464 40702500 68044529 379629707 275884073 556518464 840668398 860773711 413439486 368193084 946066768 612984016 157696302 337389894 895696907 360684462 146864277 86165145 309725213 415369530 857126919 73935447 477212563 531695806 275021837 196815836 808893644 576417561 897407026 871615548 575959255 768283950 698960880 360499728 105253156 360756818 504305929 819744353 431875721 88873699 914811420 499456406 556078102 14808654 354919761 628976470 483794759 960339709 337020928 522246938 183783100 899680383 245428638 416786929 76711349 83768581 273062843 507950973 658794656 878741381 193308766 20470447 847049812 859402425 745616255 39365224 703108214 457727182 211208664 228061938 153028269 448906072 774135225 167761380 794006769 419727823 691553957 211551661 141589038 204588567 925014823 786488908 534256075 545181683 854870377 943368477 880915857 868742034 833193614 907687088 340961078 202478435 640717733 216912911 89043437 337975626 393956307 484181014 604916546 221820013 750119437 293002133 476978734 923157304 993117940 107345942 529084800 981957416 685233875 7434267 381305212 603490904 108210290 808689796 447632833 367007938 503586708 230046817 969893904 150811033 506643984 563908443 613246760 978764781 621411052 661486058 550212813 364922005 470877515 256078669 747187882 431783551 121030452 802177186 778837566 995086566 935023861 214375671 566704549 794636918 57658441 413300158 628753696 488711451 381821020 9121353 37743979 143050058 187910111 343895718 365067842 472762558 606666859 612470510 31611551 20789537 810587579 385957280 703959206 308376180 432495588 857712692 587453152 395237563 951078014 902514462 64397322 10482906 457116253 873553002 524854125 951454522 958706779 392002272 417884502 476414225 150571288 242277286 423962882 19994438 855104334 745065687 661519528 243006030 612553615 120199327 426160610 820602630 534157859 363665417 185094347 497227548 947278600 401020910 210956147 236351517 326369092 794680467 878637881 971749821 540094330 524895426 157672600 396455037 771391262 241706638 828839064 114469143 390444404 133183536 864830810 772473032 729006175 461482395 111590035 779032879 490019645 102660989 246950167 753886356 200777884 94012930 343350197 854242768 977981714 210425548 473947948 86352106 555976749 761332811 408304903 346845461 332941838 837980545 14750232 474014081 889093892 249690376 456963363 865403667 909943249 214980594 381625762 930514393 584648725 807595643 270697246 552904077 708879588 533284933 182629959 805024073 548695664 169454004 889348274 210679214 563296593 232892373 221725127 491405870 326690573 87537323 638806830 540643338 409113079 315538725 695709469 184959834 147268406 351034323 763266632 652475492 638587764 795052059 256380682 84366112 866980567 858248229 749153807 272427330 180872451 978573000 902801791 735508883 252999412 108378501 641942777 207772915 650039603 815894610 288417895 999227930 849120943 682706182 313738636 394489466 234959533 735160448 168413959 698829604 678508727 114202792 319754657 91919139 657951070 184882985 239828969 703014365 246492107 540675860 443716148 794862857 419939967 496327763 436676486 75571452 660813196 516689381 118756521 924514830 27616970 89515522 595275451 940215561 219823631 564347765 760448660 958088245 191516480 960263137 576669674 605788429 119161135 888536860 302943182 190479649 227377565 13068325 654224635 517741580 456480106 136332608 555961580 727706221 936241063 179037124 123258201 214756620 57453901 40891089 813342340 55007385 934219890 938697270 491996925 207890300 802706625 285719838 697198183 919633829 604907626 690278404 742957813 138573087 132159387 70385632 840325145 245877415 879310330 321426040 268602908 902624003 296005465 492192094 73132250 297624926 129419499 766472992 888415872 988140531 152783523 671818524 748904548 278991090 650198462 518637140 987858807 435681154 406630835 4859260 210640846 962524281 984363775 824739009 252004530 903450308 355484059 601000222 214023091 97913582 113679050 495896703 756683981 654642157 550124333 108304370 390411019 448448215 940771172 423926865 517539809 835429854 278391934 799762511 55082371 236058234 224009656 74672244 116771132 856553522 611383519 156847195 190182865 947101164 384860789 430601309 161339583 434394113 109973141 145523467 736623115 655232347 207146197 505259730 438839962 230672124 319944739 206042408 638949675 926335710 317347637 958255711 536511932 950060088 219723305 15405727 770514776 951161319 406682474 365851286 48200479 926220707 411229377 614663275 931759908 179770558 27698684 478680016 154291833 149133973 973627272 815973847 162653014 602615697 865997571 34724241 398455820 279655809 938202964 852473442 410181888 912719976 620414550 836103028 995561708 769624956 173273403 750679615 14213209 279460066 313474623 102258836 986727335 325827547 978002820 407574748 766030673 935382306 575094883 857546154 968641644 162388133 84461225 291022050 232634474 61490955 233904756 153357817 606908339 3576405 465225136 918162068 318702414 395104816 914340755 658097550 723938915 931592921 320563185 664528570 55137146 336484582 726454145 848078299 389632732 409947490 563263466 582820193 993935529 100053553 576000448 538674340 536555339 604950093 539594719 547860955 982524141 670476472 853295587 977495632 984042081 113206695 618467810 934079287 131990731 910902805 453340378 609961806 2874613 924958635 813292671 371359983 773879387 946733931 438818293 610377191 31457430 637978748 67555042 361117501 426845386 794681919 915907777 898820660 868975373 188530151 495412642 709836994 537512318 6355261 709931057 407594984 233287362 383369464 494021077 694773589 444185214 525912107 924237997 217713925 774129976 483981450 204711412 454009061 294671185 102247464 68674502 788745617 636760272 773298013 808815652 127861501 9409086 663137026 45531624 765417089 117271121 889234956 570859016 364051562 130699911 706118087 295861293 187745655 104827472 691200795 196978689 838508237 127827478 781296859 389400075 333728960 221132796 350280264 798262277 841336592 64507137 784454348 762617839 487761374 161361001 728925187 55273782 648748241 92239985 145372973 67126888 448636807 780552924 917368152 772834376 109370360 39500243 647951614 847384253 370379229 682279443 119847686 511600 529167585 842183170 413911152 663245370 702733876 184448911 145611638 166545044 812307704 162678011 500576969 249497444 101783777 650640137 523419800 549246549 170964428 777991582 917532460 506980287 86410645 600966331 931179781 378980917 984468191 945858801 562082149 739783450 615764921 595054420 867669027 906812306 238634042 208666130 321926524 154042439 459519801 148780970 286328809 412818637 875931092 448869835 216827012 244371967 821703706 599517027 296174108 431454007 906274007 268096427 294573159 110964001 293931981 978831884 656266246 438598680 126281692 47417902 262570645 951279751 546275512 185285576 167860887 32613058 963647156 470620194 45170470 55444569 229438203 114629199 860814548 210473533 97810058 15299848 921862291 852225108 805017287 59141508 364895014 769923710 160164176 692564282 974225204 875180186 259829826 692273352 776847422 47300586 801952925 431700644 428236373 632983537 248122846 388406733 579766339 17766044 602769886 125384278 578841346 479051425 165240877 644954904 718703017 774221434 634307609 317071637 721204875 631281412 456131261 264334255 678919158 461482931 607557802 986539295 420970443 657442291 54582498 856619748 928417570 359579544 537463825 846184351 673681455 470809412 202045737 453200384 410842200 848332015 292548973 422852126 218239943 314162217 937132731 13612993 722015167 936382139 971955948 273458818 649992862 287034374 495302739 219769625 79386092 626014832 702510945 628273701 983702463 581170522 404218418 763786420 722767686 997208715 596459669 247698946 186708254 30338425 443954231 227787004 22384634 500463019 748118331 886642428 966170548 102184525 861436235 574487773 101391308 145578213 760792014 66478420 887151369 739765383 792516271 437859403 139345123 513508575 622595101 409472948 592868670 453039799 215413412 362185876 943327667 273357766 514294216 397285978 57948316 819110761 149843385 967266204 688614733 505338211 446995234 121590051 825455562 606074908 683721620 642463171 693262307 294630086 228981415 542248174 415780128 970935993 749134840 307800439 290634835 663012921 93314876 80993346 573825367 360708582 81729219 976356019 81388000 504542123 286540612 160753625 881465295 487981670 939492238 227836148 939218571 906209407 670061698 837257621 201230241 375816235 605885824 33541633 605465224 451788418 325085451 530068692 748975404 528728864 468185245 336703002 217110038 298035432 410773889 455420533 206059635 864473733 928463650 422929481 43544438 985895854 603866089 573717447 752150552 4760717 217217128 66304597 603408277 247818086 17593998 996066388 165952325 438062736 972380096 37638816 375227693 660672620 758982516 280143656 972778007 820868340 104329125 352281877 976414990 490150796 915691759 416257032 139991607 853152168 744882183 62043618 102188249 971339171 814098187 833223897 599315376 703203547 857679515 994324636 788069019 274836544 210258568 284590852 447428203 455755066 564751234 479211280 146886066 150994417 181401163 368393422 467340478 698896621 217769079 107926202 872701533 761774191 578499591 287963009 297287567 108986671 182944206 950124312 377409380 455017948 203674966 828289890 82501078 51240438 823411051 919301303 727986707 285677954 24544592 740277667 98330066 993735740 439781783 695157501 958932111 189303208 367896218 401637496 830122248 557612560 820366329 586976067 297399219 895137594 265982802 767311753 200069106 421680379 704254756 296706637 128577930 303835392 872118108 463308071 782468081 367734740 385122586 850235544 916359151 646413626 434851118 628150936 342070532 595849206 860089782 788827350 119344271 552037436 959908263 253738322 610569433 775841552 181561218 474047122 325613276 719135465 155845084 813487654 212317439 485084347 395474386 769582840 862544774 674950074 321963029 543669976 189282055 595817739 481076421 119633928 296114984 771332111 488803340 105248746 311745571 953654688 897417977 331151342 138453931 763964846 128230935 840209532 491914406 705882516 403857572 708150534 708355733 84206020 943234922 58932880 233024044 47594914 520681598 652000983 538081497 954022652 370498029 849876369 44764023 595617478 320407305 250574661 629958714 567882267 352888703 27451115 236197194 503583482 547305896 29821847 887141465 925414307 499045907 621370441 527745473 856124962 191928721 958672326 851955385 82516000 439833454 833190599 541493767 855868367 308826129 741950650 245368486 768206378 651649700 544120784 354301739 521040828 548209745 952624203 673042538 200548736 464093365 567792588 616978374 389180797 272262746 66029274 106124457 646862712 821141743 36314661 715676323 981629896 465367917 68049944 722695796 935248818 734257062 868690751 296662092 454366031 986034151 841594938 373620400 2225908 57991925 18858347 369589630 126466505 33382900 648263630 875244728 79605660 423625707 964077034 9456624 412895076 324265237 233825004 716066350 599846614 131934360 526573409 514918797 354340010 353335868 80420140 788959222 691828931 58607527 374948545 976987563 363919920 664195485 545661184 350238991 912501734 878689808 634719500 982549027 604399400 144612866 514929201 982102390 177660695 438413778 491370687 121043685 2522983 6927384 544319868 856682933 782879308 572367148 753400480 498236002 218053660 392591002 647481067 520905501 827349019 395754499 509950832 391419974 329060870 418941155 956866051 675144915 936306395 923267705 163668126 146541674 182476154 436632066 711365104 529715693 664228289 883498633 140642752 48036869 273893700 647146060 917715621 824051619 86778241 635446408 428053772 948250322 53528742 558951474 135875402 829822949 273124530 216371742 149598067 100645686 776684114 141867717 354553404 360308533 201990144 567277119 301373767 905896891 99039700 806448668 383301134 966641014 627232801 84622989 121528295 582126069 780630281 51104171 160754373 53832961 799664414 92036458 206607975 94224797 858693810 175012861 617880725 766323524 535081244 4156200 197868645 520331851 667727783 129714149 29420671 433811867 669918914 724603730 640188024 190376041 850647314 585016669 820379673 355717745 652599963 285583680 42858722 534376648 687728922 923247668 696016110 671788173 195563451 105649834 243464334 680866142 178900975 93974345 688480068 595300654 383218599 683481170 384669014 347026461 403169945 499015771 63503269 508893297 730293097 698850333 503989057 789266294 277636959 624491115 521949674 878973444 149207198 343678758 904225333 216499309 64679391 211393743 672661773 513815107 353019412 333456820 468723750 158982190 736634554 814278993 861914565 65863456 311088473 121793273 842105560 412559217 448810844 107062890 708260041 94176161 321263438 990190483 211470548 464086049 553482516 58116425 778023257 239828616 311035503 47460632 944276463 433502804 400135517 258245556 87600667 358676408 84335502 907330421 482787773 185310721 185895357 4531154 204230102 463020900 220603782 925833678 400896432 95977369 606114585 487063531 440877857 600283865 475491389 303346936 302856089 254460457 349095370 603713666 352057691 835768528 608476316 691978742 333110592 421153147 310207346 225235671 522982597 832457598 537504247 774389782 999636669 218587590 788033279 296116041 545306064 186547515 517575775 750653283 60431362 297699454 673805841 133495142 296684707 507916932 581771281 967201967 42722036 272585886 785365169 918609773 624793162 82715905 500736874 359718222 99308728 4531301 80185054 100986071 612687819 535534751 669710442 715311213 755394607 129818939 465302026 899489999 507954783 175918502 529060332 72560272 340165312 847247977 741533621 989935869 994428498 641027256 64884339 980041848 282770407 548684760 35031830 907327975 871172485 845404001 185751490 131901101 185365839 622633929 557355004 184816333 148838798 707498686 747675821 928580474 356566834 877084575 651906137 558473720 849012608 631778576 635709731 636507091 501286506 407977369 492209404 453413168 93475703 67884430 144879399 866286000 526629752 451767497 205800526 661796868 358054942 365648069 971947270 217512366 379829553 819164418 402862671 823961595 787824062 611823890 37394056 445356587 995674660 553380593 582858282 604564515 893850042 478143110 670923412 667059994 801207482 363846292 311147005 668853295 155904635 885900929 323545134 538110739 336438696 636672852 569414316 331470425 298663713 605125308 41216425 602171579 262739778 188849969 536745666 126853573 184314950 745054941 867356591 363775031 419245481 286964269 310479664 578996189 928269649 710164449 799729821 891304824 540018701 899811604 643834107 897371403 858031738 809084029 636065 188541303 886447469 142357565 39358442 164670993 789077652 629835685 185075062 34104242 468645995 904595514 943368362 272077589 762032334 234988050 460439180 65295265 606181727 72964639 942902058 144448187 434499916 197875858 604322783 289395883 835488401 17211401 681042512 856844958 778802324 856409973 251108934 747664926 922269990 39314678 256426688 950448363 366125916 496692527 374253703 129654337 258795930 373939814 531175061 857712099 45828060 625827871 214262939 665687552 141613148 848941819 310167520 923337523 36664856 438916938 451743997 628661056 264557098 715744501 394127380 264966699 50444618 657821232 297842425 559490798 803286050 933273869 873495466 308314533 612097995 831365133 803335989 598789590 84678026 392958429 522952895 859433446 109527803 78304343 800091599 701110634 595643734 584198830 133756240 857310966 985169655 989478199 261178450 694093449 559602208 455733360 215482751 562830049 59718940 32157266 989703097 413681955 193979527 944401522 825162491 789463151 224740840 235829754 340596341 133930374 942623329 18951869 131512671 552046030 429424481 689782269 152879986 109819983 860389542 664272415 402373689 219848240 664599857 769695014 664262753 489771595 835212394 630416111 847847687 789763824 904738382 385427829 795225491 162750511 586283341 658332523 437306437 295566598 837749363 704990154 766472031 238902182 997464265 33280052 397283235 822219076 96818539 887308360 40353013 208106466 754267127 385655548 453433757 957558686 188550404 204279642 251871742 948842291 224787454 180573655 465722177 628938362 183811118 721631233 54233384 242138620 479266742 994475361 51809216 723354498 703971810 89210394 808229117 72092176 951552309 537730278 268951419 767092932 127249132 595808225 868530260 676207740 174959056 916710211 552440321 288515882 133517925 450083097 98368302 919160328 807239074 849686492 307989656 697371959 5381207 658918808 829368364 739428082 937843149 530294871 527533935 642015218 124481963 898178740 46652746 7939369 916356962 767300787 740678428 44281887 341704240 373432176 329540192 350626171 814597306 289596865 918585408 913588829 382573127 508319006 759546608 309938584 419256723 900598886 580162461 891159021 108201075 509387372 742539336 167439639 588836705 102606626 367840203 24915918 135987664 113841125 177157781 535524567 270735653 608285083 928988216 654552786 335212200 35489976 22169278 901108757 44814901 914307352 350254683 164116935 84794603 954918521 497259921 746057579 669601532 195009689 262784817 776610428 973309397 4479546 577607750 150882170 501710818 136062830 405182844 19280096 626740188 620562525 763663344 437500134 273928321 61106377 918316575 287173113 615301496 292589681 63313318 899285213 383085958 640020139 518087918 198825419 807872720 541103257 411109067 129887295 31923705 601656604 723817325 686638324 893396742 864028457 964924519 753023681 936242938 986745464 270169998 650402635 106909349 857289953 389260054 135108237 730445516 191289415 276373086 771259435 617167795 410935273 694562356 555312622 120527651 831111224 576520275 653841758 967725145 379929544 612263395 174940718 62199230 237029046 900742470 591387674 618833067 982078740 559985615 903736086 218146786 233837713 629281949 711080208 985714923 155437782 373721692 388974153 944605789 914767211 568360030 130361338 616140643 864429704 769216242 169525530 216049621 456014379 682835864 429969064 82234663 49202828 120298266 636365475 740390651 606090126 308598749 222126043 874364817 240091686 276406213 615722814 680580494 649514580 584051879 378233201 715052706 229377119 485698857 81243355 748462121 239617010 949714839 356282172 959534136 654332885 197647493 200862341 348185563 988469202 686992703 351137030 929171081 340451504 73830475 513267206 388261750 954336056 825984970 29468294 314073906 236576901 819208300 753654813 494096484 633669021 158531211 622844924 651905788 445346925 720346940 814789312 19220480 14100983 528868000 215271199 278735630 440404340 871887270 547532315 100006771 597515283 129715877 883152686 302270491 356735003 737799141 651548995 98631452 928123784 993406927 703367577 360547116 621257840 199249483 826368535 86286062 575672435 112738938 610351480 879498328 717805652 58095295 165983874 596722857 592431803 628203755 132287725 578001722 676037298 387759988 721654024 637251196 873525832 600540744 289809881 205520064 570549119 55192339 162918367 745464546 121015347 25274800 947267703 81099832 608019829 773027044 548627775 461433115 708503867 351391723 32297320 424338838 815156828 140238127 518304485 122886525 896427740 699486536 876988822 294634363 817685006 545439688 231507854 939360914 129096804 100299161 738431806 540714702 392267399 755913504 918186491 90201716 605043180 955885667 758560243 304168777 958674924 794372779 301539905 476652416 516182848 964249484 838055290 123497894 702528999 341318061 942305191 742955033 569627320 220880180 84503542 456751033 750758961 223497232 217046724 284229401 774679847 518915550 797071685 928490873 485296145 797613090 85124873 985683633 375468960 98752352 916655680 186152684 297845226 430983390 786593754 769673444 855360889 965724088 728155810 666888566 516171132 712179325 236598010 401126811 347424329 124025294 378991061 84552080 298225666 598453587 232424772 253697493 937712384 845528952 134644616 883780761 191912669 456359434 197734947 289099195 264609336 418127467 784400889 470859731 557600001 845933608 130992231 280042295 644208994 192621816 10442699 883495609 7818064 425150697 821336573 486372765 409698749 695713197 612960217 606243723 135305521 143262781 163414329 116263561 528867482 936601650 612717589 959769977 632188252 997694860 86426228 609268698 953255698 342964274 303118299 333119966 674899414 744476428 177748732 360074660 744023682 513933787 853416887 396412564 269790972 312139582 783852219 100559885 912173819 737500987 461460959 844585239 357734309 270894810 889730174 943474452 497694042 109053229 128244436 707119653 41781692 969997781 186368221 906429251 14013798 572231385 729280516 140122630 736609621 441592035 305390111 642735032 961277321 954119931 958319900 799079137 142548343 198919983 578755846 151148719 974653903 702236473 804007011 183517021 327036309 33196571 847362896 504286583 967840852 976891812 447203030 591479475 843357262 839175923 514244084 225553742 811376981 865599969 233448263 931087091 713760975 77006291 971522997 37011798 870011000 64573046 716026574 885837104 894114105 19196968 258097918 794531420 945822416 480873870 553618299 108279473 23005312 759820028 949507564 869805961 119445822 72304688 273774908 851575855 758836744 235452921 907176760 637679064 499845024 525834573 273003520 404593255 265471889 244717661 887168791 793409570 619599918 180196443 606531754 842131885 336864453 909360742 461331286 501224215 911536926 525034528 476765615 431705792 409034965 761737885 955063725 745671272 485582102 843511614 668359161 2004808 991260777 44250885 985518445 198315009 75458379 890309892 725137069 730034271 676349879 203812540 325479002 914947580 868041229 680424600 720236065 880930719 133705033 244267450 479566226 452629947 176310706 794593101 354194797 668435893 918345022 219015111 279120675 39527851 862152310 607637198 531923787 875844039 604051606 565835453 627079281 907419614 705698779 997473902 513503125 709709784 235934224 208370168 254572867 636920580 456425774 660520948 521825682 911512267 993593008 800967454 568908714 145809863 260408491 622988609 436478326 371652585 234483416 907598281 292031690 502342278 378793129 650149697 471351043 196419994 689361809 578241773 925262089 765162220 827598971 313667195 160609953 162017695 886236037 648852176 802848182 54580876 318500679 556540032 523019114 65892974 981917383 52638956 114946227 94551094 786738722 733333227 527007424 715121243 896853793 621136700 503150242 650959927 634762640 223405764 974405728 633432579 867089909 280235932 995072821 233337120 94631338 639120017 450837379 627358074 458126222 681629520 659281218 671873416 211026065 968989455 715116796 551688994 71104688 894745860 223309366 4974335 367054322 468116409 760015942 760500207 592868499 976506995 961941318 855847874 372840534 379078524 690252256 34082571 268705191 962822631 673102460 452800257 627181802 913055250 858843209 566801004 714976758 661136176 100715564 476449285 217475382 808300842 679318279 805291595 381573523 680366989 322179638 818144124 747449355 81633855 895121599 790085512 906530823 840288969 339680555 983100938 445135509 54295443 461368249 810978083 704933152 459174618 360351941 986337529 669125875 649503729 580031 81954709 677093367 174355170 903812964 50378801 266391402 440964085 770428475 759449237 304079285 670485348 664354799 830243126 394486192 250694732 40368046 45206172 647402448 391991435 284441625 311653056 26564802 562975195 369210619 915109156 856502893 276561053 243174443 597627927 497211348 221898423 296552616 205909435 830810184 330369153 671964174 9106496 626200483 406737352 853923886 738290153 537977469 18058921 806224029 707225839 908154468 814382100 974722695 316218580 875505868 956390342 876497903 893828664 754972857 299405104 42449340 965601391 497265964 18771935 467882054 270883598 630302884 506263910 58893228 405970358 213388530 315806820 373988856 264528381 197575470 772155496 959840572 596293674 512738840 656331922 284596120 273662701 267358604 846738137 188456568 809964115 142698716 767132578 734466488 730706890 350473120 621447895 246444190 743650933 606660103 6847127 799258486 916663810 605922626 32065320 467781853 183984545 659377628 743606632 453911228 122855701 77224155 556975928 181062441 751233028 693675021 859327558 491775879 457968016 140839676 613208197 570035194 422425742 471903834 328892374 193938116 602854662 285836567 540154943 293064023 464881222 325365782 129761734 661420500 685550968 543675231 883550641 598856781 860076952 493191905 117090357 808133523 331008575 394062823 945083905 511281537 46374902 874391349 332398954 440437015 509956592 266859762 458802136 506614778 504148539 63530829 241091416 90697312 923218617 571286886 902595044 390178038 794238372 925166826 626377174 603400420 282546274 746574047 361799001 150791467 135711337 462308888 689926134 563429885 957796120 108307283 665266047 107679389 369153668 915851541 473099896 306465206 287162891 104763440 170400633 363107340 727485609 440611110 794906228 50698847 539901625 153195369 906253230 162370021 155162375 432825194 300519634 556239605 359480991 334343496 186136585 375802528 301907462 720610651 252674302 647805989 468266663 787530105 205867201 534297988 642433277 24866345 909067205 590383789 181633529 850720659 541992647 735041060 511378966 653329571 45831649 678698579 229796129 454715656 332666383 871367293 43652937 447577444 445534260 450031968 990182570 396962216 86759138 295575677 672788097 830104314 80343591 311243268 51767754 742216312 643347004 890975902 143107872 774161314 155444285 1288046 148545172 232342935 944807479 93530383 7906728 451213044 194456165 843123599 367615429 746522046 674578725 245234857 775914253 327439092 925618372 485884816 7904092 84606371 33652876 341912742 904691191 947406329 977089786 659292488 995466818 939740836 884441736 338173919 5466191 118481281 525562871 244568360 356676864 330592860 338980531 51648982 596489775 819895322 810486397 468601849 318393094 176244895 144035906 777539596 143060471 107834997 801205212 803317624 148708659 115824807 359486852 19085900 305281109 424283629 104019047 948276456 893109885 873365071 950458651 935147030 756024227 718511496 622461603 459416204 599136755 273266368 120457135 88135108 432868524 51720097 453507901 848788852 198338713 977986878 532078204 321241851 301363613 144544658 92056205 618026060 697378733 807817642 679602370 908877764 604223598 58880774 217268369 261486718 106135376 208300454 288863612 717890184 577355734 970946306 185276499 503754257 137667797 282443759 773399732 652542493 855264888 79814739 298189015 33035061 281301499 989655877 115249107 318885421 800661559 723401102 434776256 484321660 888953349 570647215 650963867 770957610 391359346 765235297 122557950 80706455 335922745 369701933 790564706 131899593 755331766 632032304 290446966 696047329 656733551 543186407 656975386 745439418 348079197 424257463 215462335 28769202 607713456 342424021 511085363 221274718 543580156 592341206 938633627 271673795 909721070 245996591 454126331 77288160 71451264 326846298 56326342 22975062 744266611 880251629 672787339 8984564 422442368 529396065 410106991 386313710 808653431 739788435 408919611 250004295 552402517 954863631 393073829 635045499 607285031 498569382 768697876 335104336 523628659 37054983 248034342 924356307 165011955 113483014 907269785 181927586 805151089 416590488 743730038 932168271 498120403 583759239 408313159 607707330 272046834 586766640 244271531 798618437 361521876 287963329 561792365 401329764 100199669 21425241 177230418 239516333 418087302 535072748 703752951 16094696 558428735 610649026 780902485 14411440 759230126 970811999 519454176 975189144 970263089 976588251 143720094 915836337 779175533 20011745 654930658 940595573 297040661 406740967 940901346 745590921 706625978 318427078 287633091 924636487 260428484 926184676 868815103 900822838 766948880 357125334 403321763 424345577 475141361 993063734 524143883 998955029 348925583 545953051 779868292 39930562 489954001 455254886 323420986 358048924 840255950 896765599 474986644 736750180 836339143 332320830 269180602 811557863 559936347 955208717 806842550 214264683 368715293 575034574 75782306 371109061 883127412 511092251 851625731 662038360 290575714 988199052 456098734 210710835 964369581 328450398 952931824 121189782 381609863 518496858 787583926 2357221 503246394 109964406 817956975 763951447 211507241 845154371 834475396 398842635 580419713 990301972 593710120 476091085 919450907 272463869 186900715 266457280 341892020 509366766 292282873 312105930 529909728 41788900 157932962 143272313 267585541 82732636 330729818 411085082 448987438 563534796 588268265 361191618 916316512 31658794 900768497 58729131 243876485 410840997 910971715 906695040 287310261 936434289 52306346 967088354 179990005 755318084 14912760 927728525 784361435 744016121 512058797 286073943 757651243 54454595 650810997 118713087 410738894 928266817 609743 216967095 333412502 849502802 912899233 360801830 341710082 654208289 455518797 317442850 738810670 324052775 629128963 265488190 135063159 503202205 768585751 118643343 532493637 761752265 159382476 397616099 512694659 784130793 208670944 463864652 522656037 977862931 665744331 388776387 962837820 433916614 9571233 375832847 722208740 393380293 695387634 41418717 263369819 270071062 73435263 48068469 919856182 277067579 181117298 374252681 320182505 921985576 688169251 942473074 690672652 240205718 285913510 230679274 500241655 538765252 795048393 472212397 400739898 370078357 329303283 502863500 237853227 494953585 505565684 801821750 123124282 893668723 333701485 837349761 488341008 178435400 424186674 901613775 355712610 629371675 911820139 883265245 505774163 500366609 824636322 946568819 152525173 752449975 295163606 309174745 506791237 420090408 467062497 739639167 197849474 945145556 889654913 298779824 539660461 694877623 505784782 716557316 17778780 856547853 444040420 240777992 46570558 447524439 374752319 842100396 310964916 971086561 146337636 793256561 600868712 771829667 801700484 241038477 970651732 69806851 123023006 828304763 273697241 575760144 824165947 514403981 784848613 91627147 323539530 528424562 24208880 251402416 982075129 21880307 78286908 459436168 573301013 856315959 541605578 160806957 424965644 934168822 111076034 577095448 824799841 159264671 572115831 488202282 787042978 113862609 609951835 106014699 61993100 61241747 675940881 406695781 79726532 195798628 614755188 846667466 385232490 991591475 696071787 668588463 53256377 990611123 624558801 133788072 220713476 511232954 391032078 962618482 715488401 222747760 626864286 860026715 620182729 22076123 94496505 289863775 924044860 371136195 681124642 738987976 892695005 993975727 552863847 675468421 252953677 578090153 571040057 432274216 899906296 60524651 53932376 107309715 919074853 505989289 634452545 110413346 873230852 453063683 993101221 354727334 804897091 834273569 925125620 639856483 167259101 853926559 63395385 619902609 892369725 415166135 24358631 624382216 495560773 496201223 109525607 567442486 176540949 11285064 784034339 128248329 757610572 186518640 326667555 916730590 964476982 461671715 310614855 532092621 482903479 54424809 248171114 2873434 419504285 279937641 624048703 813575700 448328494 968529885 341764003 472608667 7462468 377790427 848242957 496393219 61077210 453823229 5137757 204568742 61843543 921392008 645584914 214327874 800771911 410961595 174267295 369165670 306319578 692692270 234139847 77632073 645322889 909489695 305930006 618162611 68771439 36397029 317844073 186770728 943432826 447173224 586259117 377056383 556042073 193369346 449515626 101074876 747149441 663072334 547047152 80230381 405386870 828582851 680895098 59349967 915076436 286655552 370798328 869536007 220567148 149918519 894595242 650449287 957243407 8083513 547710331 636856352 168832744 213414903 20203923 180556465 380027799 266839822 514463159 707575023 678465154 580192041 222912535 911858505 760733973 230472997 733497904 978446714 401679871 738393029 368895197 445955107 926307295 393514319 334791973 906009297 979314728 623185555 658705669 836271396 839942456 132231596 559705001 540239700 155566476 843355449 510196021 142196546 749904895 23612750 671357849 851404134 930211846 929395385 730864759 440804541 323682177 618871259 368879277 602101043 213665088 459053079 93270006 572155949 433074394 98210108 162608530 33914661 586465100 911098008 536133010 882485086 113977366 551214931 865986517 726889622 930139571 282265193 688130363 415977952 740621813 139533056 903918804 146364457 371623516 659169952 340548206 723897450 201253235 559505521 889804059 330922308 22042079 163672081 630596022 790761797 694314249 904418042 352206888 356652682 389210122 88426103 493482254 888372449 596101000 150204632 413825757 648922165 622581437 250524544 617599740 299199191 512890568 295239322 754338201 453924061 995643413 772348693 509812963 922158394 612975802 986687704 107557070 895836881 627047661 274230115 718808527 58278835 839953578 673335045 919475488 758001959 850522400 804518421 201434733 715486781 858542464 549798643 555102869 481569578 438056302 270292000 406538112 361888265 463789691 664782400 63681714 59603202 140478243 99717929 428887682 941136955 783983037 429365212 374813190 805168456 640382439 175674287 370575949 964195599 657275230 503291045 481712091 830360610 188141612 610814256 344550821 214702908 904657970 179222804 775786512 249638239 258763393 250417920 369014027 881830469 137897561 919552438 646114269 735292706 741672813 885111041 417203898 87005624 31088699 181104667 93234878 299992941 249116279 745279171 929664438 258618444 847254134 218181737 295219497 553932705 824593903 673976533 879602513 329974769 374639853 72943685 442945342 916940421 108100443 485866739 371787815 316650521 856759370 39063997 496455755 150406582 35535743 328793056 117768956 303491108 530805814 792787792 32102785 245837159 803264470 347745923 108443631 392756368 723781669 223806118 357432429 998976676 694396443 582443778 695776812 90534749 175495083 612539481 307782575 379006976 618818636 247285471 890344522 922912681 731154375 89341567 39925590 865226215 848028573 144597761 562208570 95431106 41029698 122842279 554910188 115990314 132813306 664184748 205473284 429116891 31979627 609055924 320077476 10098057 574323967 654603924 375349766 120061960 511539845 194250517 994946234 326526012 870437060 333546048 704948633 864261400 295669181 508061380 911889070 443334114 155136770 172286492 591132847 466083592 74918891 74098138 71738834 688917752 444227753 544159316 96433522 937074480 757867977 735242447 208739556 608424290 289027829 887497830 5802444 578526305 689140905 518835776 519076320 127612186 664015875 541109382 330831123 522041522 599248659 219401586 317593733 365319702 989198419 856401577 578087628 425963445 774490769 178519740 30550818 382424691 485112856 641287434 792802696 547982830 762606493 79133143 299207406 491825151 470015067 785953475 608713213 237566091 488752992 752606968 318377298 317994419 575802812 525950771 151814593 722740216 424597489 523082864 945660954 893272865 382287230 674552807 411898518 312712150 932589883 85670387 655645643 937105784 943514438 647845892 544134185 403863406 513878874 79979705 800225573 653771180 258926005 399334184 882899520 722405711 637878412 937037916 650960835 478630463 835905123 120108217 624055639 306759999 383385814 75473352 235997846 127092857 308904110 768183472 437757428 73941332 313363462 888839953 408682250 197388728 151256673 916406926 202449305 984211353 208483446 282628269 734494634 929226461 29698849 85478378 997251661 568586132 947350282 121842053 724869286 265022356 566459981 337114118 308987644 98159428 131447637 165421005 48676828 527890641 182480292 744107786 895304385 688687959 775363672 641466018 911659980 726009637 404959128 994065092 412107242 375238267 162626052 179892747 805495517 429886310 225592530 423463610 287750628 924754845 356482778 383163502 72499516 409266761 918007680 545488873 482473837 805207877 795768222 36901339 250088485 956102253 5443066 586280007 25619031 63014544 237842677 180920069 928449405 253274891 33767392 520393915 182023702 64094982 381390643 728464423 495173342 264381333 200652576 710084022 967786887 286924062 801892079 422153379 734705046 721865417 409247534 805502758 826658859 238518001 908227820 726827786 639522373 696781015 709123416 807732557 7412566 838707688 19635372 146818505 799424218 319041505 282348131 771010400 227001852 696914989 69236602 228551317 156754845 388686838 61840268 310184795 612274344 574060032 183911364 569196677 73693439 319317000 782407993 343194714 306132530 193404997 408559458 931058510 102432390 198540465 691065074 989094188 690316707 588048719 538895310 621188090 911792723 947520501 774720935 610965079 890803244 255597646 406843501 876602249 181406413 732189157 284956998 93926457 20784874 291505357 208358349 765048995 500939105 63949571 264267297 618768768 445512855 589735397 173133562 995022517 43985585 343007016 559891263 326629317 337693842 46993429 951147874 938951223 138432870 483542216 443828875 738684502 832801304 677028231 33651845 681760665 441452191 42537170 67521181 887801683 715626488 251484700 315684234 34793555 607418484 574828797 997945551 27057496 956314846 119435343 768620802 161835308 652770921 759733266 769967927 364589564 774646153 959542035 788909903 913371236 335728751 220784172 147282948 749804671 554499457 325251836 525085810 423999387 138791164 100204910 802089496 432859980 537063982 68308858 992922964 211276696 509865590 704404871 884522327 53511576 337457393 358382814 303248995 802458883 205285758 828188362 301527608 695165668 61851560 200023932 955278044 969461537 704573552 896945157 886793612 597797162 132760137 702969466 27458148 764407808 999271904 770265675 434240110 347375421 948015326 169193032 707494914 381559885 418126033 618846506 673737510 730051221 506786825 819326577 185572282 931279685 753674239 679960075 161587443 96249709 481899219 147737519 579328842 193764893 269558933 566585119 641050435 925264858 838147363 762038297 993345758 484329723 609910306 631674777 340853020 909856896 307251594 621242650 969861207 195183479 479522683 679646957 160240924 943419893 479415861 815386627 717123614 966086884 351930103 416525631 396306373 955066856 734537431 836739946 33432341 767384599 446900571 312531309 41342977 192334729 882119944 753339560 359853663 272726668 410121505 139938627 789678787 436435986 694150593 704701227 295735556 126546424 627212783 980598945 551064935 503792414 921415088 941234099 257046185 557264722 812609269 434377648 996862243 281501801 977539371 809978124 659138275 44171915 824152720 496652037 789268723 773554165 30719331 555925917 749940974 749083693 854174762 104033325 831583072 556909213 357111219 112735561 821407120 409467482 995841088 404615106 509961490 545404717 749416667 416082893 662833341 287654490 85396825 836628345 547867528 463512276 252627014 619027593 452707905 734010716 764045060 471686207 337460260 910617744 798642705 383834641 857607454 605856299 890774447 485132247 976347425 573930379 396155541 363913113 270155499 493849873 903642212 164906075 856204896 959103447 910750499 587691666 647890215 980786484 312990045 499531063 267443251 404891256 591531307 171255517 58914083 345397995 926496008 269135915 408427144 813918291 100196858 488485944 243808789 414241008 5310496 983968027 186499326 259561624 689479619 236838192 794018272 81376428 526246599 931226710 719823828 931347490 60880004 662147219 554506969 576407989 458508748 479881324 595066816 598469840 606466317 769138869 704513305 248975657 614748322 214644974 163632159 749470471 691763075 344987345 989105459 222811644 400720535 88855092 534917441 94712911 696711592 357392185 230066964 890202566 155103048 859403245 982251286 206226064 191174119 245584105 739377010 157260572 670761379 791225793 858394971 784839861 790925928 673659477 280090465 437900398 513162881 238409217 957635740 964795835 246780631 948669739 443454070 87421297 674895676 487385632 331955318 397474834 371498309 491218199 716633070 46638202 341466405 524197738 58305643 103499862 901383974 939771203 391790998 483516841 422403139 437560803 225956294 159301992 999263023 687432868 333647224 167797458 342737358 835426005 295171513 222726282 47506605 840169710 767961254 641882036 481033838 898220075 640443525 198616617 968966568 397520428 847998519 116399864 445132653 215845934 562833705 688794672 22760154 132674686 325468912 499048930 691129742 143868971 746321950 624726096 774539596 962715342 640344266 827122322 396208749 758916524 640272540 861485934 801394983 268671938 763410248 666235 915184573 132382370 743452984 406733392 46354441 361534266 106549372 911012747 676841093 573751266 645360296 261372671 42441974 967295549 685859083 239116205 766505366 551039774 904696950 749655970 105329275 12342176 53938115 181464826 17906035 542553299 557870759 646283970 600318752 115406016 301119814 652961744 940848233 307610895 636475023 457751097 625104554 62289878 298469385 800517496 799373606 951545337 661386049 225155605 205614341 348916205 221009865 447077149 762035008 56849554 828447460 90595468 960941598 629081261 94267350 492302647 143959024 359787461 919476017 68478813 460628831 885905748 294525527 148238005 454500091 494933573 781265942 369630359 891873375 330623829 73035250 713254060 40894510 106666891 765189822 433441374 576407127 919044330 247473089 150295309 754677355 38838681 142862511 661764173 978347176 89953085 526995792 176025553 588317639 159284508 574593796 170569135 263729054 376256295 839726133 773617583 894261829 757804354 878578571 281428005 448217616 307255205 584754837 674561565 440966223 533290753 830421430 612595750 503541937 255138084 40477001 166407786 743345435 478156343 125874460 270444550 182377456 144558567 453891755 623518449 177550086 657545230 224170905 249865560 544978457 720335300 108329593 530658009 480640087 646765745 626661572 775011659 81029313 597350053 588632813 96423141 95670871 363004351 498190248 974682843 119253477 905117840 196382516 674576456 383008803 703849670 467369684 88774713 972271913 149973266 675436027 43257952 410113094 889061615 299838951 57184204 250193946 557949902 714444129 995892466 765081651 708315428 531257040 252899194 343552389 999884967 631675589 427060775 57197651 735454281 914037198 963177524 786740794 476648021 101139821 168636333 791733187 675165735 50658089 542215694 541804192 939773933 744286651 907644479 996560760 604800041 777695300 201347933 897351956 760057158 971014164 556216045 13766696 362580800 396637511 149529940 436712708 887753040 480390270 740202160 573858132 790847289 393462941 229988956 142447709 611532512 928803140 360128551 172984540 993302964 946183216 147903338 165902916 848489333 134505121 473626532 178175150 637833287 946200000 195064156 886662817 34471463 671983099 831856013 120557048 416388738 527021871 838922411 163385596 324822371 464653766 979264863 583811345 833222673 434768461 150948592 55164985 176130428 22394205 956685871 923193874 589575400 377967219 620250794 869169615 3753251 382614297 625134008 322156967 149459549 722749779 274597812 297879344 351462954 196265089 874492023 920912071 632008646 194790273 767661848 247296308 574652758 637297877 983742010 780767820 286138802 224264360 221333607 682274960 83838940 864460452 698359319 733100917 657977298 860375678 418987843 989271280 222596152 210700663 209630163 521259235 221279129 214200796 703801985 260035939 932025349 326722280 281746475 257201084 245328537 994264220 136564855 554749841 802834049 638938784 476136785 282477525 662563725 12601348 199007097 55602756 605713473 978898876 877850867 690212637 758970695 495441173 850108659 610607316 298491867 187981051 410363194 414971064 179145533 701660895 72830511 731013225 701430919 432871828 851494073 583383411 612881743 807128443 881754351 270928275 138822958 788587944 765424250 249102440 819732144 126947554 481294410 501602409 777778805 897311071 653611832 500802923 263249343 8945750 871612383 500501472 404617269 448494220 142582932 793806077 655423887 892080855 270386836 221457582 313861226 432466254 954053428 66683666 641978283 101229168 623786497 24266419 571663211 123696015 277344911 156054865 523625333 955449126 316645953 789186073 831402125 465786195 620882398 923701277 303162118 222958934 641782344 358796470 441015269 21337401 398739007 5766016 590469745 432864919 261927808 948048328 274180332 674578447 297391592 606991952 272278188 835879692 915736363 970924694 491313539 504276371 254114967 554521529 192628771 628077362 136292753 840674294 38626128 774441541 548368046 798459129 682427343 644137144 509450540 864489328 939744363 722669154 524493107 81137981 322392496 422066462 909548373 865897155 41300773 357371360 958676024 524270585 859798947 894403872 980324140 735092447 21938244 943261579 970653895 298629552 258869232 46761672 539464590 285035897 801450851 699508067 281060841 779212137 467846040 66227195 819978096 151770662 25701457 532521415 798768118 775016549 971094605 129921095 174214977 397785694 555367458 185641492 121070952 467059311 432495721 625500225 686307177 594143191 526420736 33550788 757218564 319934756 294432828 414324113 869657585 887383587 257632863 146033790 947549164 671326415 133867238 28851816 25272609 367407778 620490287 786424383 664088038 498719225 818347564 711733586 544231963 144544250 631436202 627366541 953828342 694019778 627388917 994330746 354580391 13978816 428454744 291878833 570262847 775852384 967291426 964990322 439386229 310039583 102504820 857431612 687172978 299006065 716730816 981991151 34030843 930100342 94764324 464173864 449230241 292882789 235641795 450822933 398245446 346375484 80795355 552150183 353287410 282514349 180995390 50735833 204750029 617501192 942147798 885485632 669749176 40829034 342735115 161542301 110654125 620314874 33552595 335258837 557711546 510157651 724181816 224711041 243020822 936854037 804328531 690839219 350722028 648435358 340582780 341443806 102379531 787066519 339946909 474708689 334616512 774092060 125060411 563537697 437554250 756770846 807422469 699665121 996174786 48606758 221407468 94499179 271765815 940679888 627668225 446525335 267645007 16041151 883751030 221105548 172954180 352007304 460576018 578199256 45049494 991343648 330603222 304678196 917050846 292127083 315607937 91730203 883707630 829947321 663329051 811679148 405116719 172547072 843953838 962849148 728130417 720965404 173727300 756650488 172733908 173227370 140359067 209276239 300074139 677589110 57124052 59985621 246749919 40805626 948496052 647014933 444160991 991934116 240493108 186077009 402133086 840375786 312862146 520255042 541848463 323285748 538261246 154235728 591781678 843218377 492737375 171101695 336854268 461899292 914738379 880710502 72622440 631647533 880659290 132889388 755876912 137683421 550851439 535970632 185421277 585628897 438506304 484844510 409261496 865116325 322235795 31216445 278550783 822544358 41834955 273008545 769719425 547902987 156646542 558267179 51829831 376880284 753489979 225305285 991426528 655785353 596684021 799131370 898329440 332351842 301103161 851745447 481831404 471415965 385349788 64914811 592957708 839622926 923457763 656665330 519828688 380533641 419977658 23674860 353952650 212528658 269073288 215326705 20414800 11380099 591926101 49528293 777556751 740512931 310594550 686985372 208364222 281312650 123740496 41771969 649179959 197735637 210962911 479037960 466892471 855179863 978862849 581378045 462655133 715421819 422743025 316113463 571175278 305389720 585166737 525286584 798573927 692699264 649006217 10670747 573169900 57930956 295538862 899229163 297759237 117557683 88392194 551555260 210240243 183657418 758206022 445005991 691767158 458196900 511138421 342028976 744773151 253744567 988201658 849701950 923219984 683797665 565425139 227000458 541529775 165755840 677063900 724257805 509383297 884817199 896285136 598061560 136652065 329815868 808479422 5320248 83079767 508032403 704225636 983631695 105096467 84965392 923583243 555105840 118872978 587936570 182305136 814898724 762264750 831645878 831032010 555314032 542859778 681684190 799000629 946292037 734515216 168888583 586011607 163317885 12242698 544318718 792458852 273652791 636563892 187497725 468441038 738612998 434805414 738020661 811730703 232431317 766474748 354185381 750651923 940945132 57821852 646861009 171264781 542801883 687680512 897962277 586730903 546829569 784623022 288805736 294549042 11078231 13692230 402107580 447604904 374322621 125676271 45152535 920291757 228281591 44475754 742794685 747670974 936821578 756467056 285780090 411276617 372644151 956945063 676008799 636842555 730676253 868179320 235481010 144242281 680127948 281065583 428148335 182209340 544343769 494562109 653896452 644748218 716141403 700877316 54735223 228998511 994883 162652185 205044989 338657159 527456200 917037249 988272166 605481486 358813602 567074071 917980658 17591467 297662135 853504487 752632205 58868180 444941667 118323977 776246373 599229571 888564402 553041366 866659506 795110235 870785893 371488999 979809178 395321300 429988698 759879065 400290771 717987878 4815343 441987423 562963099 459910166 400063328 243005247 185479138 738963618 536048753 491710453 77791017 809432027 529426806 544356291 925669744 621350244 358788620 345124106 463790174 190569995 169946397 492412368 12275435 205536176 228734026 473333653 76935261 42674029 538325028 787092478 193644499 187599933 815268111 11541577 61776610 392547676 752856931 880869833 621089171 561344080 904357208 541780216 507604157 285558296 133825754 171748493 915181726 422118950 362385440 994146738 952577191 532370621 90313028 111802296 226135445 526346177 404264203 355117951 433141719 413429167 396144053 20020751 477997374 453696760 890815064 48275081 385385789 750058644 431660592 590406260 17958799 425645621 599493291 714185207 535538258 639944844 387034018 949713349 202053177 685667382 327590983 280468203 868674599 919639438 197585277 336482969 584975714 98694098 596885298 547357554 970333882 739895868 243244574 553411119 125089900 586593432 71832737 314432288 65413068 841219907 404074546 622665051 531254052 787567811 833525931 137825276 817915192 372083000 327420635 647545543 227443099 797121694 438401072 248184479 819872682 187131066 660794018 570970799 977818204 61103334 846616391 289076713 427555377 888143098 27710773 408344520 268930848 184442155 777193586 792902270 35014480 252953354 467557935 41384939 679566045 234862461 603250755 930928918 602939294 707864543 112958547 529709602 107396345 539594005 203337504 931746922 585434820 393217916 650943502 353004715 98437371 5471346 313566396 549569208 90045779 543912397 293472032 867672718 628870888 112806688 270512903 23197457 385170619 898018631 91044615 13360942 756660818 623160995 52164780 752964117 897205483 427019106 93639960 834211766 182242000 712980862 412191960 728183856 448690489 148917615 965823581 417349618 998238444 57343690 331760473 102504380 250172672 223556085 787099539 549762708 455433816 96287440 146139489 699999970 351837145 339717473 570356875 407080643 978826985 732098916 284638982 509604830 512242815 25393454 26283121 947809971 422725341 325192207 954581643 139033248 547555727 486288070 655485217 41294387 705021592 748602181 780544116 100808184 38526385 792634942 709759171 739730676 392517934 738647402 577207032 571569850 394708046 56270048 358170309 354334306 122167078 732473346 231137596 983828649 692346448 832701453 741537002 428196370 983609366 814848618 44607056 801924653 202922977 643644244 928507387 440237090 928675955 807877937 636068108 261212620 341041404 430280902 392982300 15403371 390644145 815266797 50919719 697200165 433209500 991060811 57753915 346509707 476563420 543197059 447974917 839602143 838648907 189219121 952825809 59002882 352105513 427034181 845574289 218547683 951392177 223814192 182431687 283714511 264320506 184700557 347798926 296533658 394336960 783401671 80436951 26335104 845929090 2956456 390158945 497537830 612100310 927909802 472383450 169904782 833370153 344579944 415422094 280935107 551220613 653435 826451068 420872494 191787745 145229587 666696207 726117656 209617332 827894836 629026150 542550159 115133290 342252626 408199224 980016229 560686900 93168630 336687891 336001164 748184224 70826969 166748207 786497199 892097790 373100273 100971396 209396619 310316783 782918869 808097242 848191739 791163150 459099617 224326809 849562217 748724517 454308340 436353724 409867954 915619304 333260848 901141814 756040427 328831369 263774932 111347075 886543648 591578523 546834575 718072813 698473369 124193894 80283772 529226451 835093499 935231060 524787720 390623160 396815148 343403372 953960870 115544523 832984430 770797197 30797436 753121255 149617515 635728129 844208906 525094477 37701213 64070048 480744924 723648886 934536001 613080465 371166860 422690065 180662421 406885600 7668823 817520941 550664372 356345941 792579939 431589065 44097850 502085140 528730032 365560691 59325942 116154434 335799388 999765802 687241617 972701096 481393440 730220241 280781637 340072205 724391922 854952597 336623171 11140747 862785686 73413434 909143014 397968008 624119233 986507893 224046432 238674352 676158022 331982015 661802582 178578304 840854689 539796473 178402227 636776278 885266946 327010137 913476264 242131060 527725436 625938755 654785208 666647835 34228774 99123676 564702028 813907677 872982118 307727236 512673698 290789137 104745689 444822866 995222131 445246147 92940569 114967738 137528653 521271443 428071369 79288316 745880913 433031628 290050344 529489313 707892716 414145146 815493585 822765110 360457740 567887352 630455287 333111345 912936134 301894562 685462390 580384440 353144130 700977167 742192249 691247641 739361369 316160430 175983201 193834940 664562004 304942530 43725726 906481842 141554613 302080672 143428090 365205672 991378840 135421640 689197984 365747988 935602414 92600612 124880846 605227168 98043576 375991346 892705605 716076571 397925139 618708889 349297827 614058257 409460656 996005174 336629120 521354210 622161100 324936974 354486569 872929021 540208527 919948581 958513614 589846469 131726736 348334599 625611174 912702357 751543233 97494937 77762699 47687729 864171638 253182835 407775295 850264020 493683311 192636190 289485831 310031139 983312802 773196110 933120949 377348942 277183359 414467154 522920677 563682370 51341785 34163664 551458624 473569581 944654098 27648464 624658994 411923480 941425725 78871617 54770617 865058614 742780240 504052289 444243093 284770936 784873080 841512054 915674289 856645605 874419313 304275467 182637515 713496010 784439935 527560746 625329841 713094077 53813769 720197954 617709471 270321078 16413035 590703914 515936521 904212162 231131545 174544604 477914067 884876703 902939112 665781277 501074904 456982726 910150551 162605047 441752393 739060790 56027300 334808259 176897603 951739470 927034964 260477846 304537387 338169515 258563944 452765848 777090767 667919056 546962669 657138893 61672815 898018668 444988625 516377621 491157900 785435417 386785208 790336223 631683954 448311982 50417928 86385788 383220559 727407978 786531756 936892178 957061345 139104005 600655017 755883414 514010286 430480740 163637162 704628404 708949239 863178078 440335035 999041678 752597652 66542330 905086128 977775754 781523153 54381575 727372247 326183811 105566324 776034480 474859830 723956822 280224600 412208622 128336710 703924961 322323266 407292356 58943164 402398918 255343436 540831556 237109549 941746625 267393068 161897063 49659303 913146152 358625788 888026731 267925665 450153230 479046273 436269625 534542656 959714136 352377292 936736209 149558694 814981400 352101309 276328549 200605595 257084840 404974385 218331657 157940067 158315647 964368913 954887807 618776674 496557449 908024783 220074882 140366222 857218385 359240725 771787442 340381458 902957115 357163649 272175122 297094787 136512043 955350957 955001706 453557488 111645156 364411508 389978597 454634085 30343856 105501224 444871185 907038729 78203129 583614287 281577794 178691983 297688952 590395838 941198472 36297130 72680048 587580241 827706141 453657912 277804319 355007273 857828869 393457252 168776565 550117813 575535732 760758166 564206568 217290488 168354443 614690415 317121432 498089225 780591611 8766326 245625567 654713449 519649058 135740209 881841039 92500711 666107831 492250094 399576696 316371804 301933583 564297683 766843385 548503415 549165120 772586525 878219493 539506833 430407997 666204519 698306054 89089956 329075677 65917406 462660590 777250615 333767794 272764264 609045390 936036897 566597112 850954415 845674950 414482217 258821859 78805725 830079807 476191764 143376226 565137039 753402668 81310107 391183943 419218361 883603436 320517268 863498279 374649708 868686638 139580885 528455538 130169265 958810591 355315211 120682916 226932808 498943455 386227129 27182468 588335829 203001863 803116331 512664401 10931491 516132863 272331706 118866344 716517929 788756323 636367457 84947153 420000777 936650913 916572325 892283592 209282626 751228855 152729662 173067384 361809531 424551691 372242549 660306116 805230792 547471028 12099552 662625216 767863078 795158634 856128783 523963381 779392298 539208692 698053425 508454144 586870723 152419391 328110473 524784729 364844240 405956521 437267283 640276928 718126929 728687157 472660588 549014000 431396418 119066811 554931375 672580361 355969585 285767557 792231195 769933352 104288299 362936716 974530496 481315142 118472135 656718142 47773474 73794558 696865604 384823515 612098529 682592894 993862580 426966121 877484628 988583997 758578872 352873873 685070194 486475356 40255693 636673616 611444200 481876425 812143160 665140528 957983701 983906244 249673776 969826006 90861777 534755014 658581727 135925038 554190526 528579680 365107818 347883940 310630742 908351640 372430071 461174223 194096039 69104436 521111904 499686643 187845152 982931499 930622385 881793971 41812085 246073638 240787821 444545774 76006607 831702973 597308637 51972319 776076849 587535609 62805487 431357755 342445523 539242269 3018006 171609951 663718776 401243493 650911846 478951130 558411072 152255298 704911737 896466436 157493846 905456620 290102635 244569185 477146345 479037332 940040119 449061863 695382704 913861849 857663857 218418386 833577078 794925858 634723178 816741549 343889308 180172198 951439197 58380734 632607743 881656321 797593111 866708900 219677284 768326234 594916761 860073008 883571255 129914185 939111805 239805707 876743102 893582024 986557732 660525097 220082995 539306835 295152391 996746455 679756972 542119134 839821060 81555352 372126722 525341298 511873946 349275582 512895849 415576406 124204360 493122219 180272749 121664567 895730310 152700917 900232796 60355941 867921912 483033588 227944585 253656268 946353702 42967326 430817752 608368179 570212111 208424870 933095459 481972019 317651448 769441210 517035323 252731042 763690866 666655598 112725943 533320258 813509968 145697653 183116205 372600302 243006929 531364504 551261521 30131941 339257547 625218628 994902894 532624865 329684141 411887116 1449370 763910852 214957452 902375102 291438779 837413481 75746767 848695666 540663139 289220162 224600442 116437361 228743531 286361206 892437560 245454970 120860612 34452231 937233719 348847408 356064007 217295881 335190071 146409870 471345121 361522634 233815481 15222921 9873637 327753820 443571714 55043147 43031693 276248699 135441470 151314550 94900099 827843770 612422692 696598302 856004633 440043489 792172402 483287468 222485076 987063676 806724307 720591443 914890725 459650945 839003651 965114297 956356435 192362047 211999636 531029379 717370084 746294555 757347487 747107486 407753883 723471904 419312896 765593508 613076446 475440121 732844107 431729963 947732383 745821102 253511278 995081912 154745368 19197316 262434782 384961720 312127041 330494214 681087041 814871738 559927008 397935884 203809376 400203392 732750568 610583045 67582064 780336617 82675995 122661416 685107005 980709378 848499845 222685856 737190114 118052098 727149473 749636646 800012851 174436872 889597469 43564773 768014364 594846498 20010820 249976127 804397181 226879978 659885872 314384894 877886025 477856677 808071328 659658118 122200002 7750536 641731044 143897465 851777493 915540962 189485637 11547616 969886601 100890932 924514695 77579953 116025687 10571739 291463305 617869973 519030904 129873316 526502602 978524814 652697765 448157980 666799210 428408864 540548743 10605792 96135297 670827711 859286678 291811439 703944216 35209498 486500828 376244795 302118104 780022213 536884330 396289801 113231351 648276711 925934089 303360993 281820261 587511107 56023090 30180260 219935667 326967597 41837844 423831120 428951989 616461525 468161677 872227121 340194834 114943783 127658737 154850248 333185718 777257987 481589110 283701595 56707033 920226499 73203944 94327234 479789179 360364873 536576297 789338204 315149618 589759637 150272809 415586997 967913295 438133288 705167185 517279712 449902363 610833524 632165011 862665635 179881184 166095078 423542748 471737098 897893594 400425503 433364858 841907421 686271479 636651863 271602010 649384320 690505902 691738989 353453505 958978139 859624734 960677300 32783307 907640183 49923789 809368722 839911419 127984180 129359134 677271912 743156699 442533391 621605362 71131834 421370598 813812588 966190431 788803267 256395133 489363978 203761594 143903784 425453702 907632412 231896858 175301452 504288560 860148318 303737194 75221245 856890993 630823974 402070687 120036483 800019189 96909521 316474200 520357949 201964814 243540196 806527854 639328109 634596217 181504067 425235859 382995709 6564386 464873895 55843155 831685590 93712750 134166556 715015405 3308018 770165419 275469934 491557296 531492240 852391268 124520875 364859444 313818145 503100880 109335312 372785504 152523951 366357601 512631260 542372663 874635762 111955150 19447708 266794858 104773856 978879049 123627132 474255734 703667569 423126470 45677310 559479250 421028964 728363132 255030693 553308363 729140987 643190524 399552468 120806823 547111604 196615587 743651152 745665743 668689832 388582355 309398567 869734137 413021098 570297463 784556379 677235701 2868952 730855351 250824043 57429859 598710355 905982339 903489760 597458787 694135771 369581035 786837050 893549369 8534625 411135477 428622103 552331524 729202953 816323620 629303066 284047792 116442526 542717052 706410885 939567939 666521570 105133940 237795044 230768983 719331973 551658922 897612065 725226451 487262368 965777003 967427387 546623222 250289561 338756811 479985772 93949462 710639552 962979876 285319729 938481004 494602115 458504693 167783458 522733326 113442057 210758973 966147915 347349882 124200413 942579862 183601049 750302429 47199869 490010755 458426124 132011300 991681148 750645760 795828513 843102632 447786735 128059664 807237409 736389454 22298368 886380426 486896083 661714178 937200689 665057305 993274843 598715381 968389554 114105214 539757032 829990391 673850148 232136011 525021737 480136088 545935022 585615288 509844318 201282866 817488977 505835557 494785416 73715820 103097449 990565817 52151631 351758062 747947648 48636207 874845100 176844513 82231054 691927969 12873121 851116319 646554214 968187899 873010091 389134481 964391274 571215191 452413880 45667367 652541406 706395315 760810497 564233775 593441447 914125211 681994874 114314141 654896347 724196875 890224834 760106838 583203119 735497801 200224635 576569374 117376276 468659832 446815151 567108580 446142043 478188878 684558976 614630553 820577582 832740751 282826248 377658351 101364175 166012070 669029284 286205411 292935651 431959331 893042334 168360041 524397911 203049602 673715785 202565830 694338419 324861325 604868854 156530300 266357858 71426215 463413901 116638784 583591453 371553037 972678912 61453238 166097606 611468886 133406997 820905709 922872299 852528406 286218352 536821149 841246813 215532882 394133959 997927267 488084114 994932348 726919587 199923098 350657915 808623716 274076876 810508230 337416770 501088087 219386877 675456528 285308975 23572889 197937115 574697415 673325624 576325886 596224451 538422506 623176356 552818529 613301129 684746229 934364822 632496384 777244462 806121306 750151886 796661250 808798305 37221339 74151488 745762397 861326102 768161093 85006861 564053252 439398151 215163128 610371365 929474523 156693055 639494565 258914754 35642030 930820615 494566306 60518980 267689680 898336685 261612030 33161908 272687058 29355515 736912822 521989409 350273333 531574026 849008261 234011660 998356245 923945903 543591487 777912148 167561352 906412049 85238421 486720249 484360896 855527485 738387636 655567335 639866301 332598529 545678562 303990125 388285684 640902325 201503130 500183120 423921836 980265446 941415950 219034561 309829480 380770982 259210221 972251931 55125315 157093783 700512472 500400013 253759520 60204377 489571231 136981247 428285641 327208161 122010388 861440419 936519966 196956423 200489125 946393518 186032581 584885420 975362012 785008047 788792177 843364609 472652491 679538015 784098386 709258648 96635652 282117352 84826548 259364784 429050698 881776264 801696588 287559255 211069320 727065359 744788335 305117672 328232038 779092698 910729967 887203654 651722644 967505222 781419783 242669576 323273199 760553713 345496188 632890560 402314780 257422557 204723301 677355417 506454967 474347951 460934345 520375679 880924072 93564640 595050311 476950988 307661937 707856111 492322960 265738353 449537104 212959502 139201784 849942207 31446604 494694434 442235739 109400042 48830546 392246726 549105633 383652198 786654252 298062624 649015795 575553681 863083447 539390866 186140472 921095364 389954567 500436480 492844479 67531254 89310841 781435840 230073981 536365225 399370692 283335380 38277576 687915139 152127248 979658070 97230914 727862253 889309726 331702487 202167081 848951386 263272825 462974622 470300747 596136460 111194628 979322681 845565114 2913727 636026013 553962480 251910449 379120901 777895224 826211706 880813284 864538333 726945346 332627403 227555172 180109829 865803771 879714079 898230918 524152262 613319795 507669212 791509745 976023228 986423584 769230182 753554558 141461434 582928055 194562400 572911022 258040520 913231470 895353315 468629537 374855774 685679148 617484929 636412680 851267468 143796198 773024591 242041259 728326218 412174676 33822619 875437517 741625732 776240192 997897304 27495861 50038058 476336421 218552758 321880918 567128862 964504141 941856113 987837228 494169201 865589573 135687893 455394168 656264402 450499619 510826890 757826266 998410519 595714386 843770891 735509765 828844150 560634074 411462201 325854506 161830659 202536340 193176453 834088662 487015018 220226663 219300411 314902178 630935898 232186037 855693735 507020351 221073803 199044409 273774020 911894342 508704596 707284210 814529577 134872655 660525942 158713138 823985420 865490790 835213726 791543615 607718357 332294405 523281561 292106229 209341835 713474926 78666620 233590370 92916271 785833353 887577580 595195789 674125718 978921474 787024931 424406379 280035927 852363003 889660907 902560486 643396036 993515175 93990333 457112001 999727261 437942440 770235992 561129704 508150065 957686421 483912036 823675958 954132489 426071864 493332307 168353724 195770940 730482611 43415252 908853516 724990874 217512109 873940539 451619249 169239433 254288207 848487125 941638602 832659864 185132027 517878572 937764915 349284319 926060205 945942863 897215841 942935562 843679591 796768847 7823375 223098865 407278161 683450 332622012 697404293 1465994 761311993 458227866 909666423 77160278 198084762 860652054 171932175 946030116 164028306 458153716 706803619 842203291 716694647 871516601 904523281 663310334 219234963 561102568 965822806 830424670 345654126 115469646 538650667 3962930 956912963 341088542 351165555 586462319 753032394 138417368 373691555 313591040 311237366 258977294 410998813 114206606 291299821 795185021 715755188 297017112 618777507 347927963 68342470 804780848 357723263 830056074 31576818 286685553 97151656 374295797 701018731 139904187 653056693 327599557 202822317 466727799 159040164 763775013 115235506 557047346 244964925 808974052 502271148 496387192 725576128 225459847 634722265 857473736 249678838 430103350 11897109 183044828 574310187 298408932 729927076 831631075 706594431 50846400 354061085 154664957 591280961 127545046 901773698 271888449 49672117 911094154 935777980 149713182 82140582 48502617 614014988 826168987 901358040 72527909 450126844 967093669 877218447 609428954 817642026 940756739 506193812 385245451 953505291 140135332 824397794 168452975 132627291 506654796 764687473 299719557 495390308 824956256 325952984 602099804 974114774 370123725 709803781 393682205 592253137 299018043 24421448 83072430 986602621 663771738 561804695 727081273 886683399 481464151 856539326 740353724 846786546 122182042 894923047 157482397 121696495 515970274 96140659 735117223 879151174 210684835 268679110 369352679 140750672 248910226 820886017 639452315 695083780 833803432 368070823 344188186 244389064 327241515 461833225 960380092 843859852 180344718 471905696 47744032 537950978 451098314 488155682 280937387 829781230 675709424 868064464 638202550 751881952 207228788 782685465 524848563 188369173 301139022 686370134 440816858 777612187 568223509 943080806 525798411 818902403 307770836 204971331 932297493 396329720 587063751 901323133 380772324 142218279 764607560 274773272 586184491 300168022 349057954 497522611 196738041 898958314 413346330 658150605 912942310 630454921 336145817 46105348 36782388 875269939 249512548 890731247 836332531 265892533 602949774 907843492 634439470 850185325 102069395 100801871 469462852 720018897 550928920 507883892 294628798 611298542 796853208 818702218 508544661 818731233 570557592 746687372 310857536 146123680 390264279 647426111 723437347 360737763 457580161 103237483 924332266 473702752 226441659 436732825 565342173 47747495 104391859 252091854 722650115 466033014 826610282 517017525 867084037 505551257 676450520 216411661 816821153 631920802 902561500 945079056 127428822 417766122 432718330 216813334 70870971 422012005 797950854 843225554 954090533 812789635 503486672 176199029 171913167 106341524 299312318 207434191 934210993 82127882 8713540 239885774 620204110 901549943 608031463 754806153 794853853 875557514 51593180 280471119 71534528 36523010 380112312 867792232 318554064 402285239 40816360 492325744 970221925 201627799 489428757 187234603 6430034 311069890 362783676 824348632 272327992 35236598 104465442 653998903 14015954 142163076 242048623 536563032 258779764 243326633 24438840 10759702 701367436 222042845 288034556 217796852 724617750 342706565 117482897 809228692 614716844 149432351 766624847 84526892 941449408 651614423 61614616 404570391 101053355 876871608 263847163 37857075 16247468 38746749 312719442 847646291 950624456 145819177 71015314 513587422 397300284 335466688 220228241 83231515 723624886 361107349 382579183 608353378 602411763 567167200 80528917 595916124 272042850 193505461 446444185 879378995 888478080 218371795 753337415 792082290 108726353 56274849 759788895 90177599 499065146 644753199 540657776 125077439 142170789 605646722 180422090 580690172 886641752 36254370 163750418 769098858 767305284 513143532 25240517 836693702 753918094 95299153 773040847 13968021 788434746 713753790 823081010 824609269 190288588 152066332 141357120 127097008 59249858 259482773 640768866 479703954 546435817 152056426 673548364 481066355 291433566 890013051 658937427 11678447 938784124 55207435 282641863 933610132 10858645 471520960 539390036 839664080 687518446 661031025 231993028 233742826 407392451 993103318 43048891 87180256 901426025 795126626 941028949 953829491 608617218 814767988 610793500 81862743 946672027 817917842 896383999 389551967 946802097 848064458 344257964 461552249 829089623 615155398 956792363 796704013 916805751 536659818 701038614 844107841 110219286 598538783 538406912 957914830 188677849 204672640 199681272 745501214 177386609 479504344 863544045 906848162 437437514 390775244 204682850 832167078 913548535 948430785 643550809 232592177 329112287 412049787 288269421 639497165 925468268 989670341 278111579 482347855 887742673 795610533 42927113 625769489 275266418 785718740 973822164 145755333 559613733 981845060 254813361 448788306 258442514 958224609 338761661 227710258 386311352 556984214 100475721 358251683 839207637 288753450 141519594 661035185 706708055 743242964 719654349 471369253 640402779 801203693 672107359 645948052 779982073 470395904 466885181 357893500 444617808 259842044 821472469 484127428 182154103 379547289 272963576 639094275 79552446 970413557 408812732 774812670 669730184 717663110 580207527 846998877 489501329 99967277 699153929 770003619 568051364 188447032 448936732 381269488 44942382 143796886 948416447 977112929 89376001 889110816 764153879 326317773 817155094 501667296 896007588 779533815 821972492 647012801 84862609 215774949 355320397 940311017 561827015 250166290 555262746 78193724 888890923 828486262 877101070 848480307 951231049 998242021 904507594 891867088 384209861 319831819 981498193 623065314 410731869 505042392 68855977 659501510 107991630 363352275 346240011 194601323 980727676 696573875 54761781 364274963 304951244 195089321 613935844 676494886 630191401 711588314 927855070 763097365 26623838 481134699 442875747 762376767 291353080 299397830 9253045 516763319 332733733 230773108 74841390 147127221 598402163 13246118 628626142 233751457 30186198 74071828 483853584 176578463 6904651 808900273 950798632 726581312 96494924 812236474 15121783 862616479 176945598 435083522 323648941 303320291 987817252 272601303 278950543 9169512 908545348 889456274 41966565 40944688 276677449 843878619 858411225 307678891 253755636 128701154 950910299 888678848 761748034 611737570 601148175 678260950 463511518 637298052 859526962 473512521 792980347 79821736 558837786 38079578 127029727 431691315 508246114 790622529 419557982 154484015 789576097 500992967 205751813 95097481 283474815 861433971 340621582 565129988 813269770 829832316 920644888 971421085 247993527 959643862 499734823 129631246 119830004 574991796 959104151 778924897 458063860 463257655 100348876 410402411 622224937 176820496 683498276 747888988 473712299 885823693 856633321 756334722 605707457 749883273 62426489 939909324 525229462 945045035 818908790 708164293 627703585 939226179 718389289 368049402 698989936 13224785 392861231 699079800 283563468 113344261 91971293 594989539 655987505 523901055 387062957 202910512 352832794 515171368 848324304 797914863 362163933 190327017 660896905 953163202 881480178 816025939 68956556 955930062 236810900 453105110 589574485 715732200 826084874 360752313 396508847 220425586 244698735 109081863 121937850 125682726 367185739 549866490 132220789 732313487 155042416 990883129 112332621 879918644 527585033 831469771 251020274 120360920 85289891 732953206 541471420 423843310 434330790 862962385 719827997 603956217 982458863 578869243 906846470 575680928 152908915 671250907 758265999 239687282 529478302 452124605 78862735 996398988 14772004 112933532 822955384 543095556 768647530 235363369 184704522 395327491 656597011 195638361 682954876 761302763 127733805 396897861 545372896 928304365 226448373 373299879 44601513 430859355 948737873 223500991 345345452 79226860 681146413 21916781 729363673 490502391 553047557 930695816 403249691 513969903 661302364 507746754 720816146 528189941 115346682 155557214 976019868 603865042 67231346 483645473 184578257 791358355 752347213 15147029 738935466 197719089 394000057 289649520 994459952 503406576 190084758 395013299 145253227 503949228 726099202 850704750 39639909 833955529 966992042 861014942 442874487 475031865 676893699 551087012 854555154 236361934 173619247 28022931 440469558 740817497 593195333 16641363 450224953 504294090 291469375 211703194 677475272 469847827 166153010 718233669 815031387 455133904 170438302 68773095 46069799 605503580 432792208 837110 319270930 288159378 445562207 824532548 900746535 528568845 447375351 215441801 872197132 458722638 495387851 694693541 450572834 261710212 695862564 10675946 685114682 542213641 716573488 797074436 188300728 678396922 341631398 392747792 387264195 980283091 446357166 222500683 110821171 525705407 759254935 764990764 973847530 540115346 862426635 984564296 341227449 531507395 565096504 111394265 975932312 943460781 157833386 22293820 17817916 515871981 208352159 994920079 365238874 232987402 754783651 835041935 158165806 467854134 64683670 128672967 129616838 460820359 204446394 996396362 407903881 590861829 920858715 787121077 539182560 458237500 34721275 678581810 447997702 609556039 715216913 380289335 645248457 871732103 243913442 527394216 389558339 949605884 171220754 238109628 669880283 249490940 116526689 687748443 629894702 862338208 633421277 767080490 588227877 848068117 884359023 787804541 734158867 381528850 369395041 766009355 551281013 493769833 609490110 338745438 189535539 171709045 954558991 632360504 419911132 986659746 936780438 227697737 550205100 563521511 959102132 719886876 536890190 255965934 829635924 612735648 478940147 243168239 313051996 623838061 311600755 957490371 702258390 784591320 996642397 525736732 421033568 361289858 578675207 303753594 605043138 720705212 196384914 113237368 510305418 563075785 466500227 41718637 784068002 589114575 511504782 857552996 236152074 359179890 187032485 267636599 300646437 600658471 523972275 948739058 466239363 848134554 320117795 806513779 688991473 180013041 226464070 280398173 987008652 450117399 78882256 926903038 278749928 178314048 806881546 950848436 505731103 347453835 771032246 589096238 124090866 856540187 325834205 569294325 617189189 363026211 460715543 513754251 667094377 349804724 10055147 436614484 716736682 88821404 59911804 43509886 765768152 668827822 522535758 813334342 261693661 5689353 360861902 590645072 548644749 201360201 965381241 348149376 141461212 399013037 687752873 381501416 787701659 964567033 602020067 117127488 720042344 911593152 521725710 696079815 53097170 749177386 566871453 878747987 402670325 68717851 950663733 593644510 893681109 869538274 282093229 42384300 909025292 44981770 488501068 343184353 750776723 538367872 92771515 379417555 587108101 654095810 504558638 700104518 234178232 208450721 712015378 416389884 959985156 299627317 244766023 952610730 178902492 784491636 664394034 696375311 186602051 970400817 735123915 10027889 154039818 433711280 190569029 217053061 483567157 364668263 491463475 478434098 770502401 729674928 380801139 81987 692347616 155151670 199163649 889639899 783350317 961891543 809060556 751214988 754899174 335393681 113023061 47540839 202199914 121487908 451357725 708806826 850355098 522161063 262663869 515665288 376478477 454256522 553248023 637868160 432410200 230251707 157779229 172284331 606002554 907309647 626228873 978260535 30920192 911483521 534791109 271625839 350307501 499913199 564629723 406627437 356071249 758896867 757166678 3205549 46666775 386083034 699279961 262457904 554675817 968621350 939931469 861575160 657311995 570091518 27439029 316311363 78665879 697714566 839735326 239314453 684098645 282396083 570825357 273868436 712841087 896799271 41881565 219046401 299592011 942185858 255565988 512427129 721123385 940442244 323550150 999277571 606769742 194563170 972714371 647103555 721201316 350074371 887202112 156739028 919121302 987176822 778915935 920168344 61388565 284455047 250668395 732698600 59828129 719489295 795186582 504205117 653942990 62322297 952562372 612930419 60153841 652326843 980067359 606310106 87560439 349212475 280220631 949730266 957009396 207290273 338420401 285025109 435627367 805785832 804657203 182408996 580570352 611137638 315223245 207467296 544158667 750906542 118942618 442313809 957802452 352139873 220860996 138538820 352174954 76641817 555606891 511622664 744692547 572641995 127382441 390159524 610397409 874346327 411868347 816753542 708634385 122983717 558438995 445983726 71523232 152051247 777883054 858116148 931467534 12865622 785171910 123741190 429463517 292885741 832829877 310573055 368335140 660022209 556379927 93207316 898089019 29440276 366206522 349210017 82401749 61448359 326785640 35013714 253496513 131841579 8397464 233841124 970042655 220324271 122186088 851990381 886429774 729309676 453080856 214886828 568183266 731672025 604770706 747617317 383659748 820870618 172319758 294474904 150777802 817488308 753712343 428092411 977132234 438806019 245175756 927716500 499183192 181691613 649810565 89721322 897376201 182186639 99409183 930149844 993808149 568919346 614291137 576351692 443434601 879518172 847220318 446530898 372158613 982736653 793536524 761782069 833767395 580609494 549040600 795400749 666914277 433779804 730615456 356892385 55799301 296051893 16507244 965478550 548049790 878908395 89043498 790112515 184424302 892696841 721056267 44655416 17329188 819750326 571476183 454606548 884797903 59824646 960820048 159178197 23606540 609860331 692701794 434933377 283196404 699861318 700803446 875796483 584223015 648563445 951525251 569893973 388127753 59515307 369893227 190473983 574619533 233480846 239848002 742112610 903478799 534941623 90861406 408360193 135396690 28894496 150467987 546001516 21294248 297120246 616057769 597781226 440892790 880958576 126310339 843902127 566693571 477222975 959479674 209930122 882973766 834877061 500307780 313670574 763828592 555870550 800301309 115141945 995605947 159107757 405907428 521225841 157061685 995168245 123415112 419975361 49018081 591478653 873982124 23918660 306667982 725741820 967965200 112786823 842222762 804755537 912050638 874251702 654418122 357582090 106767005 208297443 548594987 349342493 928160401 948705214 764076413 979035157 220634905 608299909 936355418 830273534 170054554 433932641 561887419 722129640 305120471 176216105 315919385 525370124 685426859 526455979 742451124 46679032 946437050 546957745 416149981 889011626 261885565 562152262 713506862 939489669 374153258 461411594 541956069 843241680 262071793 646528336 703021836 565489135 357498372 559971802 389584800 647730060 725807193 121828150 347574161 177042040 141368426 416909584 670205028 27648101 833710620 977429448 847764021 641247221 744152235 624212259 28179378 756839486 403780634 919765857 989981848 955267633 663978583 468107512 741029685 312351607 465479865 657479789 173894181 514897674 930518368 227311918 931653980 113297127 369914161 170655325 330255979 891856218 330904559 396685683 835741092 187007186 881370366 218859711 462999337 223676289 534903052 700838786 453253759 89907101 447380971 327927541 211858327 601305331 719027579 42065496 228511807 380515401 262659443 970580573 290135925 522375663 776415347 755926763 516910410 454253073 207141849 383113269 901302272 647521475 723752125 508064285 569043359 429333752 575866434 665617577 525789332 853649641 768586189 42988950 248262056 248505338 56997974 204934986 268361166 923577756 730383278 635156513 219971448 7934475 552804679 396770920 562835553 851474568 87989666 794164409 917189922 797305655 974601941 341766416 775388450 771790792 943361886 254279943 928849914 718910147 323209723 39044631 100682943 754798038 262331273 624467729 251988088 12511382 920281915 80988645 68770554 46356552 397479033 148924881 632473761 286842122 608119267 888142408 810983421 483886533 132782388 580645689 940642451 872169509 594173812 211219554 172145575 566328175 938672877 604906861 609321741 390782801 298338856 722428293 413265901 299281958 532306346 441040957 725081112 404147530 573572761 271636089 742598819 175167812 138948123 442457474 192570768 89679354 229746019 183605622 1186983 17216827 727363945 581375635 161545413 433477230 969778840 527471684 633656814 784354788 675236433 65586159 960771970 573276626 532407194 277938794 916200687 651522605 848483524 630697780 812738533 613016949 783431239 957318490 715119759 577111303 74391978 107503518 212298633 827954034 572606139 795437355 300981357 367808063 448575359 803719343 839055820 536095879 756034847 271784669 644129065 582948024 775321664 536443891 350823052 693264271 8744217 691660845 549791330 623721931 676436285 636045564 440516004 551851752 311421760 703999207 985829126 588021415 567011542 233593464 766142580 455048732 789677868 208971544 965120059 884744689 794654080 926093825 767228092 607088955 3166242 987135943 239563672 56121036 300863942 302631488 212189418 755625817 819568315 959504807 171964854 733862223 548032816 52427137 168880033 786203496 323600066 146609054 337719192 980029724 422059125 704119178 987994549 607640276 999438881 937669089 457408184 477158407 253872085 920875368 958915197 241541708 530008829 690865094 876271419 297565197 955548383 95886605 501188835 125289801 506108613 631408802 707489514 66332440 761386123 292657167 347170901 527761666 413448982 560933307 154415386 614093912 328335851 925089923 178692346 129467998 926393363 916190577 406418923 336362787 294678615 986026685 804266369 150087346 522344433 682195092 446857077 804667305 660835742 956462827 551691691 488451947 118415175 992290786 592823609 555920895 468231005 315838113 520823806 798895156 656282457 569427472 772957156 664054052 93006381 673881091 287501203 608854503 545138957 593183720 35806645 961573169 817350267 978853818 455006225 143487579 827622051 552233044 972616810 712235147 103820039 307751548 519668156 312143903 85750685 601595922 459383325 751087413 281146550 936561428 96982712 159411624 397330338 856159003 623406883 624696710 479649164 463597120 572773039 169936207 601140978 908732775 959252942 665357649 116177159 771662907 453114210 168203531 346369897 787896999 910286860 477066218 399944418 67506622 30214883 621379653 419003764 773419100 624515476 489825904 633529897 738247412 714907025 981090781 744164408 669931816 995899319 687723815 825631581 9711387 46161974 825660206 186276746 203073654 25048281 332797852 980712338 708790762 244166032 378117831 869824043 49830591 913866729 862829923 203739932 727120980 616995855 527246863 585735390 300576206 304583623 962558550 441800542 410302991 999178566 874821720 252746070 341163303 332614672 680390987 211941944 198327907 465516936 927923593 148263253 51440232 74223589 594254999 73129662 814580368 907598618 557348857 255559988 665434868 334298067 473175280 768094209 951200348 268135159 755661521 454439390 897912185 493184144 512885713 902944518 550566597 883984321 306679010 424958694 33400636 432850033 331033015 476665870 704282232 488784610 788032621 956965632 29724745 485961456 253200500 623610958 231764351 296349015 459435124 817789849 197095486 387150122 615957112 943643681 642875667 621497386 46396953 944047342 774459712 704502212 648770137 889707987 647833928 624476243 807924819 53564090 76577037 191872344 65099066 620120833 715694282 104020879 16398631 708414137 862486926 603494379 12102149 582162378 425237331 223308695 602948895 719677552 276757349 237578475 145726821 874552340 769369920 8238949 138027809 742195963 827452321 76617798 281760422 835734544 271094576 42318758 789601273 272854967 303356346 842352710 616000715 740048876 312083774 862480597 612727356 184042822 23161013 759007169 724588701 170946856 666563312 956497634 48702568 8552423 242222837 550570907 364773037 172666826 399805541 537193508 65373578 327982974 947472363 143269806 429695312 93944355 319520085 330125982 628096817 917124025 428061653 583227554 33147866 210306492 636254511 8555422 614646338 30372536 656071792 597949682 476871239 31445739 854736038 82143161 946970506 363307990 640847843 13476552 851196621 364903402 452036003 134220136 711555064 662729485 502776681 457219311 920522831 365030522 815599365 955918006 327374409 105817602 388577753 5656827 99415005 473905795 37107241 275293177 224708701 707806208 56437162 16797677 917739842 887686201 153050557 963491169 415377762 102110562 8443129 849437300 227109231 440202409 53377103 695562943 86790797 51062220 805666641 145781635 524168668 503169686 615547416 453593911 254588766 616420552 752333195 52763764 555409171 143420730 614774907 968211752 150089080 641903678 155265347 196601413 132610785 66202257 225035306 410051585 565613109 661884166 534192423 261633287 907973086 167852920 858726014 435679146 917267974 131749521 297643350 235019145 29606275 695675032 479212515 497919584 677878791 252474670 12078806 8474254 416253856 724150899 958476401 281327273 481195603 274214079 920622223 356674185 172039486 376397390 4165741 445341073 953056815 431707848 162026053 361434449 612646707 626703245 553895697 184104981 772477849 448471000 116460034 462522999 348768674 33855910 365764785 985313284 225213054 276579883 720176121 42536448 591506619 636695687 990370675 575252952 404165196 734059475 372346792 529988093 538524368 602548979 575615995 552098895 810416253 300823227 882288101 617300748 656535331 656327658 307930771 497529633 58594210 656434018 254223846 302435490 358767565 927070241 604737309 127480563 205950176 635357979 401815480 14836232 911630429 198270908 887934399 646200164 139591879 262618181 486111560 975771357 78961299 84548904 710669939 642720859 976844874 814955667 511089324 538773267 369812193 474281610 225635077 127644234 888559103 573086111 686426238 603468950 199638501 849250148 993650000 416621965 631662311 471189029 528082403 172329419 416581099 797195537 693416666 409939557 300390048 437828540 516617917 558802866 15258110 311493483 15483550 627399055 145542012 378547692 787689360 295454387 155266378 901275365 531973680 487847833 333162540 578564836 916836527 272385285 848646130 84736123 660570800 876115013 671440766 489778244 641176415 359219489 534191217 763764948 406296594 364635505 194012672 413948334 454325050 788306967 449545696 810903986 355504172 978241955 976944178 240548643 126344655 659603289 500661841 701657445 536702932 52122188 517121338 882190665 153559358 22909851 137477848 119719062 590000509 956296138 128908833 434626352 894138326 45671534 797018536 171035117 767500884 606588966 102482499 520161089 966536489 594252386 307650990 558695830 884028435 966535554 249422268 332706601 995145339 201086510 230870198 578815418 371892592 227148419 22071406 255150163 55716362 390992749 976148355 438881262 729594423 398350920 302938090 796590838 378760315 132127740 993224899 521623550 264719869 624402109 925701478 715915967 57271847 527017490 586155240 148499025 471276248 148128232 742700015 448739833 755004701 95776631 22119629 238887590 117326371 460869248 190020752 638080111 845212335 160798824 448476974 824562422 553313208 770385854 534087010 831263813 324673571 457512519 45098266 249323029 677091188 564016118 562164303 374509544 224133846 455405552 415168255 584639377 820541855 130510171 152797051 479181510 739325619 242670753 635480560 528766907 985355504 994852788 835273263 564819190 878654036 859911741 565810477 264295616 932841982 460380922 700924190 347268493 537701765 313235428 988948543 525203822 771584334 372824928 829491180 637291778 924798265 287270400 176775940 940259580 243041956 528379935 593338516 406027255 498400724 920376596 860278662 997471194 865702361 419734664 699794288 447519813 35436555 834471709 348987786 973201534 368959426 346006593 130860032 769761003 529522912 126610746 604786240 639474573 746098824 322865854 453271485 486657184 379700518 620956173 886055504 831607884 229804531 431101864 690339112 625172990 579456796 318499539 530445334 504780363 795943667 990011392 888814258 742246984 183450056 758343759 955313753 389117573 867611605 875169522 100673127 324376490 246786988 873274879 811390034 370014097 668147506 731355289 106897809 243757089 24109837 733836839 778801552 500640392 51754106 519946298 534623924 328305811 144305886 820877778 440425704 8148172 639607768 322085620 76899315 146496998 590439796 860619637 732567279 536083307 364662858 436207525 858236904 212529057 394159579 755951202 346340690 23141046 894681058 865536597 604004031 277549317 969724625 90701251 425982163 326124182 908022541 677698503 413122567 912483387 279207990 459137276 200307045 576298532 119539014 188550695 580065026 147356727 279269481 651018129 447560603 521811038 514828077 802376766 413358567 177015142 223104222 169987591 561816391 470363953 607673886 110998846 937875954 22567671 120733541 507055525 417915998 375969752 718964505 954437892 69769919 293502213 663780586 905162782 82752595 665389500 680067349 990242817 589352014 371386484 14800098 585408956 335492692 380210865 669092136 317974410 425760518 736978174 721632397 280987339 50096428 465471072 238603360 724160539 316842302 52816270 497039070 653304934 13229561 858669416 352751920 665496027 464305266 333672548 378068276 887838321 62202287 938776229 883862598 269522501 910706329 150523256 42165262 615998658 637440013 265007891 234929639 199771110 203293456 464102553 808496557 565865482 991573488 985585362 95860174 69562535 61533819 472338400 787889028 821503489 975398480 72182542 921182482 195562204 365406366 684553360 59801403 992136426 919959394 653618350 763356294 209831735 424999766 107717719 667787785 525072735 243847663 439553321 903019297 96384612 553103332 442668247 140379694 298655264 826381268 972283944 540835796 934781371 681320056 67394511 698373784 33434620 677442527 974675234 946157784 816089945 187320680 220285154 762724112 932803928 624482484 633007086 917973946 71143367 117771210 473542528 140709723 797653825 808442106 631663722 560132204 532766943 203874063 98864892 278583378 45440535 861011180 455969450 200161096 919634767 393634599 651358721 120497359 701148700 335471283 940023773 438808211 263409482 30330896 96556975 127365583 473204035 832573285 541677670 58487062 29706314 543901682 648555663 933986928 476204228 437394650 14546057 529810425 54857865 191495681 140337578 353162620 104038276 124012280 988058002 303467437 811211257 81110588 737405618 369231249 126913603 296999902 743726033 84618179 140962525 29037082 473800207 580007741 948297080 431342270 51969816 828376826 51968528 820992807 271968517 745771949 194506143 734259995 519744354 93385381 456936858 926223445 749442431 626166699 422960623 73741898 180522270 849501373 92828560 879428561 150417481 389948407 315664820 58262715 345458349 336063646 133924836 724152385 959167579 932620596 842391366 319948035 169895406 214440880 664896433 982695306 714131896 555167063 608334574 116340331 979738367 154686052 203499908 237706335 61920147 12719332 888733218 99433550 59344225 528714004 586073918 549172112 769096857 589517967 461443401 442085607 437416505 699322856 743222750 383280185 463472197 701582804 808879299 251636495 604241796 920825540 940341279 262851600 771953142 576731674 917686642 75404359 569500987 913421536 329061071 478960650 304718179 386106671 821279195 372002267 493614806 912649345 273376867 870745537 207299553 80553689 395453000 241497087 830771390 799408847 863645661 704943132 108213788 80416390 696222861 891800433 244552079 881218086 450334058 863544460 903680891 445849242 786255155 162721217 967744025 580244508 177818638 501972714 16963015 53185122 546867185 856311851 406383536 870017248 331919465 914643985 527739061 917467785 772875798 172059153 980736322 219548747 500118589 724188569 248422699 844238733 986641219 678214231 958489354 351875883 730039895 234584864 689019637 274368611 218289936 936133 540774368 252825035 930657321 421032828 528422013 778014670 543094607 650329280 714505968 211819539 425939212 168457228 393952847 493535110 903941539 487973358 902840978 193065323 921333471 184835813 900646524 22875260 107274262 621392176 264101924 787760164 869111474 583407832 4249756 642589149 671453181 213670958 328073750 266972552 150981058 486752484 397159309 432481129 818453888 813771230 323712822 448514166 441017246 959955568 240196131 214065830 74037113 77014800 71701251 406393388 592705354 671074680 853387234 933922188 233714863 21768484 98779415 520844992 2600001 864247722 150108736 931222259 906627367 124236997 779275028 911939196 726435346 771114644 639605867 393180422 458043527 480813798 473868114 421628707 855116506 736006183 713269154 751318066 453059260 735546970 152769279 800953168 90921377 246723469 786156313 874957897 471658510 421968196 805132377 977342269 95690430 716746581 759900485 520750683 528579978 491402176 168454476 38791444 705052607 520530569 596024759 228855299 938843035 389116998 318866565 244545263 256186299 29018115 543240504 827662371 272469440 498758297 75866154 348661710 916240948 531845679 785322573 87179902 52305448 541122409 135250953 245115726 208619319 805530149 301079095 390852303 767248805 5412613 828766616 84644956 504436811 615348586 165687527 240334313 753707653 555415653 212227003 432675675 307338202 593707081 146948030 655018279 58021988 952491465 772038269 840293630 361372359 240422489 919808212 829725073 477195853 694497 798562506 328171980 982239606 490902323 346848062 766639334 243948178 572197006 571391236 110200309 448286818 821776987 455655835 4913836 625057790 734666535 503673399 903911139 831563118 607939849 327287480 460317532 967589466 549515761 366842879 328759182 264108256 777929855 678201393 731001501 100403719 747596009 74220387 225273859 506385681 247156402 312595025 630488989 936726593 173781260 906204022 468442655 749587909 287755676 241499340 142290138 198299520 556963097 852233270 333887358 30377100 123113458 269034881 845753807 977315300 377545735 165596234 752011624 461030515 68871976 867376171 876521349 918740019 333132992 972169817 788330246 12812321 992629918 354691614 497344999 57919495 13669505 128941824 985232171 936691731 780914877 603016311 485238863 365957406 230843060 995313717 530588277 596043409 89785166 159851517 393432765 35818397 996473938 105263550 721647839 798298536 274562829 473183102 376916347 274151020 225226931 831572457 344820058 863312619 364509584 609269652 281631884 498094935 810597815 219400999 540862158 620275776 125233627 913866616 652616904 924280536 454210050 877275922 858585427 474028981 34044761 761625113 578290320 927873495 528861867 269525409 224099357 147783707 132310549 29250904 755392672 210130792 198256043 569465413 855352529 731457573 569846529 482439302 781792325 666791890 474185064 177446037 567987296 61574877 581601610 620798619 233554502 334945756 209917224 561565900 27910225 652754199 479697308 276538419 713833905 626228887 985521787 483270859 169699089 666701064 78158077 925008522 151353364 713247262 8766110 528029173 402797541 608909554 213481359 801472143 561165640 531506814 324634330 294458852 587509391 723108629 542178893 491434998 125154557 584806548 732122305 552670775 431151779 709365736 374888936 502787089 39823594 293658572 204095089 297845535 628825113 933045030 181108435 852318865 21467619 581657215 693938912 202286216 852187358 885576387 259502775 3885390 958168459 798620026 455220927 419921640 480512530 938498389 883452766 291462554 984598597 375857203 527412719 883463963 61391504 880489412 584166943 654975915 442471861 63492509 589354252 525880035 573897607 431665745 942941498 109297727 693693896 187141169 2691018 838977176 113853858 181161959 518533009 62631879 358591495 340077166 407731568 367062985 323770854 172430564 605615664 240695357 939645460 579571019 179938583 179008625 540369442 96803695 56952756 155895213 303042376 521159949 300624569 410610356 152337110 412933060 956119095 894583356 31083151 412592567 698345377 601829859 259519621 222629060 631556935 767460323 579031185 503377909 438952967 202262802 99705711 842837783 125505688 735485320 994613342 399359477 188465518 347801635 630556614 910737860 872270575 281702633 940374846 97024782 784711945 524647761 719777171 507875180 44693002 256523343 718791249 197369019 529761010 437446121 11428250 836520455 345658369 912884671 167143031 606780036 209623625 373926681 807762028 502578514 584202787 736262734 598275352 999673288 743551056 737401486 973911936 968615900 43730420 898266140 87136020 926314321 612923931 18034454 716018224 245751435 262849686 332010803 596100431 290709176 542439084 849152588 97969359 338524230 511813386 989186391 74934217 212925265 382252606 776349314 267093073 951930799 126005066 591080768 561492477 452229524 339055944 143913214 441829361 385686146 559150470 152469754 945101203 264776726 502798184 806874424 914472295 664536197 432371089 973198976 463940533 4458138 96228117 786161190 618373126 447059631 28393273 228232284 194319523 62065316 895802746 859941729 84882142 917478837 547116195 492130197 7217983 171279295 396956375 101361553 445633848 623675866 549481596 402389909 236924058 638922348 602003382 162931924 662961526 663038260 989266789 686715377 790612994 399371826 189942668 527411692 342901872 875533649 56093067 423087510 666472444 875054436 241037149 460695314 178024220 183705409 187829969 691605366 841250499 210235571 874200564 558942510 503212132 165442905 384314670 74054566 77797381 626074226 694139997 275061685 621511956 431092190 133991452 960754378 997900101 277827867 686442712 474281227 492716362 265025559 776459026 770690565 647605539 355549657 836336322 831222229 349577776 686147033 612954041 828253437 951081769 904315021 943405948 732826110 60708030 682842843 301225784 204827828 72895259 524666648 224939967 857454514 712387901 571453276 106337941 660932281 47487716 743380922 559420239 352667773 592735913 43102641 275486979 581926081 862482002 95491992 381328322 926860354 815101170 804660017 495108420 959619612 944112044 498947591 290332700 516397260 400696026 388456766 588876681 244735659 396408003 770805752 872008960 692420386 254438542 926541675 142724561 384433320 478231171 829080502 689314533 631997155 887111625 541028612 716869968 547426258 932625592 820563982 647426051 989833825 751599440 23236538 4836645 344785724 194133661 700142304 306231850 967665425 237431887 821349588 359414680 982410907 681610146 13978765 649309699 202271161 908477570 243696439 962637307 367515658 480927062 315179120 253153468 238957445 819738705 373539737 275951847 613548629 579431517 493735579 39283142 715153544 671496545 614689005 924128717 52134269 404783577 648670976 841959719 304785340 998728787 834856334 210612719 235975643 505757635 455330948 250911131 83928145 761274503 329470086 596854781 33942327 470080327 680373984 547973779 119560671 255444748 35092877 820394513 958316520 546965681 59283409 767440094 176320512 8848197 402503209 479180808 387906552 84287897 746754187 846754342 292332763 384393459 418703341 864524041 732410672 749885979 517512564 874920245 345852029 99951239 124976216 943316224 104275328 614865404 596591275 58641659 344295519 753127897 496325228 207621419 503003737 399664883 319891980 174477596 469814375 299480737 449274271 684142634 277522047 606572956 701670778 518902707 158089952 495738151 19027884 659542293 508576886 244929494 547348892 732684621 938898877 132031888 210133192 461601191 923447959 973322881 811253642 391264837 582595909 616865179 961524420 551216228 326097031 868714104 634549001 848449513 867241432 2054944 593469856 72291658 196929573 271741275 937272097 834073783 270085542 430831239 365154108 87470714 868868443 306733886 351941965 319604134 73801584 280799703 736408639 788462305 256896089 672919966 480842433 253420045 415819452 274811151 8898915 965246214 179083933 700553542 777451070 395464511 307459011 895340132 690534647 54196237 470960086 426395789 472138096 225804026 688986967 82679005 226731485 667691072 919527773 313201298 896685845 602312793 464782530 15790309 843469991 709076705 180108507 805213250 320175899 328351953 622509207 569840129 910477693 751925668 633404507 376958436 96771251 383039098 544068748 115510000 712083161 109310505 328662044 957906473 12850630 509931633 554827776 780148610 720453519 766139094 835681830 654023043 975113595 358013054 117668343 152803373 785310778 168680008 197682049 223848752 668960711 890355985 500258204 345818994 767274327 349533712 462945527 797189557 198350322 94032144 356537865 714638790 171076534 927453892 206760509 810835775 730564046 980253777 920854725 924927806 81160406 653094151 662216234 989583699 109603809 431083443 609865437 744060556 679134510 566741631 874267543 393100752 949550073 508897314 681241059 623574704 792823797 800177646 808736182 196137722 887780730 727699163 937226349 389517230 552797093 720610444 565007043 33873791 507094227 180596686 480894738 79779376 732803592 368278622 664229667 265436699 921605567 266246227 145937064 466261886 594214921 201486252 949421789 397872555 687822894 677957881 122748319 983572684 125422688 809057303 59552376 882359266 660716044 550631215 42843499 790853737 694352794 949236608 420314813 808366203 590833169 37287349 39260511 167027269 801847184 668655761 971312526 505709617 502526677 643763074 127891421 842073894 411223239 172199250 949906386 400817021 491450710 671616393 843531256 737681184 203942045 659108279 265455799 814677755 123994527 742725587 270580134 17690969 459360657 818584462 807024889 255263967 258009750 963456931 381172176 437509765 455694808 846953549 913585532 905863415 502955543 420428466 427442328 476273395 201852576 723065819 986750339 656540479 738543511 644028649 467456329 505683037 856839335 348098377 538907032 556903087 343345471 722887546 6873887 45908301 684563710 493810148 537034445 449687059 758916870 142973475 401120099 862898971 116468990 494938664 514517374 82738657 636843067 845362296 191148310 273032470 28028886 181387707 782269034 521843379 142099683 341952837 817698441 907097245 967832270 540988450 629978248 531960914 679232905 958638140 620574840 227293114 942107547 402012159 572469933 223671011 688859655 713480575 536167718 541772823 195539233 377825314 61814307 636593325 932398151 918442863 108018556 643654090 759557348 76332404 734137560 442419209 9487725 619450011 316889115 239727822 330059800 439114978 451450516 824699159 857790181 959582610 273790609 188676570 942346617 673784452 578441118 88454614 413422212 962736944 276423172 760152828 984829107 427773631 374244695 659753437 788938132 249910123 832543152 876221263 448852127 187593267 823108402 179327190 530124427 62816256 936393352 659834459 745095010 442238352 667990700 135943828 295464339 124284241 980855160 81258383 862781705 597167317 576717340 129050918 287503249 705036868 132843332 960457231 437468257 599199810 810550600 671901815 108031433 999395626 717346275 468220016 139696698 111018583 754916850 349262904 524208826 477778173 126276078 675705885 116640008 760024197 258514803 180346426 331172741 295710777 55683987 245343195 764830415 455301713 512445753 751772074 748801068 703542879 341538794 50430535 151375537 974072639 310279231 879433765 470552435 754172867 738557887 191432019 638526403 975489947 748245829 655234135 439636249 141174085 391328055 914013544 111516831 995356424 141727751 128788849 274175685 930580558 589694416 284450905 369644533 142053773 608205564 205549388 99278767 337018761 130748350 81784115 343292799 538036817 826724157 130296111 557685104 799517407 85863797 411044952 908017036 708929297 691047088 790772981 980527828 988075921 110588933 364090015 954191887 760924861 111737691 918186085 673499077 692074985 479757716 439288911 249338998 404628241 253198554 840657504 552073735 501201840 462410032 6005613 869182488 59716388 510811445 111871835 627599889 126471131 649855372 104421194 96520235 202508750 471413530 790816141 773265944 352722661 191656822 203947418 50952391 257431991 376454228 551739571 379319663 853584056 533320026 870139766 81848869 814728155 855413450 243242702 649021360 510838550 114611678 44519644 792850754 282461366 604461559 597034824 899642886 573140040 745824827 497997570 692118178 687101038 844039412 709923926 810048270 634681827 507650929 731844588 313797513 558398834 654424778 159444952 586846192 551230770 145502207 34584987 215409252 213407957 569142804 143646403 197572704 724284961 72761293 204963298 664497874 618675687 320622144 342864060 625602049 615323296 278642645 326039515 980771492 40092455 249893336 747167447 898239581 666080402 744902907 210049430 66069481 161318255 118191904 63494449 662402076 919702792 639974909 605951233 444372658 235353303 930463736 767617089 304854652 639375714 603151547 153236716 494752043 443149345 658346258 718355636 805678116 144321110 502915764 144616949 711573292 92859101 732582139 740275308 574559097 447192089 255091232 653802982 740047258 322364541 339668671 138406649 823365072 505998906 56050232 330976875 84888269 896788869 327053566 168663422 444553056 932744700 777423790 545706277 553728610 275735422 923115006 147399175 992288522 432778224 994934776 438445863 988236181 647718860 486781827 295175530 788831703 454003502 552531859 131722683 565442440 73497098 238150703 544195535 125923577 885203456 452742331 712504037 534487246 967393986 744113951 984676857 181589813 172681993 164023713 136106156 972264491 701431267 228752943 920562167 462227668 768985516 574054173 308115129 575087708 328315124 580768103 127778070 67470232 253596993 769759800 531041200 303807392 520355556 462810377 82297119 982891090 543511365 175350268 922578563 310495952 457076533 713226126 124916775 317289681 232608642 933262305 94228893 356453506 451921599 768907355 946997874 836398522 754956808 596660264 793611729 202825941 159449944 721530937 419509847 759204688 406306155 371503413 102621723 743649366 549980408 198557341 279139170 294968795 24272428 712638739 596037027 563948911 98331961 275410248 729775931 283178750 229023545 534355729 716274151 614422316 385324422 337159188 741444103 385718120 618258192 546221237 828558278 962559627 486441951 97057944 417250085 783844382 519120641 771939619 180072854 301544975 281523856 142670441 603244467 466218566 184718865 599027854 56769528 804387621 418297026 353558682 401576236 427851225 87342401 354057978 992382644 691070191 940985078 77993518 65236146 663910208 601909297 889684663 665323752 924726593 84777774 21696100 889999262 145469446 562110242 550558058 236414839 92773116 335948457 264534308 46910651 226394057 769818982 562086428 945401727 948274709 152134629 226694677 168537362 825939630 55814976 734791982 953043416 362261813 165346084 103813083 139298643 399593751 797172996 63177194 23094386 473017596 918247912 898187980 79215149 906734492 705597654 737634556 68241678 94859035 502970022 976104651 168099054 798326298 240743775 208489710 367273982 532593398 162723378 290100575 319471307 150713016 736862871 955754542 347071158 592084767 572603460 337733204 174715128 428246020 367551712 711414071 106670554 181899136 580379903 826219004 404325118 752866959 770327789 117688410 788096079 642236859 711585811 559411510 165146532 462553533 418146365 19148500 179032165 767464813 490100938 783046391 40652151 371700617 398305522 190479552 762471968 584743587 156160782 347278945 465515457 252057770 704049415 816001942 446509333 472558007 707251647 329602693 408407442 998102329 700247478 501443234 875337912 810708625 111737589 627788690 974087693 56488578 600489587 956883222 519167218 819173227 898354224 534502246 872576765 305269345 386806820 926868093 161365963 381351143 853184292 947646151 596773068 673177458 119349647 110062798 110903170 389290187 17293643 452725424 929202421 274569828 722362227 222666025 992853145 986159144 639429138 32416620 453810119 616880741 696126074 917742384 375609056 982536219 329570270 645194604 678616315 781977594 992672806 476968607 479892658 977017130 823970824 252082228 311850888 431398500 164299579 261970199 550225607 177161734 959856451 165710962 906421893 26625134 405247343 363552507 687973198 497858389 641748374 106868158 322154544 939551054 820665461 408102430 982972474 908496529 78378635 625188580 677747357 233967198 185318997 433821460 495366910 336139353 270231774 629779205 52280349 44777657 358902502 63980104 911147026 178150527 54183373 709708581 271757262 656377009 43994630 929545483 98288902 910404603 78043386 652386695 92226716 318305223 728676497 433105034 795110145 831925612 480753254 946430279 786454297 908892748 754839850 702651080 389369827 219631246 350971128 558189817 197806669 617853817 872743365 265566411 958712453 394842967 828290483 554726140 424407260 363342552 493633586 259244074 35581848 795398471 928712502 315274030 391057984 754268170 512639749 31605403 795216988 384495341 664073643 922627855 181730336 74301544 107592386 150640729 134961953 140548424 669439246 820454459 191999294 415255658 818410853 702387062 985146626 990474499 15336174 44540222 116431238 197697802 926877456 963467945 834241478 564146 718852604 587035839 199770524 395626527 6693139 980085680 302478197 596488467 545309824 750142925 679342820 319156046 84841789 25367975 949782355 250529344 109824069 583710368 975678976 434617872 886250577 208354816 916455698 437906160 897911879 96827969 670124098 937650615 409391610 381742033 536330351 508564971 350627244 881695942 186653707 23283368 448770187 290337196 373998060 903503683 912413708 646024459 463190724 417574182 753690303 143707198 531349219 964091693 34343932 167806047 886535103 67781956 93073339 287510856 68868129 908770136 720643668 220876589 596358876 800696876 506078594 231048226 721805707 38357832 267656380 752173823 886761434 75880554 322367536 98349356 330896488 659465428 630329762 409409002 486392092 109391408 253679397 854527300 430972124 407502627 746687816 248046224 729062880 931865264 149897608 514896218 997735153 731377797 39589271 213060459 194070509 169080793 7807503 163444017 122297263 267950377 121931103 235512774 53635612 826521966 580661206 9176144 860164222 74354763 818837407 923947631 564583012 894475249 748940727 747651438 829083536 406565065 536743986 974306954 881103246 567276258 911938917 319771942 341113205 208577781 328221483 285897183 984526101 725532308 607124818 272211056 381902999 218620151 426100874 907583777 991267665 758196541 409990455 548706170 264439180 870273871 970968554 493213075 427055941 661826337 795307104 252613247 664539044 120011836 706469835 800078048 630790761 632725049 275267451 118125056 267936623 522543914 649297457 652178147 486023117 869795894 186961775 792076931 486894633 178952953 607631574 505085404 467800009 809927287 490788498 208907153 375106441 518347374 135504738 209381441 496444278 193128826 762645183 744620954 561861453 336223455 241369567 187309612 371138233 419166330 581125108 478900725 911506483 40982364 330267887 322242818 832231976 300796265 828578547 94164370 14862484 388232418 707216683 344189194 632767415 779247729 945590268 9587779 147397137 120779939 809853143 800290259 387192153 229873420 501588459 147065169 417181946 567494532 430953359 218770842 324227938 911064678 443608877 661918913 836310399 406443470 828076518 693215609 675956569 503044540 463761515 823783450 582616489 70921759 691088152 43673477 746274591 918751612 793344920 802246594 601445017 454375809 855081426 541930852 850692387 497416592 65491973 42137733 458777830 991667947 493639533 118372659 445032109 244904091 296591028 369386387 802841553 206470378 8919680 521043040 489687469 743072511 256469980 710856885 224844955 599544548 48293652 473838598 658667120 956460513 777670737 57826953 196018799 446734133 453085039 865972492 762556930 850387279 634866566 163799283 731879772 288248434 948821933 900340970 223887811 70075315 668733954 205981297 427800265 993936673 547546990 514385330 662744243 749672173 333317102 164353166 731120613 492351988 489347628 474986017 51359969 318671007 857982093 280557734 884705038 602328929 588734551 857083039 270446086 103815893 718824765 345821297 48314573 714233574 983619273 590368858 217518066 389945801 103209724 42218687 387838183 436234628 768547310 311308291 847952583 129733060 791514071 658682243 665300797 55243310 788120564 958246116 731984533 459253775 788901002 201570543 757102766 833788012 970228496 741151820 642967157 740067442 789202485 471394589 867865209 216095971 483851293 837523805 372015532 835153902 953675323 166506748 345867410 856573229 166305467 953422067 814626174 734415793 877134093 742397221 333457513 540655101 951123351 840740932 658533500 930588174 818758242 787329744 656984372 556191191 861189807 796878835 399308128 703156076 477350185 794873888 704102942 229294070 69006352 656360262 696466748 329464399 954043093 897355686 846324776 567238740 52454848 834616442 80873474 218947272 135208101 904532818 476630363 324434462 643773244 667372354 336093412 477558783 273659638 534383596 851446822 679119688 807636884 480507732 259270244 396442347 982713049 107618380 296059921 919768242 160032043 264819973 148365401 506117401 774470497 716786863 2398655 595416624 185825930 129527234 310390230 76109307 403916426 997575634 178640295 783273667 267853760 435089883 739404026 16213943 859885973 311889312 768825383 728910903 801861779 954403015 466735064 670329540 52486927 382208584 460941181 411260960 986797790 853397967 491760476 548446722 512846902 541450450 31131505 790910598 278198910 262780417 193609622 191830670 527114084 615453529 931641907 508849365 521525885 661558710 73983925 50686163 569979973 979288066 589109619 90002772 741938966 847841527 660961790 921094862 501093496 772381919 639048189 778421110 936888557 395989449 767949367 777211884 836063189 704121976 143789511 449927464 955130833 720018924 710749542 588363154 638383430 28156816 784374252 97212534 891508112 278853243 629264125 204970779 317379559 288494775 691996129 518155269 61553927 864324903 900883877 9611574 374360098 474384791 290753079 237309703 945627866 603128131 567443014 182285004 549782200 155845778 790652566 860818163 289664797 346615247 524613659 491072970 90694662 877517013 250666056 270651640 535559937 960278028 240091649 464180352 625821201 607333597 118242214 967526181 18528816 822922569 98384373 701271406 653067218 48928874 602192674 976830546 208812988 13836206 128762809 226214846 366908977 631503883 454481327 144997809 565092390 476487629 511100994 76723125 384923286 982765712 65816644 211796405 567287743 617508467 209288908 70716390 932191409 20243984 146329370 794961123 453713369 247388658 439145323 202146267 85346569 148797958 541151496 847346080 535923499 520601728 835495669 906183563 859018461 405079570 434434935 783588058 112516247 143671109 358929569 249500678 537984199 557273723 26126963 606294148 482438937 754916739 520313924 728709286 229806164 47061445 422486770 116887595 181096074 509090513 797275995 267128903 516977617 680033756 609331302 629678467 403947693 686770109 973548134 405658158 727618774 353640741 77560062 435515056 161657187 100238736 335448545 407946224 628788734 387360892 749935233 64506671 416202843 667542076 607455528 274196935 154578776 734385959 113325142 387307524 225734697 632357661 764292401 855847471 507553616 469426437 31527750 276845550 886561522 151768636 644276332 478819523 907943085 994058171 558053899 478116001 207783480 484061975 185983895 760108895 884472487 233107569 922558659 749918045 302042546 915169540 563838859 147026972 527165387 867394723 459438295 307359858 670508372 714182070 119630503 47424403 876558602 748172734 848991155 334974521 25744384 238810532 41345730 862228417 811804735 698901453 481552579 50778618 945936127 560411730 581409587 339319208 411779429 159528591 905416497 500757880 912312146 736532351 506661459 97849857 793764850 550011228 545928151 462977838 838163154 379166436 476613731 806834383 357251051 224777153 154727082 221852349 337380031 37647177 571686842 687211081 869862673 673040945 554402347 582035095 333553188 666038932 114395845 692595018 383972076 563682218 469320837 799951913 307852750 265689413 240936534 392558808 268642210 420921157 860661002 553144132 382676140 613944594 683991992 724448765 146944032 25351007 467860203 422297934 556123309 975457712 261417299 288078023 32177832 524627320 266231652 173841198 289392509 379488096 931504238 113097991 924579766 722979326 873781401 71508139 693634245 992351577 527826460 113872209 704442485 713232651 331803264 349568816 752304109 595832333 508723656 31688495 449993887 909116752 826331764 803526997 628898559 737927617 51560414 858218498 347293034 278507966 890552488 354663308 563225839 552771029 747631471 38227003 897756034 605608716 540180007 885318378 555640040 70083621 804271015 886733935 866044323 97241256 93451892 961758970 465471549 586460955 811973051 786996841 982859613 941244722 460433878 225244378 750530501 116910080 167604371 793272053 426426471 223978307 785223644 828150605 226935805 550654584 597857327 212648842 589335640 423049459 126420644 724177707 474616248 421998500 151247282 488375663 782632826 219129804 11970793 760333773 545862716 341476611 130306933 601631319 930908537 565754349 70030904 112710186 173170311 443155503 977198792 65768341 141852895 609505662 407016248 304054178 908151527 604806660 792223740 31409779 133702034 583550903 334300753 602854600 189299317 192014022 893645032 698152974 156551396 410439697 87228179 47053208 88622219 128609631 279952942 590333871 384953081 587282382 198471712 569625123 573256687 797914345 682186215 785433883 560827248 873492557 722068834 505052044 350771363 929099765 612149330 947126733 945097863 904005383 6531793 388230487 290412357 591942690 951538611 880102663 693206650 876370101 80518477 729741377 659084196 478465081 993881039 816119697 472819294 73001011 588546299 605422499 538469630 975484910 895295571 126500408 92200462 408426372 68991868 435690248 957530013 124112272 753557558 315440288 278237672 502860332 372132535 971490000 786234227 979949013 950810092 141258748 560275518 335823460 362679569 462045338 494128253 838199022 175661271 899856207 906778577 979754065 772630105 119091240 584742402 565753865 498078628 629407215 529883329 58201782 301860522 624058867 672541978 117217560 986928378 216926012 591547378 565562697 129936999 592463693 114385229 7261364 201621795 301904704 478527844 477618563 178073216 544351531 782058942 760331065 918654066 345298998 234869085 388208464 506472713 131122633 794676321 276454182 673792816 986409550 950618939 615259686 371864536 565947545 708392560 940787797 710418199 823056285 742480744 665731997 403223608 81695644 726043326 69428670 928792291 993321570 627913374 586120274 36512947 731762858 194840293 487446439 682035894 688250131 646028700 41494141 922674913 697907558 111776055 518047115 737832673 559061435 154450922 165997062 171582118 192063009 770224125 330740267 983162502 877471966 968650012 406168965 320881676 41279886 890355657 586777506 909177699 296258428 51547167 937787871 727949545 761312563 698245153 757996544 599850551 396661325 438551635 570921007 277188639 729414655 365656173 974371915 852371709 790573101 893826070 348372000 28133523 390919851 376513255 256349395 106803943 582453042 687492743 95112209 769800881 418709771 199919512 921619169 854411859 120586775 617229989 44695942 784276288 271287881 448482776 815482210 196614143 467575275 714326439 969875999 674081507 433405847 570479585 105012821 165725347 253563659 97378938 452701532 119194006 798530327 290982764 251330767 73063551 11216095 619102412 276351882 906611986 388543952 550859877 307854514 568344864 225428251 6713570 464899715 235410030 152777897 228645633 94501396 106459963 446981712 736397634 119162079 890771997 446277323 185918237 282609697 416549398 16294614 619994864 315325173 183282609 251869372 668164412 86256272 190941181 178457271 960049358 894287001 536373775 331666431 883161373 298450884 63224091 603463743 714035464 788706274 149380103 602742428 129104957 339924268 115390739 791456148 112455951 315877105 162458710 447806577 170979531 751414356 478162100 538058362 429780103 55461263 750799634 108834247 867871331 777617427 627014322 522075518 985250990 523965509 376373574 435949453 49850838 985359499 16303185 962384955 39439038 812981387 564075408 448054889 610255013 35239636 203798956 565543651 400791753 531742101 348446784 679236727 562756389 695627012 737652655 975746972 671287665 448361709 29529863 236210744 420919767 43105294 815954931 830660855 954330450 573859225 788994627 545999645 912412874 253159015 563550796 763429377 746617109 310285510 400132692 267545368 547301708 42690431 878580092 167339079 675894105 370692664 933260775 982053172 516741051 994809774 349439134 664520540 327295735 509352569 781048018 195887596 170700343 845626583 867082999 563995559 105356695 846782495 870302180 400331003 560373097 391294390 963633724 877594714 807788574 157959844 185309476 310632810 454228924 215692461 671842276 399573387 826375870 824414202 501450981 500140227 922389610 53140773 241126063 262702336 604505800 19804543 275196167 122379288 856790958 788467256 362126715 287510441 759267868 1271549 819420957 370216062 327978461 743370076 575697985 979257446 194687278 488919594 986019445 107717168 597561321 624249732 606764768 789331590 788339445 571476133 176728324 368608673 383319499 614492397 699295657 518979959 139131716 253776690 645980377 231512762 104163883 811221217 365223237 232319926 664012059 748561673 160414897 249979004 746769792 674472480 620706123 635726345 6199075 521569582 873552539 522556825 690512385 328595263 415304525 981611369 520829561 709593465 525483200 765901504 187957627 858696119 379116982 540833094 207383409 697368691 357247466 859172279 158711255 645521808 225333590 430056305 578010289 866183519 411286657 862101585 640545760 948769536 20394908 580656599 222084641 780023287 648236188 39736874 988551714 558482481 662963455 778037936 488042389 658208195 281098424 851464829 662988817 253886782 665047256 797037236 221820078 508353860 982611271 30102429 323783627 892627757 499101884 918272799 411606026 465269212 162802640 340548238 492655578 175872773 16009526 52898260 195009600 960381338 881625786 813294968 568381328 155495856 740501886 673477344 344465773 715988036 86697609 537302114 411014652 753901360 864964905 686165049 144073563 756040219 436278412 100100204 617431799 138515032 978360157 681896017 580303731 786561874 47114527 570418615 872744721 944276445 136323594 263292168 293823956 787009064 613160924 515716023 819604174 493737883 436037282 332321772 707400899 170781980 551239869 74792818 733427698 779685553 975378388 261866747 483543011 443333082 232014179 509341905 466646625 520263443 332436075 83718966 459381203 20841846 98038983 244828003 306389084 175443551 507441869 106317763 136987802 726902403 765606821 266353635 148633210 180292556 898801139 498353777 215353481 303998908 775132974 379366751 821946414 393870470 332651765 888964585 959413184 732631945 843482199 272662620 715001523 204638410 375191670 424196248 847571515 68573329 406064775 742581872 125870316 810365088 553809545 286700946 945989777 104118279 532779061 665851841 276074969 128276512 460532635 664864952 715275581 325348714 287026791 419258007 794246040 894935896 995653102 416516276 300832844 539180534 612358045 916503879 874695320 106841728 932872564 647805662 362010630 217275904 243329920 968824235 745220662 53202679 648654601 223992105 101245063 597005301 841108961 32594860 714645544 694872920 299161924 864315737 86105806 626064279 583390634 1051586 429304166 470826580 728310207 8220760 494212915 784920271 998225523 416976166 387213093 110940509 872064381 267236473 257002937 370901317 451618093 195446147 842780054 462806931 787943687 543567033 688895632 454671220 889732470 358845205 228679359 832666286 11360426 449349053 209327502 87345132 755923627 47993940 336776857 401697201 733111309 951540134 315942570 323622085 934021739 657315389 912635061 226639943 598070777 244965454 979739344 699700005 222013215 643581251 147891870 256927952 710103028 755211865 609828359 229064615 40316487 975905946 854952664 780796464 387570672 697926212 18050470 959876886 289736465 546310063 535748718 589092887 314968261 378113600 552633978 198943024 753009514 877144732 746892923 108882681 820937275 267394256 385615608 570427430 500639816 236872717 38180183 468024985 607240364 651847953 605966456 198364941 486210092 376513578 809523751 294577119 937529503 566835547 495525733 365656686 114339820 72808976 462435381 574170273 587663795 952223392 667132050 238227894 277211734 176506628 733144890 72018476 818526725 833799609 372234092 863977274 68391224 280419804 846754325 380770589 323601087 39375221 742086967 408447273 990358264 73833666 840789790 816140931 891742592 324333328 74627940 657455419 241055620 105142312 576890153 970427015 593904071 720722620 810933431 748136285 99015795 844920185 75133241 236152615 967240578 618063831 362184391 205209797 836226540 315630309 897508123 536399262 913974435 475585114 837974461 17537122 204052427 884274385 107918892 35388232 510324013 488176288 211888940 611260089 767429943 162166467 826895850 610533591 545815541 336002380 979448498 523164358 586641373 796438956 539323485 757547608 438885009 470483477 955240616 372861073 919340934 153799147 111946497 248043703 35982998 267917815 323489477 554358810 428117840 390380934 78169174 991658020 332862546 831513490 971504088 726071295 463837456 773561540 849260758 16328854 328009501 247010829 328273700 684326578 635926590 124701463 166676421 570012513 929005314 972430052 876640829 856470186 620202950 122830683 7670235 158203551 494976288 207720463 633456178 613190967 475023209 6965468 115008260 400277185 501677021 357281740 655250787 10934930 469865983 407741185 313506029 761883893 217118562 525667492 351275643 240346035 136668053 491413462 806117472 398169423 662683513 844020924 320804428 284935581 773966861 391129875 152386832 325820706 428494502 636526994 91138951 530966392 98737900 282779448 928100891 840921495 260074408 678251569 256529317 418033314 539378138 262025793 349154742 54392547 274417809 159467843 381387332 308896598 650298331 981472063 380332021 904705052 980269634 945659921 525909045 494641605 293939549 766993143 619487776 202699541 247714890 628099385 422431341 548277948 82383078 529073149 682388813 310157922 17903914 428541472 169016617 454954029 193085235 282828376 853056414 544115150 364531718 873242881 501229959 443393837 853855480 422022225 3611441 961790038 508632702 165199431 426539413 677011760 899553278 576071205 91658698 61673451 868039450 26750929 537747141 734870198 801834149 420438468 10507967 502533242 928098732 911126192 908169406 728224457 423392 457717624 731248998 15712444 165946479 868643588 49015459 194425230 286183140 822860732 598049120 761064502 728696483 889211148 477107636 589689953 721497311 686301477 993532793 954829535 383078995 278986791 613773408 376638396 262565051 840052057 24514218 523886838 126992987 21001879 405157814 772264242 612826163 458121514 801775874 793230213 392408164 586235780 335334934 653224724 552366172 626518482 260681421 260271778 363374116 733552668 161898931 961794991 919247286 947348905 484857574 864903377 553393686 149354980 298488011 832145933 796995948 853769082 245785537 324351886 219039037 118235886 649633265 564963244 386240278 286022375 432649063 435184768 305776502 536809027 646268172 354645740 392854614 742802204 358271750 169259777 719110753 171685317 781225851 742367877 857484304 939218182 31170286 470121951 568070220 515272457 839488148 495593710 801715483 961228624 971831334 513705253 93094797 20557713 366222529 426059785 262034110 428311428 130600236 117177082 688128110 847239445 725772666 290365880 136291101 352448452 489492413 152002695 37003725 458170957 768092241 993975383 889980856 983433641 369008089 56064499 699367330 341028928 454912871 634690473 112356184 74150588 127007820 52069918 370326569 184888704 948059736 85838717 279521604 706175098 903626909 391269554 571745475 875114989 857076796 636645501 529552511 305155219 510282898 153242012 838999923 640001804 594100324 159352879 802579040 255141373 915361409 160301005 308453423 951652561 802411242 602465546 662533067 574059322 201517978 110937231 118910873 465082012 234414357 136178207 166106603 489114286 180622039 637574337 847278707 823572444 45446821 362121730 964132705 75600108 827813500 827404462 610797713 244794679 828413406 715474011 159957658 200151384 304623175 341649945 329520560 412776048 535040334 122470625 779983788 267959 571857064 465150465 813588191 888041615 794172335 818244714 172730649 402179139 8466842 768648290 914547688 434206376 62314023 531537431 209733155 838548073 495269371 564717845 774793364 255306359 112185573 477459567 660565728 808261768 930884254 663594706 289486295 292399814 36792526 652505108 177740583 669580048 329369179 21693734 391456020 678472989 477922534 49510158 562431800 765078255 474001845 293837967 835417644 851201063 937424765 231776176 746857756 264099111 878613519 251910755 156299337 580944199 33452085 713067843 677222934 81107706 384651910 468196071 755293185 299362494 859192225 623693950 157994392 88405298 973943740 386438408 607623839 652441710 171619603 732407287 989151505 884693303 642966867 641114163 679844780 475009920 62632357 303852155 592227902 966046963 977815534 515915180 763108927 806739963 65196183 469425590 870205981 98111478 210925716 619523165 496213755 293947497 567266546 923965853 432735268 249085753 942498432 218620753 201901131 740234251 984277362 279005388 411226199 15600201 175353863 709765970 319493274 674574847 121617543 757294229 225966615 817184032 899329643 801452447 182288769 333078691 402521859 453118976 805681121 488534611 571457536 803209238 557899059 603429612 696650853 312345557 553158012 415714074 718298994 22678282 277274431 103144820 785399607 306457405 275909234 214110163 808157561 819435950 599018058 931769790 438292390 465772954 610395415 951231781 592495168 149688591 512107659 202504615 716648344 951062275 776616247 746722836 819658263 603977640 618517008 995867117 46890896 31494355 523380013 595674144 870641519 415585850 254594635 734619822 903872846 609007113 198011484 695343665 17303810 594144375 166044695 852338948 786316331 387651271 103705822 714204167 580167399 18119049 680545397 78679546 250687285 830341680 960341169 151038111 599525065 505575585 509680806 65074152 265297394 429376548 879446187 675408462 790469699 374881348 845643364 296041599 891390197 424723702 946358584 733395429 315424743 768721272 301360945 610413946 355391221 464302781 197753139 398424162 952819312 473492606 109759302 644476265 946436613 887796524 151866570 452354538 499283366 553579976 369444456 651292713 397949427 640774148 127832378 910605854 891730761 312168434 915544232 777989208 553125877 319915830 518532746 981593925 646776407 616641314 583443246 512572161 795628364 80196325 237443004 305233745 726373061 89979740 720978673 272005416 92826245 789746784 958258759 714706722 597645547 958778369 809050752 705204635 298786161 854321320 188391796 951073901 522207152 178539112 852382005 847221500 453006280 566761179 113817385 505960009 394701364 516470392 884553252 405087848 589254251 49258973 302031456 271184673 619166487 391391516 396731615 278105779 112523904 744498172 315274985 197167467 563881229 682142715 365097220 893127480 715111426 505218428 280189868 206942457 897410175 984956330 277249707 374192659 276166216 852054489 567197511 571416822 403295380 29751402 997998271 832579782 58163118 249723458 380700835 297409391 668389022 228387544 211281020 9091308 454089687 455582258 939891022 296081656 116934426 434311546 610850731 802117754 498169168 579532519 410574607 882422140 886975903 640665850 82086020 775832133 740082251 199099351 161082290 439945862 63153678 430636347 353224706 546847890 215113887 435276724 806528393 435973540 181811046 128418826 266102354 893098573 208050350 222974086 400056604 947452741 97537253 725610951 138683286 277704493 486408352 433660413 131497566 798197201 409431082 141345517 628523041 326376536 76330229 501241808 529035589 13742177 591190455 239961471 966002368 15470005 471660689 717994777 91422539 962154357 966976463 765211761 441280017 22943922 888610507 163794597 972633690 57977285 153320176 958264376 906237611 2243430 909440198 70221031 558854058 388821128 223243770 937786978 117053866 928410532 633238699 913492290 269885416 440440238 848922842 340159216 789124846 663627784 493552959 596174864 806971343 846524620 638467234 419154379 340976944 720121850 556694909 170021959 464308542 967096189 880351490 79860802 416927646 238512854 86779186 387134179 18360712 160264871 104905612 110080748 35175289 953968592 625108729 432634727 501053779 801489898 668414353 62001893 280033403 295110325 545176057 557023181 760018418 867566310 30716700 944890475 778271834 817588549 463287855 411100237 613340639 80720472 281802894 491040657 849872084 338641994 670578239 729381469 986160463 747880335 266731525 699483475 424969876 430296024 992568583 219422710 98963593 492292328 781453819 198379713 871721787 914285453 68179602 394348027 237904485 405775271 509928845 701435981 241137559 81157153 177130211 346632550 325194909 66271793 176951269 611822432 696132633 483052146 514901244 723364953 887064270 673119043 14433168 781469072 146724761 972775194 451415561 386062770 381882440 431084787 66763588 824033743 60868926 207671224 597205565 858274608 516276605 791577437 949772781 998812718 907096665 759743597 389280869 25846903 143264831 440284302 245575678 876430145 220880885 111101401 904945620 193061115 283999462 899154180 201281510 317653209 469437600 648665843 85959958 28097975 967769060 475891019 336575343 451485478 579121727 393412208 629280736 654245651 854583209 44000087 849017068 706144058 104545050 951328445 584624420 451141612 595399646 113394262 482631492 449518 232930235 231764821 716175818 187309712 510346507 491599823 300852025 280102880 652224737 282830680 286971936 615789996 231124012 292314803 947779788 307862313 485882497 504334713 207311486 231107993 423737974 380261718 376649975 536615032 682491067 936519131 146054638 642248571 489413022 111687146 860086974 422535319 192270734 282540112 731139014 7314313 66309924 596807857 331368992 936599966 249197508 22305259 432618607 412794452 796894686 669356426 961753414 485720792 546965903 108812321 384065552 987487374 817892336 285773470 282139635 38128425 411762889 369297354 399233113 520287490 245646065 610487913 754092406 114926606 564880855 665669319 499428164 418003460 67634318 310864532 531446308 453538831 884252206 899724817 812898289 512910960 960511489 792616910 308628309 814009820 825496525 819362640 750684984 244398910 106083551 945445335 926590103 537173654 327242615 269941671 343521770 18504672 754905573 291315032 233565725 892311997 294203830 169925668 419195135 965392188 793887888 197015116 681436166 601044537 652848963 656046976 10503980 705638361 923640032 702717615 476937199 415207757 612782770 608102145 595911402 792713116 86305963 655230388 649642444 682602979 32171046 294058555 797875437 25991975 609441537 131510318 155579889 617994554 211392820 607969183 472677989 898082207 689395408 25146552 382617073 240744133 528233683 783469775 659804232 973797018 430900955 647239707 221693908 866146604 637105590 720753617 52490115 335044946 982075463 722709563 491247714 624802952 127974915 563831355 786451808 175501725 790353877 604597455 375664852 116655832 82306049 726031025 284892030 79212740 147727468 662914645 816112943 933530690 302344668 255878336 845902153 340888525 189694427 649587143 397093104 169869253 165575492 480901644 316511688 384523655 968645958 810113268 195078146 28749189 39532051 992484751 334103315 782962519 880374412 455947621 805928889 818542761 359746357 584019443 904829439 870694660 111002526 934979570 427943371 768877399 586172281 23325685 426045865 183742520 668593605 865580885 424605282 216075695 17381 410922643 258863282 355829583 565268905 175545796 565907064 69557080 324794173 69861354 248539904 902756435 115215076 184141117 82001495 625656176 151269516 902774530 320791240 663052483 181474984 910234281 439099375 682289045 368556733 650203375 244163612 66815350 166768445 548423095 112163890 633227410 151018204 755237270 114751957 657345795 64507178 191221383 426896133 302481859 431077856 771714450 127370033 64092005 960291384 291892847 49867244 906789978 860980390 784813811 734618938 994057917 143005160 69971513 663887320 680717323 21202482 625649993 489088676 436945728 469324467 557655519 264863441 885052089 879484139 744746719 583505089 262137633 371826066 442085493 87870253 842541631 189211226 179379616 306619996 782470774 848907818 490190601 215673470 800838495 613982176 163172505 509913975 116289477 901664268 728857426 623903440 311924897 566711885 102855708 798651096 526627592 193498319 558974665 854547321 117541714 822251031 556752392 472421315 877936450 817015976 133155901 749484689 188845095 311672104 375554848 429752934 236395531 30674917 797307952 384928295 617697901 31466220 232288139 981222142 995561593 694041563 995272854 255934382 115893820 15832924 813369560 129553506 44562606 821930406 67691375 142156820 292723323 550370641 700048218 874403038 997158763 316707299 436987344 459849033 564985046 734370522 953077214 916696959 557526699 913593460 420921827 328991949 178839627 19102750 785494256 636652438 629189282 507340514 957887555 790629153 384953728 179303516 456003318 580008182 797478352 177471200 630350474 759274243 565926941 39592058 495349126 185509904 95298143 674142199 620009508 325312557 223308867 603587531 790950112 634901257 55827765 884514961 704309660 986252796 811897937 228967864 724640264 564023147 736388930 840354491 313768127 842960086 291814806 838742696 3008654 761954337 472956866 788687209 222822353 959985839 847365717 307383185 487888363 203856066 136682149 179259883 533046384 282564278 992234616 23168401 291426304 192698197 546536133 891211330 856554368 124415500 23476669 327425452 646428514 494205761 385022876 307635248 347578082 475418687 488925514 282174734 780049516 333834183 307376759 65045257 740854121 402802885 921702606 676037984 38740940 36720266 408471134 577138226 354642258 198974907 151808992 69418005 478507463 868512261 404777042 866282585 830218891 610199675 866987769 917474869 545415934 459723344 824603309 175378684 841140446 62483510 388418137 217219083 989062924 819238536 914865692 666621606 877200791 471498817 991434974 174395401 414497083 951051318 225383046 82347598 589000652 197817045 944660539 394787735 778386278 899567416 21596729 723946648 940204617 233301677 242207075 755826012 912453605 612552940 813866412 306232963 15371780 54193973 954848305 698032802 212260964 218418116 867649358 117759812 377325449 167473698 109624105 133179954 816607670 445580000 302368399 375349074 375971233 772119747 68545606 109477228 312230947 79765872 706663772 360369024 32190058 962580638 299927319 514476519 662326754 15566018 942125338 437031447 633678153 960822669 529402763 236565186 404721732 517997656 299010866 517419490 487817921 615566835 22450251 729323774 507872143 632045973 454680329 916470289 461032181 54906897 233877070 215041349 975797730 126227542 107036196 474786590 621998092 446644807 188393793 444666724 754057878 170921478 99447476 257346055 939234428 447779362 963278543 955493304 583366800 790836286 55378778 959000805 806684249 633045795 911325209 866936834 215034905 16545530 440731302 52295447 446063946 305851154 29069664 47518335 252724244 599641078 778532653 680732236 888820192 823609285 527383116 363998375 671215277 972276571 351579125 521315225 679644987 85432315 847301417 7956528 381078590 37974970 663227973 319428469 824041397 821150450 885046676 362370424 324247425 604438336 136971444 261118579 399169879 605993515 137429055 19968271 354709914 580186405 115698863 953907709 948780493 249187367 831715043 947138638 719292310 809150288 824391329 38604150 90798538 163009194 51167324 348383241 583765254 661296276 697399737 904969342 744450155 309296430 514085092 682132681 952334456 663499649 928787234 697355535 718658242 657560090 976504085 683492395 195128155 992844864 337898942 116659205 220959396 457604908 791949436 192429996 663063006 786596580 952055504 380822053 811085445 811669345 621279082 640574440 943082452 489995700 974447306 603806327 631508627 827520478 834840499 658221905 925120928 888040201 917962967 514377739 254513761 934871007 76197892 137538235 861891742 237649392 341449771 322664673 157146976 547844498 799483585 749408735 456848823 898993515 421605586 950766085 177963771 311436690 61383393 433941120 717249802 216426974 883689912 979187434 773995786 626801492 985063296 580674120 918123946 356343375 907717180 552430475 314982756 405873527 787545939 307602555 438700823 560667022 205769540 241787389 110208044 138697562 134521558 357458252 476915159 737613998 352139459 831441722 133290552 172774628 373913844 993304229 258682728 639257028 880180346 753781429 687410257 472319059 42206141 852780081 766661439 26115256 882309331 813830807 834168629 793494347 582091882 295871752 30576827 564496195 156407099 360690934 594105408 887997826 266081585 726899240 228012861 143906122 621489941 574755154 695102270 567954706 460380771 4950318 181106374 366322004 778944544 948950832 982455332 725448137 22786196 660054792 758456743 982685947 752542317 196106631 858108179 818133093 92898938 474400907 115831916 888632337 75845232 24638067 147610206 53535673 951920702 553161810 599048405 387245607 852044428 321775727 102480016 195947877 231236872 867755342 583245966 421723710 939017660 650110654 21255198 438151510 43660884 975403627 496867369 758793601 715164721 797566239 822810486 864425314 828194330 697382394 556735526 599309155 51809858 397014485 662847781 993192923 404796887 411839863 293305220 136005535 871161118 310876815 655898018 916936014 264871484 716578097 548174060 765064891 940244069 970786963 928443078 209432957 924837350 297517622 525271344 684371254 708512357 336371382 699242004 228390708 28308324 795504276 777172552 792032124 219855059 63557277 747118136 523165933 199463519 966696590 286805124 948923190 351214517 255699514 387732091 584620037 986450384 856438732 34315988 206574011 214644898 633903303 76845927 957257415 198384043 388577303