10000 7238
974024038 652701192 573938689 759841162 6192733 986374165 501742387 459138134 753783592 392029696 301813948 472730468 628371372 576321648 931303185 866410899 848585648 476692437 854673031 531261939 391028228 847635287 68202509 425352108 992866897 66942593 914535641 574847280 52362894 495852752 82296240 556972352 56976167 802853044 631340981 350917567 42592519 440613470 130889123 24035998 509927705 424673864 988065657 193804317 2078934 116904293 729142486 819530639 343954171 618346672 449871799 580442963 255333816 629788113 303707312 58714798 651613485 217806613 418133590 734049503 832720687 562661370 808942643 258606738 324772295 692741643 633763481 229061549 312701471 227821492 733994689 337234790 44229625 772963946 662090271 913529956 325279226 347559110 229517141 108582299 153699114 434463219 624916165 197490313 638829595 718933223 339239314 123474829 391210081 231255805 635457880 497744126 26199938 146758949 112008384 879347562 478932541 303451827 469804872 253930407 387862858 989118865 386276989 93316667 219714513 4221808 468403632 258778597 752520627 242673755 433610686 404831825 592731758 251542542 509617368 49406278 267156100 248009292 242907637 192756760 498268488 514131323 803499517 170623609 174593175 334518789 645186928 544828149 613044514 613900387 814616344 72934992 623204537 256482466 722726123 281765268 791299119 74858550 477136569 787000152 407109306 398850373 152989758 827006746 270343335 307331557 866762410 240685180 490248198 993313530 5177295 822449565 522978283 980153479 426237706 509494038 692999514 746022678 114671779 30389703 240616376 681131071 792882973 292779968 895281403 806126397 670386288 616233506 253517665 948806430 925301301 316575428 253726311 133280766 641105920 28310318 396259983 236419488 563541575 883834534 771762492 889173777 176173293 610079630 607493231 79201961 509512825 103154395 772187348 284213144 886312129 149074420 386731311 590031551 652005089 541239186 543223678 152321815 986664839 155910148 319155969 550847142 559073970 582702710 942501348 673842490 912633617 229182122 143835569 482510910 949944584 83927324 740508041 328573021 530115840 794644119 868235975 194768455 161107014 78490349 834697251 333171461 366633838 570573206 58938649 94071494 572986520 38096507 185834443 706305884 750194116 250441735 754952495 231952896 104975852 370317985 979815989 384908696 645841006 429456197 290070587 254452459 78938532 228781415 850964756 111608374 459948023 227931559 861792239 260128054 620953420 572367260 168866773 22718234 626066601 28308200 618600743 336613449 472884638 258251370 448147499 504930392 233103173 639822091 588505930 33315910 830813682 102123052 607427442 701327327 739100856 650491384 870667665 296781022 187632717 939802384 376803743 253384228 899213664 87308047 407308979 686031915 654958210 542428379 601284804 502956647 38622620 70600200 231176405 417519734 253698270 168166060 266878163 474772667 134630607 894878081 960058311 582191391 400334802 153444211 967715103 770946711 835951145 538940247 71032913 431336492 798283043 373232823 59205296 49567789 647303946 318554687 973135788 449103457 254989667 316607304 349642652 582697585 509815970 502146556 479237857 119872317 923548583 157254904 768438541 864060727 445733014 998331354 51285119 295623802 746566604 309440798 91634615 725323592 437200520 852413161 519548178 99243483 549814693 82939216 826158251 988106226 671942640 646823521 19847590 776566417 636300476 677776427 412145307 724102858 915209839 264862371 543114421 427365970 790931504 878638980 750970138 204852230 358476396 603711705 328219649 419643720 589899956 924190293 414998751 565713323 818240555 199476199 574420623 14550141 753227741 38023733 103845205 859380834 666424397 791656505 776111934 90319502 970292747 559985098 357441966 70334408 171621308 912230172 143299438 199134331 431508694 435427199 882384452 476394234 714771624 455751272 493249333 498342177 714014232 562641010 557210982 647935873 101265397 379628473 747041879 506963918 661521819 385626834 816051476 925013588 925552226 859034631 835428358 630421801 25958436 201385893 849856683 283354376 620917077 529942603 215078215 114043415 303323231 800004437 37918685 229284068 269886796 94155735 558911945 580181042 629231991 923477229 728671846 286053153 500068639 363165477 256440856 574735310 585486122 28131933 895822359 548037328 462763403 662675039 149468055 258216265 507767098 212637521 356416767 878753058 954485479 973751447 230016241 366939371 518590776 642829788 978898020 670901528 987345199 685133259 647671440 172855210 354684091 273676286 238030877 668559223 199905637 235765692 204154986 542708444 203707634 242597048 799617403 643064949 837870788 3243464 846315157 580299709 97487218 193147055 799856030 633327130 204437890 837065766 372466415 474127256 296164456 37323353 30675482 950821912 748469853 724902642 323992091 559296155 957573250 24895635 476357731 762200565 660999209 288047931 488132763 7500074 30165677 891763179 176117055 294256031 958697150 742447859 522171289 553203706 561937697 185487984 323883686 232831242 659085999 422917406 689977146 444058824 853846219 277004824 876790470 761660429 365708785 133787383 201278 453451359 162999977 397760485 899919805 568903139 718000123 910931786 367234935 120180607 76301463 217262744 294677083 361007599 390927401 664732841 603632812 148722280 685453647 25888925 646471405 527130765 483184781 411061461 677457585 317741283 320742705 544656390 871744868 929534285 449585765 214611196 277566826 276864640 896332259 807449269 412057793 124601175 303572437 985387627 741393203 723546044 386841265 306037911 183482954 165118551 460794011 567092943 973467489 454652621 235381431 633717199 826919563 382231664 309709717 648170086 179284099 43712760 163506222 10948694 140430235 311448131 192716531 865712905 601315361 440378804 721232116 553181295 789734131 622728095 964817079 182111192 180817260 205991885 729014985 873758492 913566667 815106130 269864996 228804405 23827393 509879540 138206475 164643408 841309920 413828812 309147376 895444833 713851440 843821272 516909403 843104659 293118240 914307813 118277802 547026255 363525029 736914261 511441011 472253663 917145370 432120133 537616646 602645336 231599401 725617832 66322576 492123790 904729985 214667196 763892056 211887366 286515852 511218852 155704632 252134998 798115694 842340862 33342796 734397783 653260561 410273316 326189097 846975199 158974266 830054738 78347955 757707570 226299766 684713599 319366692 51606746 911056626 841693659 465772409 991438287 505497819 338869616 155564814 322604431 936893683 783234221 350006372 125143268 378153636 768630282 64656884 11692896 15675661 880619200 688659423 505385680 830852993 705423458 366264109 836040303 492295792 983104442 851515897 192757305 277227515 707009256 106597175 760434106 234981661 458995973 71958154 491918042 884436224 960773309 755944567 563480156 896641297 525266463 418536642 531805343 467918167 942285102 551380634 348888953 662222695 870041759 132248007 505801810 855176315 796839864 844255283 556560683 174315234 27642457 515914997 982909334 649520678 906144702 41786314 860704407 770466377 524193571 156422970 586870744 920450850 291949823 797197444 732251730 630620226 764641762 496543627 511593061 462582219 821687558 338738621 478332693 789751463 525329576 239882081 573824566 509077622 394986530 910272169 486184323 664093640 972044952 767778360 119745811 330156473 454660818 93525233 839082791 191025458 187935483 725094476 308630119 813947752 329692690 856077791 183423451 836977723 271241568 384057770 460627332 89678329 128911111 266924355 618031402 494543151 917073517 571597171 31617901 8718769 657695264 781666054 634421777 648782020 189596842 499759236 530569539 654612539 209697036 999456939 985600690 586030541 231607085 56452589 771735560 733848130 600588869 291238115 285496312 785229376 539417686 471732778 956287098 963693665 746417727 764211918 595958555 975407576 304569456 971868555 132945312 95814996 359531212 152052953 102311434 151407206 57304574 617744832 321931148 519209037 559549979 198946533 617540917 129895378 434371401 673391402 404456497 683201038 876039648 669886692 675406251 735179163 452061016 92968764 183201385 463670853 506283434 53819333 577800549 232100073 680238729 422141234 389854373 884033257 198762442 365809604 489305983 67037357 243012871 109170548 191225024 717637004 700212765 538361689 636246317 339051280 222534790 331609190 611742987 117136610 16139814 94987044 909071767 207881248 345398567 893688312 33226755 194709697 821725677 835407875 775581348 213707952 562511737 46117938 794472210 157026572 662658074 460728632 527647433 437099086 393579328 839107345 644881109 105626188 81114632 277083166 937111885 658030098 816204351 138317649 744459719 31818854 926604400 13031268 332729437 312251447 615505142 800812176 87764701 913501912 735008480 507017025 274993469 723574177 810640855 620949813 580301418 31356993 695564373 396030182 528924869 686250648 719454036 413173003 674094106 250252595 722664614 7324220 824082902 560390120 289892955 833153972 935042207 109733599 122589931 347638634 564284854 729095727 975584831 181791482 14988545 125314954 771120223 860762802 623035825 637590972 122548303 301714377 823579694 898164564 950193353 317975451 894905173 149970355 101736711 122945269 848797330 432541554 327368758 791166459 736606321 859803702 674801428 530897027 133045750 573661265 176894899 685512013 65180592 912728125 742527052 858414652 245130984 281483747 314528791 775008816 794153615 964211297 331229802 781592558 657554364 8061087 307975438 933915820 770540381 836619322 841627386 969081550 390430736 99501515 953486737 208543531 618145483 657834400 483221234 890970374 128208310 59606076 397249385 247480084 480042730 708318397 521533946 103893520 563015115 230870414 547471040 349835435 589780816 618163801 621380909 898170033 954283311 588399184 13507003 174334927 807313793 459538201 414091178 880165724 142089046 940886437 993961737 293860354 873699115 228082168 514323000 11773370 719626288 303253064 353706134 174299099 908163119 474523233 916548337 351176346 725641722 68032221 866405835 50611788 807546314 318250434 502558048 575741129 732219723 373396334 330661620 531716016 96516013 995688962 234791390 803598322 943734903 939192607 426139385 495938463 994695250 774233446 716846139 439785437 853769871 547192583 693647240 874952934 864299701 713394338 687360703 971702577 839687138 456735393 204562024 726404923 608367081 783674382 166723077 405894881 387794942 433468280 342601298 622962416 472728300 343372803 982092249 867252449 392551753 664153422 505249064 390664666 409247872 739877251 852132644 334850830 627316854 529997400 817723859 1000199 454949696 647519220 651221607 678622460 532633524 685897139 990706286 186552271 795157200 921249813 87796141 617429961 659024261 100871261 642349530 343397720 323975467 727146065 863541255 654471287 461631715 799928427 580319445 128104500 767489472 826585168 281119797 842015283 369511455 990574354 40784203 208747505 670679244 969932905 572713829 499612821 3574566 864046530 58275394 116506789 847245579 493396088 822575357 364529524 29167317 873226607 277106712 199230547 467617550 164665083 968984443 141972350 639147009 290423865 780523615 861978262 237832126 919186454 445359406 434153302 986388576 281804438 141057201 251407054 995998143 943687534 951926870 205266092 912117990 162012735 146216608 539845962 568873159 902268527 328882099 83014777 14262393 219162055 506272885 284886848 797216472 976347962 740435668 769874712 755711620 711638743 954062526 884002670 191591467 89778906 121237275 804392507 824301561 272679729 974127721 852896173 529295255 620242153 848054623 960092972 405542139 758865513 848922235 115082138 948868619 17634417 381167734 730128206 232976222 165322127 946821863 69877873 102420051 603277552 996981207 923634480 578945431 742658078 323373333 288515056 150579908 117644372 428999915 686190001 503712583 761517633 456264657 55075656 75422335 183348291 559567096 64059163 451953806 246052879 135916245 143190770 494852581 114573550 194950888 228010029 925454109 213507753 672188367 780259983 396210512 985868960 901416059 273748363 921747199 54612300 625560128 152204422 188746160 782036601 56811523 959156232 19778814 113138772 902525176 859926337 895233775 256332823 355912308 919855915 144308507 715909547 187632867 857054354 335326615 635205075 590125107 543702840 108006271 74252142 942951920 532183801 468648449 465328479 154231480 865398553 466982549 354852198 607956601 125902735 817768473 592363722 874896095 177726564 320207824 521987748 409480057 245201658 71518790 281461878 370713403 616659215 622019021 473759132 701430863 46336551 512781648 511813200 633767111 977100170 441377630 769589303 411981940 669652281 381989993 290203590 791940359 744714855 648310923 204777271 328749001 36934630 594600251 646821988 727246047 442339092 924188545 343522867 149609385 830750914 412673055 272116140 602982100 158369580 257749807 633606460 213645614 219969328 986901670 172131197 364002717 233923208 22056686 979772341 184137434 778643074 553283415 482336387 983029953 106224899 44435629 444426277 820834718 778099609 113650153 420164956 477102041 875134946 184750504 470527982 573375244 723761672 135286935 107255234 59479165 620994374 41118338 907668375 592531636 374698497 679871994 912120604 854361781 246130958 278112817 193152508 422840554 110525337 2050407 199556623 111791863 528495336 895269636 667542573 653401591 497634165 626015799 289363718 206910057 388161039 137499254 706598282 240853971 622538834 52753969 374109447 857457157 126898269 17052130 131841316 111682087 225974730 542289272 264889965 920445831 843030599 908021004 591523553 53075374 736933459 49204930 341725317 777791979 237625133 44923529 975243150 184570733 178751697 453189349 182160682 955466052 727023768 43937504 554864887 189272147 42057588 331369234 103464421 157055450 718163374 189966743 338713898 338458372 7060918 82376553 547463957 596708753 161884785 924361027 329609332 924943309 821958026 974015505 891096619 192903447 551883744 463250939 956308925 293377696 700438541 353507896 89209182 94907137 313857840 898995325 457589292 617334381 494319459 348747778 346969200 41023775 59588417 464615798 422360601 623064994 599735456 2162953 86784737 285686592 659207511 637058945 394573073 933662956 309515556 487991867 300476108 173975482 94541985 995286854 848800956 584462151 975232095 393723428 16616656 994464233 547191558 814735409 356553624 323655617 964387411 198894884 128599630 104398927 872686456 211462465 581842593 199381535 484655449 816304841 493736624 707305716 970200682 371230483 99497150 66598605 822300310 985590192 999491007 338082583 7816501 28581684 607749341 611192978 465068865 12051548 85849826 873350817 804954223 559364044 647990295 751499320 609532103 65075978 518789453 916557860 308904874 133630199 551221024 500752464 614771507 639734576 517222266 123769173 293929129 669643977 417100965 493106114 579968737 222839428 104019278 560760010 176571251 395881296 478927776 28100088 849502262 432546396 871898551 796261742 948557251 20962240 944764178 306412785 588060073 849642326 272974192 370148076 10575837 596670803 942195399 296512130 272546686 57811705 213556100 618539371 422059848 439296392 201579728 401885078 842983959 812279017 898502039 379876045 819318169 346770175 549336314 741058157 350845480 679502739 963414145 90359880 951478371 544118271 888394690 635566527 824165652 696190628 32456909 597946420 957985508 991297248 3828669 567603038 621132488 365451957 62987291 80154239 315229015 407898217 566882287 353275525 887532427 862031052 953930771 59955375 689374688 801438010 488993435 354118301 120722357 118625940 115720631 825092609 511723688 136021818 855012899 439268843 48976753 546611995 612614102 684347622 248655776 348874763 368588622 760528676 840061246 274077230 995738574 613015319 460000659 762198939 321470565 70603687 483624101 277993502 830639940 809389812 120991689 369098810 838696128 354529026 208749044 126349706 465644341 614733194 949434342 534282688 555519530 432586769 819161935 729012937 673684210 345014202 272198760 252389862 257252832 731528420 732538614 196814844 803442541 84998400 77098670 125286128 490872365 498569171 470299068 239995658 965822841 520095186 774408032 110562767 226604062 724598626 148564177 385209647 322404397 998848188 905683168 752447226 46951413 922596882 769568645 648734619 804565634 668970578 424375394 225617687 351478355 936741149 6213031 728777814 570542016 601209082 961672762 338063476 803607029 795457396 914922254 101566615 413471606 824041915 748377594 188061909 617009432 834781228 259347658 353312050 376771293 85116005 205613909 148662451 853186133 360421602 454468092 781117851 216653638 977521139 158891587 634348250 349149664 601605998 961703380 193233038 760691555 509013196 590279112 560992323 96730274 993908935 749345624 317600653 335213261 900124410 104195722 196737805 237166082 85382697 165919819 811975916 740121394 882767909 999614963 664076190 813520409 606841423 315103599 760670689 295662340 146478073 883376400 392705889 449033777 303768474 139495555 540298671 111450963 871456225 469383163 688609922 355799019 699831495 456283732 468439704 789990401 713961021 173624791 787090874 527083006 784935237 162905062 986328071 660548587 795139700 449615655 526117608 213056932 655171031 478295915 654541202 252684767 471854636 771381267 411494442 584133608 176245696 322444100 626848554 732295950 807450114 777878629 12910817 131214837 393459641 832891481 739475008 230158114 541639089 839433386 709545277 617010649 590046477 873253829 326431967 217261944 157612251 652864408 555445842 130237301 76126998 511552995 980542520 46540367 116511071 696469185 589681618 695473535 605330312 714327816 522609082 18050622 105463807 683170494 467259522 509667173 271438620 191289999 185157527 27392805 490003142 255242209 209971617 115007475 727370398 4941791 382825289 221571265 576833848 18177985 931316715 897172880 333214949 861864320 740713932 91063481 204042787 675361322 799738375 201613383 319340449 931702911 635786281 165648120 761786410 660667990 982386829 823534959 850559258 773882759 768021158 462013736 612259721 997958852 551311612 478491048 174593080 788123883 785883877 320263424 907596617 485778669 708669215 302678805 93339201 813217698 594468138 491567632 777625465 40740336 401698563 123978332 172192658 892639517 199656315 95385732 369278497 222538224 51239474 698922219 855474955 484566211 955676545 18097630 660157804 118952997 689052 34501517 196691358 461959904 450940914 173965023 34289815 705157281 799380870 28491027 794657292 234183826 816554274 509548828 568288374 284061775 344277858 578846688 151336581 643148137 684762766 804326492 339937160 279710224 561345231 902337975 584963091 135806289 853106847 101575290 69193719 14069406 962555411 895146519 796466339 467850635 566334483 164170774 475480129 188388764 468585427 37898636 829115351 647908361 855955479 338912982 624927123 394225430 745209711 792725521 497807086 702657378 380823151 952320530 485173496 463747450 418671159 776463483 623602366 957176102 879026284 103875604 394536664 788335531 426353142 777869370 666145586 831024467 407230111 525563560 120977410 601798666 380650504 48236422 582891552 482285600 191077653 897241625 278889969 524389993 523776706 951428507 593307981 80331503 742779359 32458042 803721493 737230847 264405648 878836192 685514239 779224946 629178942 424738485 141205671 43801185 307165239 888475867 925787329 559615520 549947585 879183739 64856161 895500379 397416053 358704181 779057507 393407147 662458452 817064304 798390746 580164197 621543417 408002805 286904467 174101530 143442884 933072338 379048648 946100233 584476381 109457903 180131398 187145579 291185327 717707450 502807361 133253803 357503016 626573556 567025759 649283126 618534797 541285855 453010174 674867915 669355269 799173269 401137649 929550361 844995560 403383238 686903616 422309639 927535529 501291226 830892151 213016930 798496515 346300620 399797325 149764703 688878662 932308854 355287251 553087886 651307941 373502729 281277858 117491250 725637067 947396962 745865165 983990646 334248530 765875431 126857063 463103573 686173546 179227744 106731976 92307771 330336798 551888013 149937220 181937516 310980974 765981360 755834735 697236799 704680963 585678308 161891023 229336964 50906763 231534909 877580034 408686549 162228806 640743959 828119636 687449595 157786310 332574800 954738077 837282843 288665707 382721106 458912255 911083589 56570142 56979441 66085742 638376690 455822233 71341724 585957340 652589309 880066047 963807042 798904023 972799934 915675443 495843028 111694874 51513850 386245911 807744921 170069824 951091531 667019380 806735474 295236432 683840290 376154490 979598807 528311764 439186469 920989667 791073461 97329171 989478560 321301105 168854306 914372416 806686823 501144522 3915013 399611677 173337509 229111255 979395061 525718246 745775229 90262462 950942616 240778780 823020187 740003991 309523186 475448075 382755710 429543053 388953272 881115864 448456387 829852117 311310675 509984955 533302613 641892059 658368570 600819152 902967119 945943244 997846756 466992853 749687858 840525158 981216108 193009631 38064342 410547552 971313549 871119577 380430017 410079184 411146383 963444855 45487084 189537156 183396149 113935455 916366505 539656012 660094651 487843073 640416804 894880622 738595092 246064041 929688792 548111203 849708981 618956379 758956579 624742099 803695459 741631315 194198398 413521117 879939794 530134801 819148678 627169799 277847332 728573608 764944567 770353419 571899324 14271729 66638812 894596333 469929925 505354857 315517662 117006949 383550800 125567164 621102509 923719904 735214772 59645780 914960364 379157925 773626765 388521553 595622687 461678781 435193795 939610411 484084036 800217676 83820943 783719535 222491070 761981033 57978876 574974029 21962808 151743770 516493201 796067874 468402226 486605163 883091787 426289315 297682847 152001144 432793000 127212671 276775256 804654659 528850496 310675808 307553466 646568403 908869362 669590930 291962814 143492935 998389706 693392356 590919602 670256902 290860070 102896589 451182160 633075490 360471974 301479953 496108642 824271383 419497612 33123246 502625172 734294773 434856749 850016079 983391359 824179929 966872666 240972901 655353513 248921345 752385764 297393824 118362528 292444234 526204057 495792308 871859616 43446773 746594497 767069109 4783198 443201925 811410359 816557537 656584597 404445287 699071404 214466112 974372857 720427030 198717693 441866417 38120918 942618573 3876259 708589657 359789202 974153900 984090871 381236773 278551352 722213799 510800810 510395281 769210422 831878698 83346801 407226893 228352824 726743757 340589756 897812948 649462400 735911538 542537168 839098142 411242076 62923604 61234057 298871085 172143635 251014798 525450076 104439638 746602055 766183178 878163568 935045706 82294236 634939928 807899062 423462235 207368660 221853008 545796783 938369330 350748371 861977700 957136181 958823979 776008718 431848383 764366891 920315653 126202047 423762316 522920828 593221388 659902669 701271102 634524384 854887256 617443323 627722868 378149599 206286118 558451472 889813007 651945724 428889462 99981956 571462694 149072613 968930875 607461818 679005421 768020732 971839790 783785492 494330839 628183939 521130499 995206829 794633617 905116652 8466313 64487097 140805191 266624614 233481221 777351422 867545575 55250991 291885808 434716265 919371487 57560900 640598023 956293465 136735019 493663809 457754073 462870841 698154388 299197845 961626253 441126345 596403822 888379253 131733218 913327532 275238454 774370989 778482452 50759049 357233170 307677396 652366411 23393213 931697914 458606873 338477266 43602434 652347381 51075448 47607605 349960990 664891765 218160464 477244494 81294889 722977453 630793709 283236952 329629350 213543994 181989873 426883960 423147562 584354576 338989704 884960801 501646794 885870322 409140723 886066687 968195534 805461603 705352469 530078297 419121446 975278552 807520136 705082807 721965041 215242175 376927745 596430047 108286871 842968148 836270601 285688044 131106299 798546184 746474827 13011864 574758153 165078584 149619447 375651245 44194805 618492161 303780767 323346636 46465201 992608087 9402703 426504114 170708145 985541644 106023413 152467702 550976570 120660409 102253880 607609571 881250045 123499414 395319577 199668353 243494291 170509517 21805368 873551170 115988222 343323057 406532319 26527255 208497259 529983357 847332781 192547437 258766088 160666463 947525135 477536587 425608329 465645333 450571830 742238468 676535747 285196059 106601515 761302150 337723304 355608336 580486091 618516158 46690265 781396647 705088122 565787087 863272863 526893364 121836960 28818501 50856050 65472232 228136280 816223108 721235934 438401967 148998197 928612616 91582616 296252691 461684780 785289508 425582598 565249939 218159821 996655286 556938867 567369046 616962527 217696160 669434833 304894009 923306859 424660596 412688846 28210427 24062701 375463675 178957834 849360813 150045416 368766241 6702516 455146347 744964555 101326406 650663232 854940305 346778497 78433688 643583028 33402160 189376415 662837569 102899031 220358066 684580473 244712872 512198744 850507364 111290815 221553262 694749670 57278754 506397572 924766557 464254008 18408532 330169795 941852230 574646494 142726371 159188207 843510770 174469223 510766843 406342631 44972812 820933694 827662886 582276756 19208363 274869261 79245389 817704405 928065894 684527561 164320862 250414392 932454375 590169878 23635881 175284761 703195447 91239182 178935898 810521869 718311280 874080776 801734675 793507769 791602375 867750041 905004813 895925954 564030775 583599778 863543121 943106542 346454551 525612857 158991540 773314965 142987979 71651503 884810122 35833653 481444696 859773253 656562077 165017227 62341004 591792047 64729753 210782287 344558101 553778762 782129656 760100188 622099875 634723516 279795245 592325007 902494694 184375159 423703201 160380374 405675781 660045275 179815626 993462744 713655316 378930401 214940618 435168723 599439029 818550313 919375719 127246396 965779157 317080569 227687578 552105322 964431573 449895562 917958724 88568571 243721707 378531210 60319188 346782022 942547458 105090434 739247114 895346332 392586085 634754745 4215400 899391604 608703906 709191947 762248439 958341480 130534280 874910330 735780039 6983885 789603325 560031790 908822963 156041328 422326141 795545739 97216905 250734171 832434712 357092966 606452083 922021008 364507020 982514922 449956394 506842370 241956965 37124133 764838511 42845810 307109807 358379297 627662014 888530382 899156611 220505714 562264706 490428066 50468449 649807462 450937993 269704398 321117495 649611770 970511979 39773842 210202983 793741073 110549300 208632228 127166858 362818851 309732048 732860303 136227623 251515030 361065080 679481154 210270920 89318272 103915690 365526854 656777737 781321626 408335046 656020297 767237679 4207894 946362948 535949626 467474688 49146154 664198613 554755475 574286998 623060973 501700168 629862550 929291064 228635088 613939789 991494103 313857505 779616894 642820085 295213243 326046197 459272702 542267334 203304631 852975118 162758744 527120083 659073878 754086367 354131840 778871936 226742866 537396087 156632679 939063040 209078577 891058333 645591232 860619615 325227521 95885054 303855703 704144350 329377977 451046584 824432717 546920965 548111172 572738712 632798121 228203077 263446463 675491586 292773614 136971937 461645491 657358785 419991080 163542551 103781052 691476997 527409125 854998042 176167363 670463281 658449146 501745141 655287864 675008759 31458417 273319555 106822928 13742169 346588856 652393093 304980119 235450198 487541385 269374979 148539798 587125637 934436769 777587844 430781747 245988493 385075000 502949001 990611209 548716913 198526388 402985628 12772958 925707276 389380186 403690729 745031547 716635060 233527327 400913331 425251526 35435012 596829713 157369361 383764707 341874417 602035746 564509135 40605058 211838570 345112999 505557553 805013255 87009853 752659083 656002090 514936592 148878699 893367015 832979251 726158723 17139706 826045858 706176192 516513587 754247782 710931573 410000969 436500353 762752252 524091240 966985846 895885797 13322027 432139541 455881246 839375611 903915437 561233764 671395501 546026134 957778768 664746731 428724211 552875686 492740851 330659891 307792542 4077062 280031921 718905581 799971696 884660599 54552756 376255657 585959625 483821471 742527188 824228713 81149632 139341418 840870028 715859305 28000656 801807138 938461985 144126631 472364572 910318384 928431813 281082081 272189772 658928996 276416896 192503239 224706133 146734745 600507476 511169022 787676068 979577169 749631517 46777826 829156650 388041161 971023451 663679302 165128131 704084367 637751404 745146632 849624184 603893347 230925733 615391974 834331755 920552397 183777295 516715835 163801639 377313249 104201941 952704791 134927826 327772463 956275995 382483455 978296544 651481682 53559352 755231421 290938141 230964199 712805595 181591663 694478995 549406552 839093261 995761456 231445108 481808439 699378937 610077696 934355826 357415468 334749606 903041615 852357092 17555938 195804794 252504161 726184067 137585246 73589841 308399488 951990013 822926621 772286667 776328201 836823500 348401731 500349864 359544591 109012036 38403804 20367828 594834513 25510320 864774940 328178034 66834458 35664944 610328618 999534095 475912348 891659927 520173448 404902038 865508380 732236528 669155528 835681964 285527448 297613613 51638695 644049785 5522688 494943904 295825421 229676116 398160209 978542659 251902132 116450782 353845050 548755419 439363523 458056356 821248442 90015878 787195597 175923733 943463633 996777861 448090229 309994681 716655310 99474611 530264601 10576322 50934422 59542251 66812896 305754408 237192983 856504592 410798622 517012636 450073872 344376388 219213826 645999230 392717545 450566257 134374300 943090966 490625497 358804209 196828577 833464711 188392416 512836266 577356744 11311556 380692449 880057894 399642779 396443605 299110416 596165249 279948428 280068490 402676014 496704597 210180680 893447452 931280416 538661805 760467181 734478437 513324057 593055052 415384118 243172702 376989952 901632814 289204067 891533817 625242172 826190782 196302719 8594893 836942145 673533895 888220895 745273219 652901622 178041806 536574215 25820424 469976561 327110958 981229145 585894811 823438426 905852844 140692248 840471831 934916161 479168535 681845907 667231285 999691853 987206156 898563189 217798897 221875568 948518571 513518825 482930575 540082434 81374964 678640005 513550653 761993761 279496434 421221572 529635166 442110094 779800561 232040318 966694762 653587663 632035226 410048452 790414645 473922393 755114378 145646529 119896617 982133574 439883244 209481022 864112291 652721550 390959004 884171963 865245056 547854949 452473036 363000423 637986091 449089720 254465711 606268595 74051025 757740506 697165738 884129615 371100267 127359615 655533572 887798349 420737496 331085804 891339336 104521413 796828300 304729849 777364526 589284514 667888063 914636328 360645151 909640624 865323714 309340514 663116418 583641817 828447109 436158584 717502138 519342903 807643679 160277257 523659815 19873752 782870083 769112299 932498656 201246227 993976022 665518924 246915537 829875009 351878007 703879920 954608153 459489380 713658631 584594994 124663463 121991706 725886008 269384394 506662918 599780670 543140758 493622242 565902395 906623222 142785585 909338389 554171628 432175676 455330945 831947249 171583558 631052400 110200225 871287986 773365227 490415465 820337056 23397950 215115680 543983345 63889802 737716230 505525930 171211244 626310305 610902584 447552240 674390495 445720297 636383202 545032800 945924069 661524832 656453763 32682235 527379079 219186896 472691224 535206104 488083488 225718018 75673827 792143562 621685633 660577957 762777019 756794715 85847396 138432798 552703222 495807935 130689152 722457930 744177697 745558370 186424035 464552884 980457839 706428374 257675707 869219892 926800921 328402597 25727517 144969063 851782055 978560011 434016775 92534897 454823856 435212411 157795235 864358196 724051454 822413688 721977118 851162110 533715360 833357363 611384386 194662499 120121540 277528035 76843834 318004183 249329393 971834506 688224695 897387321 210838128 101944687 45790246 134995901 566006532 393415606 323128408 536272325 425513845 678741274 367623878 402340174 113791390 3402110 840582604 432357809 704648432 410175218 380954893 856335435 647605047 392824041 77066645 460948302 965235888 919513850 790289708 637863620 144381009 277750761 938149268 253582636 307909191 566944035 782187338 354060291 879679267 656583740 857084749 538140581 868192938 397418895 779171696 861492076 345305212 107032722 133854543 39125657 905163909 687081927 695041527 402869263 819127137 83409282 878308079 255888399 148227446 191852574 436425317 318891671 207527798 970986705 849750316 458267429 280814773 650714836 989983814 877336985 661115257 602423217 986050215 426482179 356772808 655736150 20364194 546328799 803300542 693310446 759887696 233674885 135931320 830923878 243513802 551317857 125451563 307645347 811807553 62005212 558992982 988785088 500427283 719090294 796310220 757569634 825969083 263758102 640017111 814232123 88001517 569020586 533300333 459447716 967415300 130706240 786294115 318226557 343008222 347139796 961480852 49413943 278235925 963845246 153645341 964750620 45925558 110667101 957450110 339288132 845839981 563407464 607766359 486818648 615865335 564923287 47664320 861053827 336799937 815371247 127255842 410101383 375003955 523105811 342242752 188560467 35156462 456047806 736779249 762453520 518953856 253408231 143408291 245802623 580769869 996792133 675109048 225994215 51116708 962532003 751232528 248602475 187182953 712989809 673585897 44882386 516953903 673729272 288294808 416433813 924821983 513677894 656783406 510617521 595111077 379901483 766365998 17947639 978947238 807719410 637799656 412468254 539132508 284819256 335688601 895427462 486649391 515987040 66766006 983350936 504674632 456016106 367292878 711311254 901618087 90032218 728194318 432876371 348863738 444823062 92096454 9236617 150286160 765705215 235634117 762999964 211687097 254281965 333633099 970054982 315782619 800074569 988032992 626225646 400066644 146209279 69994884 407621285 314938409 147630709 559594563 199598180 529895690 246359517 764290697 334575786 126339040 514002332 320955826 773704755 103470574 685934434 804262374 219985723 269505494 53737624 386525173 233404909 962178165 73923311 382587827 795245358 730448570 68573742 589928414 739440871 869768539 723363754 262779981 331144542 248887551 652670669 400370549 506715503 812486544 982320129 681695311 380840438 647784071 934651852 444220600 289341214 609010168 382880189 984130086 501569967 60014954 659276325 145119679 203661676 426680303 980768895 493750412 964936936 297227909 636603611 653886931 449710871 551541722 532228535 127267432 630614120 896981401 649241817 499430837 903138847 549638836 648519523 169532526 985057772 662033580 689444582 693424899 538806877 885363646 148002424 512264112 690243911 147777316 478912619 472522391 8364455 305891341 195196291 195856378 759262972 319595022 835798746 686851305 848847469 833338120 592168847 532799516 842143925 533331402 484258419 103657181 535892651 192119589 896096826 811262437 953552554 474495043 928351634 388032897 635139614 794458736 534476110 495856406 72909765 153634409 830119830 17518804 11059647 342464907 817074756 44918759 93634842 742322494 559712209 134093284 828040581 697105801 771374981 675484292 512053981 974340811 280674914 937827654 347267703 94460673 682252309 315885673 598585778 403301639 107879605 965659128 710334082 788191211 260585647 528388664 818175930 430357422 89150734 921352893 121726340 84013885 205055906 951856921 633000636 111912917 896406464 3359546 193634942 134393366 315712802 984465242 623104055 16333350 55766921 79150941 933653558 333818133 602680824 865709677 909216660 743264946 462920515 213539536 388878323 944629370 825844649 989195213 676375199 233053193 407566245 511743011 583830986 77278031 158872674 83442337 279478654 738762992 265110568 589628200 166836922 322354166 393186985 647904702 513964016 122533053 250537277 166256108 591985113 845208269 730440815 464397182 653069858 984681543 10410950 678708319 962438080 458226582 574469251 889893011 897218135 233105284 486551994 80606514 527393044 45421900 945077793 666692427 876456542 776878951 30558408 298452805 311721589 163116450 981786975 448636780 297846697 79599751 175145014 277414821 765844406 628514668 144491314 216221558 800981493 724320095 310792952 645332350 546147357 393287840 495004812 187036087 530607191 40158697 884281139 550037825 619442015 201557850 564282086 391214482 339971805 138540436 950496279 936249863 864975747 12631421 950893157 292254310 812319344 957036105 48984126 189008055 768972004 446695982 274272045 798519811 557830238 470123563 170095320 882717267 102481396 462461049 899261339 923408332 907584540 764938835 857599606 114338910 821819269 897596946 261903768 219368575 282370019 617136652 108159590 688843038 981619640 581715858 270594409 436345253 62593127 766380683 422984907 548398309 374297989 265642647 50960936 19526896 308858371 381863309 978674567 946896036 538171111 703666803 861401220 864556873 671865395 170927528 498529298 954354212 69378989 732953430 25932114 318661756 694655655 594396834 642931252 104932056 979768012 211487625 62852023 534171805 339498249 263807819 329988154 423915302 192838765 194849269 68345659 360774189 701454710 131678357 309609425 571892247 927046245 42660694 779481270 979105265 138268447 94907274 645433753 630945062 956554801 358325589 226728271 663596936 657481963 401775130 151660254 113038467 140926386 293798804 804501671 983261574 435820153 704090511 461717092 679345406 37290520 916832860 377187585 31130317 687630974 719952969 62122938 229656557 587564461 286227324 966837996 313568304 741850698 795356687 87233529 90353210 759685639 832761854 755377941 651333196 433390816 632164556 208772620 958582939 279237582 556390618 733623844 601921986 374198377 923605556 522392186 704671729 884763343 156313367 376240514 752119222 627355639 753862423 505025509 972487854 110389486 160505970 83993833 170711708 201471685 198172513 131667759 570910370 369189688 815134922 207340164 894199161 729939736 588630810 209055737 95856336 895889916 619733607 509321362 923198404 317496370 901780003 475616662 847238024 273149314 91082169 418480563 304953643 249427683 296574621 905265736 514863370 3986594 250167432 486554963 753072042 561972537 351328430 539897741 682426425 30469111 766369384 603473571 168625518 345186433 73835305 553101347 799297933 184511754 615168576 284521682 716630499 240529018 200131132 855671110 643842550 367635897 612992441 156041938 65400526 315370448 417122226 641525172 303649697 567092731 70405148 12654646 543453705 706248691 65306466 451150638 948551832 954109727 851524932 928442791 784208612 507158606 774167413 268072912 661228007 569727165 508771542 544907640 903255624 304924887 760408709 875444392 984806469 788425104 277410222 134980223 227089655 967876011 714728345 245749453 537549410 864809708 818827734 42281006 397997206 801878378 796603605 1849717 865354883 332465374 413580719 941861688 543412779 809693595 38534551 224420577 553446288 772928770 30835376 631050956 103055400 234950295 405997266 102190419 645626482 602547735 646538484 187576328 433163630 355661574 984953994 306354117 155674613 630074078 130817210 192760983 496334785 958387007 403116948 926146723 585764931 684570964 705916128 886138459 314262353 763756208 559842888 392910203 581829750 111767943 215476217 626270633 570289648 5635856 210762640 861215935 985533473 832170548 909267680 597146064 179165329 296904274 883397197 992357803 388244571 460832391 766005152 517860978 968943598 692423156 971549662 505799279 532708127 428379345 21226677 514783144 345782016 285525813 630206177 796190267 183877241 795575000 472182354 616779229 880397152 718252615 131351135 855591069 926057985 948429608 193541436 623580873 687516144 540237511 746541683 331547912 82341606 966379149 127650870 872172336 53543135 930320997 678543070 153465827 164991343 790051868 246000703 436006146 822896612 531222349 891335331 24701278 686027878 826754279 601897537 691159865 20913118 878905602 891396457 979942988 268248220 551201815 758793187 936743353 18929521 755738410 56434655 841450793 594890270 67356038 155074525 187651240 633033831 347908621 12278919 912791996 144172501 493551430 479109655 902058653 54261942 577072132 86963120 187522596 619942973 153912774 447824395 800048478 298723347 138287175 984493661 493634356 203744177 249877831 84658838 545559034 847777043 614224154 347645967 251071686 333255873 7591962 414411081 153075896 160377686 601377775 147870893 502651603 361645861 633356373 729752402 338537120 956139033 263889767 105405554 108765947 516262758 970314508 521644434 807593444 853684976 980513351 497604812 689939270 942077061 524330755 543606323 706224497 253807782 309614886 68215749 604065046 172089064 712935008 78181427 769991140 392429779 157330106 637578929 537894676 528804426 346213045 777625496 188183966 798809469 660641746 880490100 330403196 51379551 14817075 139491710 479054187 712436027 123131136 913271930 514044365 143207933 734441803 190232522 647334388 719705850 267483339 352566530 760763702 353364306 325311886 944135419 780778385 363589745 15099373 65445418 286993720 3523160 678652952 501804171 547965979 875143735 442739822 496643706 999657324 40317833 372525699 854575789 307280315 962910953 193946415 386049791 450082291 418423268 842037195 421650572 962960848 399219524 942157822 81907427 386439457 118132066 220658629 619461263 691360929 332253516 929181071 390320937 61992933 94879427 299952086 560509324 286875495 901814930 994246195 23885587 279268657 519363857 876260530 428550206 3119459 451586374 514627000 328703757 219001034 700670978 914481510 173584439 908553310 25086533 457149996 623928050 288476191 747261189 598378545 495729312 80547211 178450272 998256316 859845000 769080997 8093454 945841952 643254525 32660686 321401375 385501397 228610860 823940866 418677793 650549390 882452231 843772446 758531122 631451586 462771687 161727518 729096323 239121548 456905012 525990881 724264528 280247522 57414749 711165898 26723272 2427612 8633417 934480117 999185715 726114196 297133324 444612739 997376486 668201556 922000259 760704917 342951438 201195346 257017587 948682182 965104917 276690777 422274101 192763376 793477980 748898192 606088312 495171734 24589828 938297561 105725230 752593037 662203361 54142857 662722777 842419128 357559605 136216403 689399320 545617057 934820069 423769558 697445574 987727148 432841206 822336484 163714009 750117769 953660162 129598123 985352187 502195507 13532077 901099109 851082482 11518950 16980209 229690542 787774332 941856274 61315794 857897764 811895694 322950648 768757106 307763386 676141731 636419565 132366265 422612604 61592569 963642582 318946828 949677477 886610948 824878552 981466164 540276855 707802762 502288675 867205012 490490315 964715835 482494171 780446548 713388137 263429281 457396555 809349474 343784303 29766558 318589454 980437578 395533872 774365226 822187468 546843693 896740916 423096663 938909227 514171367 648123455 912162244 371485882 965268109 332796591 76181255 85141940 548747067 820011829 99260101 871932262 369921246 652771209 399323768 526725409 885440435 936159483 549705132 752550640 100549254 365701553 711049563 629181003 915268571 305918245 246270671 59845336 74041664 926544575 94290308 886632011 969181792 994462098 941996706 720823598 398576361 294260097 47781432 678806620 906876663 329586883 146205790 882759298 6669641 426852531 737254791 923036888 948422339 130497615 367838717 963777517 202506118 415661712 624686465 833112375 793205402 360659436 287807047 910702616 966739009 557719334 63101157 240994854 865659212 808359358 410052175 959775722 959984959 842456215 332389962 644289661 434364843 683854983 651046105 758278759 536015089 169528053 798159475 622168107 391975477 511872358 264811782 128139273 748082077 356345905 965313406 787968081 509783827 212433806 534200629 973387511 359025276 243656833 397338461 140408063 853927427 748590331 532279199 304138367 364314485 407996740 976079010 111307046 883211517 365301842 505081178 884875788 73818584 252620987 939103203 945954169 728600480 669797525 862198091 814343034 669847497 563560891 410840531 50347033 571400844 209758591 252085135 788293141 835165679 272028077 877197247 722447687 818108379 977639572 840717489 636842469 196139265 97832776 869623222 131007965 732756682 993495635 523969088 571986431 262866629 119476802 7726071 171841507 674693501 606029835 966800960 578865681 76708263 204828016 29553607 53234831 628879173 432453527 487762843 114656338 159333796 876319046 22847499 287749561 138758740 626518142 286035363 288712521 421015729 241135661 524710086 135562543 46389232 323318586 991449843 692345892 24464470 916535562 575872673 715645623 84431315 91459011 722856202 750826760 173061155 99387066 30225564 753862344 143399909 495388176 110831939 481218041 580600058 986305399 564334765 832898086 89763919 851626118 260478552 385151911 570361838 144503717 754278470 462048191 763459513 217074869 624422007 805037327 737782216 116337333 573797958 633066979 274135594 344655389 936787748 397368903 587127008 780670059 548341011 874719070 333434243 582559833 850024939 599182429 320606212 445625746 832538544 391197100 143461723 678930619 885545521 207865115 916604226 81983265 400616984 636361474 30348511 619284126 380746296 705786304 447839524 824081763 299327497 642933748 237050547 48634553 16464693 291442004 444498333 192057401 528886600 191813826 787661563 544538287 214600090 614914410 881825780 821086725 617081075 118088060 544634120 529613575 456580807 193147029 943618907 387364025 365945822 720383276 429095489 503438198 295393151 999770601 930545391 817247766 956465972 279320561 491314725 585859566 322229287 550761678 973804036 881960479 872730727 258284480 257102484 51597128 278382513 889595935 250991297 403341502 750892031 886244935 871042718 306218899 220823760 562688786 14285610 462482444 194718850 531998709 263289195 813085016 891628661 358779211 282284385 243430886 820493514 138839890 780950700 337644095 933641679 652855948 524425217 606582222 943258788 518744615 478412065 717216642 333261344 365179116 357137974 474535710 403033961 26824301 342816791 296981064 264295999 108284396 934175945 811803894 626486971 958967787 200768590 598311081 637033818 525056106 13712706 817121352 798762884 859493160 430801849 393872693 103006201 344140225 791026722 801380683 621176311 52824250 47764236 646124261 895655236 606336809 958167902 24857207 91181304 977795458 681350929 884739347 747787003 459055456 547265030 57509925 409988838 785419331 227417530 504466174 79591109 395018212 182271490 6288768 327770843 528349963 997767741 191973946 552519782 581062909 516907388 447756414 610221030 896297941 634953541 148150411 48211685 276242508 968476762 681997808 607005059 841111544 985656360 572684519 526993951 299586107 897414375 42495337 548200235 724528207 40775154 589548958 579082764 775749555 229834066 94757797 74873574 634058942 515963057 128614084 444661690 392463059 655013739 970452182 227400488 490947795 286783998 573815498 570418457 442547572 923623029 19199557 151724579 792445929 394464167 742263889 359207763 940155310 611937186 99736908 254792303 246548152 573704272 604962552 663248716 196193262 193332370 527573616 626667716 6346028 715227692 719355429 577881484 516602350 19793550 211096105 541753146 242941021 609830180 497052013 44876867 405487022 856297858 800864197 115746971 150357026 860960891 22923580 326921262 585378186 233100608 538089745 921153491 351058179 991333276 595557359 852240346 82873071 139120223 68406177 958455634 706715908 960019694 592942234 934714864 116333172 168336855 912340967 587192154 21917421 942521381 899386196 513867998 732795899 449181114 406076074 206095839 321216027 998653915 466516854 164648524 898463562 374458677 392521772 501227376 333152699 832752439 557564904 720871697 941734661 730714780 533083808 430381474 608768368 459752519 387451441 372343197 223847479 411393512 321764363 790432757 484554095 594335428 457935313 638634899 465038955 136846910 233509875 662906143 189854162 384817619 196102226 700219191 423280841 978123888 1866152 807566644 802094361 510854525 46331044 56399539 132975547 469229105 412652530 857308155 248185468 563080029 738189311 245322394 227199277 202290737 540229780 203673095 938081594 460938687 801305624 829626657 256124195 297641247 726361327 233026560 94391438 73290147 272737357 251565916 619098598 142216609 439459900 366464625 93561876 535652883 478235562 261454537 298911458 770956675 369444367 490330006 373257854 493797342 246122109 423922609 566627921 736224258 185579934 94293544 603309750 906312000 943932524 925014119 791389557 96078533 816256749 489469240 269042901 404138378 4487207 865429077 155500178 344488710 639919553 933071310 650359846 972097087 594546629 49584870 692794623 639571318 118893249 465694892 153832426 398949986 762626968 623422326 226819777 859621132 773528016 184580740 319289140 83352180 353242044 992076477 260817588 144128021 363687152 538379841 417797658 160716733 446657907 495565393 967337209 725219304 331333180 921662881 435859285 185230211 183182884 322995551 708681256 909184085 336390530 412439429 629290717 24332045 607585904 894304810 915707923 393184012 689540727 913225102 90575878 848206941 682821190 242344784 196025434 738133037 956616155 722446680 899503507 799433194 654857878 240053992 446264820 495523747 323318717 411494653 962223779 859045866 388588895 328149954 625544648 526636525 134705216 507137150 136457631 343634974 333145893 668736417 274682624 971017702 516565635 381759308 714600804 189923881 576920340 941044495 684869351 359859651 907823689 969469741 444804239 473063166 223799176 572967375 48315781 575772948 930822226 818580292 268184242 786664184 913554332 287078193 531509442 804276396 998086493 636362044 441458647 352547799 596959604 421612655 892744282 998513580 342364382 139716163 252563037 389713099 242304198 72981762 759551130 929858653 436659980 376575401 74155123 319669435 374006032 162692770 931462566 115695254 519683868 970373962 148213249 864542287 624717423 129144400 867249354 708717273 896225839 536722811 54663090 332043727 33411658 133409585 290040611 202215002 159954148 542406157 530000300 798735348 107946188 107973208 959402697 387515580 179923227 471459010 841351253 692796455 608484987 707809157 763048922 776533887 177431529 255067158 481007368 355683754 775253537 551804812 140097617 809742709 374565144 812672518 617714619 337140549 41828780 697441327 534988691 692238918 807192883 717487496 254972264 717166344 288144051 20104781 70549479 951510934 630725779 963506273 569318193 397432973 292633847 172442812 682613805 174728885 205032950 181871239 414562262 349521940 733812911 352037283 226345418 552705058 740248360 72486829 566623355 43494331 711437308 431296740 962678015 165136928 424989420 619042443 733981203 492138432 886595456 85865703 333944435 776551178 724040373 519773443 369441599 663057698 698904693 284121162 516342369 722770324 73227056 301727062 371437386 117685577 109003337 401551728 4488003 465926050 76409984 553233853 697952636 58894605 81462581 939969203 951059585 313598640 477242019 728300219 360800686 416336626 871746742 53684688 577517268 563273382 678551941 66620813 882554003 862171187 499198639 408903797 8349915 917598494 201499236 883313266 979103084 43651257 808176790 328889034 321138931 170839782 51897571 2624803 189012697 110421251 955672536 858881303 57489726 658806629 250431510 51649565 601396051 183001651 868138655 184299212 15503262 969340556 557307228 180536582 568201843 639144805 164137475 139973279 554855482 294240460 560634980 159831682 340831707 557193965 816756454 449551680 961263390 206019063 368707953 260731801 725066822 87487156 447467764 965322631 81561568 674005986 874261963 225042650 967238356 645528827 592905695 871511664 816083934 971368783 77051319 608543095 880137034 996060548 367612338 943313550 193450197 225563996 944647871 194126007 966413520 649726776 73097942 21265217 975298912 236492551 224097162 488698510 520028923 274980835 107074109 713026411 184590224 782090718 184011746 187896137 269781821 760754216 79913812 810630244 265973607 964443125 184588270 814122916 599404238 190762311 668349708 398296359 919757880 920645052 421285209 498502507 528968245 982371394 862490925 949877696 741838984 448378148 870562615 237870357 698269067 839133244 954656777 702284418 414137243 778433396 677888043 331813344 142977419 520603500 506378037 147536622 727109496 811026894 130782356 61097872 501335372 599109175 896839279 350231572 995217914 916009703 789376240 802762224 93388993 870337991 386122968 42044093 552945543 292314455 169535135 54970310 504863879 408707115 803522579 81553197 797180390 658865903 738255736 364499480 606488723 777172287 927817608 738740871 506802747 963060324 210020372 757437942 980586219 709770406 831258534 138157656 739221589 936816610 665543130 755457744 848477936 504171613 387326376 670644222 505868627 627169787 996239475 810118241 363710101 781556005 922059384 233494231 637598252 773558930 59935502 300562987 583817999 768435767 762653744 127062188 744238238 779771249 887310097 260301798 162731862 108631010 65142176 440803624 803055896 580187981 502896940 645848290 411396260 252836304 289080279 911437534 191006731 905706783 797911461 947019035 650992652 29589446 164933061 816484870 241792785 546664652 533194870 693746881 41445825 492194297 161325819 802316449 998399401 853758492 864797352 434692590 899731174 856675264 168256928 8848061 665399415 339969229 85533594 713659944 561417842 992056115 805155124 566417625 394707036 107650233 549498439 469920502 253333337 655288146 626626293 179170827 901973765 687124126 249793475 749479211 415052482 768287053 581270962 888462219 273350718 2873017 915137533 642905261 893640431 100724842 776230001 763338260 837198795 722870058 244007201 814898339 483792041 249882224 609012585 28754555 856021926 792751873 399843891 661348450 617932314 26767401 392137253 640714862 326456928 968251305 532287818 971619076 473202511 274222795 930935015 214987233 886821994 3822639 628271441 894272860 319224862 74179180 755522651 706833835 173754089 470892870 925938082 691594007 313642380 119655790 317072237 221038206 35975416 897894791 428112920 219623287 710704205 807705725 798314067 290129859 85164049 746610631 897826813 450684043 738423236 199905382 731840377 890034523 152426510 527072330 133590757 753482875 894287917 604479995 168266380 465503388 627089913 213550781 534072747 816435520 142373916 450754982 472046339 655288433 115730710 865955577 632992614 741344161 892340985 190720632 980791909 978377666 990237420 603665979 339142531 970140127 268084178 794821951 348718959 232632866 858865933 518965054 86948479 542437021 522672941 86011917 953935091 684349547 382497854 822724323 795985371 20623027 936055425 696486483 21315650 366414418 612077690 637187654 497202206 393550321 298213832 772817924 469898398 826632592 36997411 150917213 481444225 377137541 777877484 822876776 280998559 410338921 607964122 349704889 683244829 976377188 201241292 666417896 156110380 564699893 677557227 484955760 292090201 138216228 925480380 6561332 829806694 998355472 506516040 95590787 710628759 160404221 885601696 294335668 310786773 362217731 86285644 578669370 328274324 148579318 177804581 596281980 633596752 860026174 969521196 269881284 993998452 415313503 47795726 785612338 373594068 554346175 642149560 279011081 689681760 22658098 114567774 740646812 2960714 802832656 400392246 895435481 226919124 564156703 941120219 979002692 91525545 772704342 305057036 525576165 869722060 737920127 505858474 464669531 889051636 168313756 547270583 692546452 982042304 325058059 983647476 105174525 570942767 158458894 654417949 331661620 656899114 372099931 143846241 322273711 373570845 349819990 500191823 658907996 283482502 836486006 24617605 949063737 344133389 350309694 400995058 890814273 173246153 554284039 926115317 874008362 479092125 695881583 960836060 203643079 75673396 215459143 763365628 914021217 645719015 839902773 817377811 776419898 997893600 519601620 426696406 650444468 801275727 635275703 820370289 775315394 36394221 411046838 47444073 99189242 798590999 732700891 389960477 718452875 666346368 396633150 531823085 362389394 461201975 389405150 581771553 888644296 973572052 544823467 734478745 269673441 778548537 708437471 47278093 528826894 174457383 823147481 331215905 26712282 315722045 360706204 76907242 955616348 785334994 113055743 92966830 842572084 17864189 557985551 551085598 553395768 416364474 451369260 834112756 919327152 583935793 277078755 911059782 796748066 614682831 901888777 129460056 672114587 473934288 651179757 255703619 313057130 653262646 856217814 254823808 979538877 971656314 256241902 405461974 613593160 432642396 57845345 76601346 566763356 302862730 520115519 986390333 76110180 732672156 367161916 630668169 543475862 301897525 406425716 224047303 332433817 621729298 919151082 20817289 293336439 66390160 967670648 636268721 109467560 428571846 431423954 344301841 496001445 218365900 364195762 347281977 199507292 731983319 719908294 267948442 424746653 966557927 534362899 741830154 94591194 730123383 469602608 626713887 347640770 697544645 767348523 853113864 716257719 724802810 99839936 346413202 216419384 330279998 222490784 410655162 756495635 351379026 47087804 310778337 66754895 80320615 925002767 175783341 312566339 981058629 488390703 562476676 589528749 576984398 38431991 258690182 409863262 715370837 922156053 907290459 519973719 901690324 23041999 615958012 743093205 722096611 128543501 638768816 95358813 89426643 268777793 206714751 895804282 9368447 906493547 264227723 266677526 569745063 897233340 253386715 237031035 236530531 417396314 53449862 655878633 389685302 504037706 556424732 294837414 853142351 882665012 510300426 753375430 497222558 366859544 199432065 780635789 482870823 362535646 9125477 692455377 701477209 953635590 432398605 89790123 970997304 661083755 735108240 592293188 466756461 220775010 863725924 682942440 175560884 458303600 440973310 449762690 231294741 769761677 149964714 985895139 774878151 317402498 439604085 557445961 352055909 946146580 903274801 562684952 743967514 601331621 890780212 43401162 289722655 436249874 367504802 713103406 63113674 750416340 522770266 853615027 137172118 340653336 186599780 331878145 987514478 225926636 571194925 499377893 561426163 255035432 515490189 733854802 73457893 323367936 394922587 635860636 326094670 548440042 650059752 102598275 247180628 961836897 948477366 228336542 864553880 2641042 506212329 441859819 144693311 676173158 201385138 479374399 393728293 370130107 113811572 721499441 844674236 462074784 109574433 757864015 243061783 17886767 470597862 446844144 996778267 657410331 401258573 707572758 688069674 738643702 398412113 458708662 923290034 688863044 704385927 341947259 886130413 893761856 623753633 193771002 71089183 681709209 366595512 618088041 274386422 460243616 382526462 632331888 418047865 646415352 444096155 161543228 846340451 66276060 652271359 38602386 787472664 284641853 542532008 442602484 911759444 268621985 977049545 137425685 637832814 860863354 234098923 819189754 798218122 988262632 646542627 251596788 79990045 56494259 754859541 352481880 445416525 88458792 5765592 99382909 961089856 134389529 998855100 441953352 612946676 982686639 609199381 253652463 964605794 522347375 944645830 461383248 468533956 386630811 140204526 915617715 245851843 401616507 928843003 949501778 392748759 443320066 873178882 246871219 832928735 774151358 911210708 618157303 338332302 466476618 591580303 605522913 347699337 112881315 751884920 696501619 410452062 887280572 576591524 178102295 171760312 524453796 950723721 954624021 194537459 428589430 69458243 826294387 652493003 56848977 791708295 124753718 201663966 759842763 737611865 601298117 530378084 266030917 450187878 301869069 636325423 454388238 57897364 52753414 961780133 869681114 133020222 161965316 873878093 403330978 630618944 757462857 725076627 888605409 666550664 674145555 269402714 45637144 180501002 301252259 908873413 681511969 373521896 79006881 552899736 688543100 186945460 374073323 392091963 899331084 738737420 784311759 955434316 952982765 108069597 65065536 581476790 528086971 229931258 821644202 840211603 609190501 228361084 110186244 953609498 718186303 45482474 250547146 103564588 371770653 190252279 304648904 551383611 482642101 347521954 738821626 541372287 213312629 689246475 394275003 181050899 456179256 841351606 906494655 792413085 742717105 553925545 749315796 859021232 342897957 640656579 141995508 936702603 41010728 711128468 613956620 92308722 871495008 534426793 835529927 550908757 640209738 235101916 809593266 466738296 868308180 40632214 177870408 285401470 498527797 339301738 220951169 572623172 550138415 236885018 460391497 978512531 983260015 13081035 962010996 474887835 63655724 187527320 842755601 77439882 59264187 734633837 644737126 606359859 86017228 243470291 194148221 327327561 218235358 636905218 793589104 51172893 258294601 864370326 211926335 708359624 568857820 124574235 405272010 840608161 997370257 425743300 92756511 612741385 570743810 851117104 61143591 585608320 187531014 350454664 465247910 156806228 554621435 981188637 426586286 785277701 990433598 395770442 317329708 634726641 564140287 197412904 586604080 505117190 124782448 925107359 426720480 655206010 286617708 882239743 550737540 892752713 123204193 162051663 55390336 630791575 901110318 148140816 987378352 697339495 674638954 376485965 775643196 816534910 707095388 62276102 672625143 846433601 556972657 57889958 288966452 513776969 593709360 780399278 58748808 435994455 193566236 110665302 679172157 116983234 699253482 602721202 68384943 406544631 562415568 740423915 481415727 717505864 266779332 54343774 338852097 172147699 237041913 584018848 595527610 474668246 416728146 572107215 274014953 357049320 621753412 151261710 267393119 3161389 48998023 357656683 115364383 176523441 266238803 625660404 527470952 618808460 105878320 794449703 503488093 916354870 641017309 636171643 753949941 615595033 428868178 321724603 313636120 419058069 809560972 824994418 837527723 585524577 521183837 941396894 325545769 830516128 152269056 263654630 622920341 738245321 222788475 611105043 883519309 587992779 45520148 920496844 354367156 908280997 859548587 437658918 93462407 528994673 744558987 871099047 609414177 530434889 62407920 652695194 352391491 819069788 927513020 279700483 157508391 836078569 882770568 384233663 305795838 625602825 250031194 50741277 611699107 655539903 985807135 737555075 167160030 736308325 945291012 487337405 287371293 403640162 404472356 29183788 589474371 727076418 603904553 658911961 351231590 719332338 441595077 714387903 793560220 35295245 156331655 226606447 684838920 855651217 338558280 172590099 813917855 906336635 65790590 989247003 999360902 276179834 387177601 14128478 804912679 601157395 42189821 757103564 538864752 637957719 410521565 425066877 233327136 348666662 215485520 136189860 755924060 530834587 701024217 676433697 878916024 159175343 841476436 569723600 775614910 622054118 84454242 892052380 379484942 160119448 329420475 793511108 750764252 182027008 556954122 717817883 115371767 200006453 328102764 617688832 849079972 107591114 636616553 175586730 999697717 761223652 9859688 199117746 598702237 733902955 943972533 925932913 625772007 928803664 333172682 300981348 800225344 940689908 847148899 715841805 529359225 536253580 527748491 587355845 452887749 802784123 290068245 954478661 566515419 516138220 646225912 764297528 166192478 797292977 990468721 921463219 821857401 378173139 740250758 109760360 354750514 943481903 535366437 95805954 74828498 824430632 732888336 673352913 907137566 878884046 846857455 363690904 520044251 839506758 349319712 907853449 329563017 685522409 343557556 69673891 581718059 272316807 437585511 390367867 980768013 360208884 389000233 768222360 452650666 302870162 554401980 424774725 187435666 856902215 507575002 583494374 60012691 803061008 197868669 653976722 809787132 266402757 736270882 383730023 692567911 704680992 917227354 171154491 368528999 694666903 835817257 215852314 8428577 392551142 941734696 457730758 897263886 271765759 885649722 44486873 534169406 698918737 506366059 3537406 235242499 484047422 919689278 402177813 72323385 179689586 767835950 561972632 265815043 456326508 943276163 79129515 122489122 884467947 370113072 915942665 813664838 130842439 132248766 537773956 481514041 90115539 189869817 103872671 906543154 381699724 885684593 297684914 957874058 956707715 906529805 771901305 835916175 145938030 824856013 144274712 868935176 469355890 762499479 239108285 189500961 505412251 730309519 118515398 552900301 767981202 727178498 709415008 321269818 9096175 685056430 500625075 485929633 912749124 425641058 249965104 251257734 137224854 424070033 774273563 968061659 554638612 684736517 932787972 448588694 67736965 451328082 949204578 46856023 120056874 233625518 590560902 770871422 182365049 219312387 638768423 966438285 797828245 213290365 944354192 529113922 494008626 609822442 177389664 305990490 866413673 769800850 843553101 484019959 56957387 732799813 170381722 940704843 797063384 919518227 909394446 895494748 905608787 533267144 176757115 951198044 931179422 635070932 256198024 557307601 962929644 623835634 458501604 404487895 596931009 926358716 852216721 792943052 154190300 77335455 41696998 689480865 285190471 398260473 651577552 846615012 72277343 228523668 976515157 564024961 170741609 295225159 190810128 831948322 69898702 225936092 757761584 128832998 320641384 435264515 251875976 677303354 595513828 299377462 465546922 502752505 12251598 545346700 142281517 48171371 710612823 499426370 249138468 860608359 894552515 4681449 628633454 280470984 820571133 938647477 5596595 302274764 266684166 520904267 293072802 938511718 281618309 947343448 294886684 499304777 259310698 142191263 387731340 378259164 742688853 688992669 812081759 110903322 143466960 332373865 98392790 350179449 939535498 291295665 399467149 742341420 597385078 285108902 9515512 559102341 755086654 834133886 690894961 615530876 488490597 983572650 675760367 834500908 554415489 318479234 452556929 454521677 173926625 488652826 740430991 289787356 412317025 113763032 255536696 272981012 552924949 863573240 236148141 953301983 589885411 224868552 455750360 236134784 305319544 950047839 505086 466414266 303110299 113621478 450029931 75683305 688521505 718298237 40663867 43101566 79914371 228541899 193789265 491486430 702653115 783015030 446907678 369155506 649847430 205331702 676185192 64819589 714435693 253226915 461783745 627209641 102490824 52374562 231408097 738791384 785586544 551172353 387184123 203264345 237323751 743726134 308493255 772432650 935437984 668644285 975995687 638318920 211465457 740544002 56651178 134107973 711933486 647534786 55686000 427327205 571511022 763817008 323309479 362823598 781960200 122454805 700422124 629603068 739309715 758192477 605251818 748834826 986323763 221967377 149518060 866443368 961802565 30268960 582066968 917987587 681920130 689882305 778807894 992578721 257570175 923403800 715386337 847875527 968019265 549494033 846476181 12756539 76345543 429192060 671365489 651919705 814752971 803079185 610951256 85230539 535687533 547941456 594997268 299126193 187982259 365255608 250000904 580077159 705591130 511365438 268040477 751987902 423204947 430633376 45469024 49414164 715051461 287081393 51561039 371819004 616962846 191450174 867529772 413217901 328496719 332274861 841426093 673933375 173330337 239196620 853568899 815880844 117581170 1495443 348769102 594561450 791164793 241425034 480903175 840392218 417525222 327935273 776906304 463846262 530182941 445598288 294095614 984882896 302838901 932939987 445411079 823481784 238527931 41287573 531780511 257468326 850306483 353266926 1875769 863012773 126814138 321591325 588611272 823065491 143702196 864348017 942411962 968067845 507537569 961382927 6704928 54002604 417902888 682003976 502262582 729761627 414622974 930801565 731303283 35679175 377258462 455914576 694062029 267858284 18219552 39071000 394118159 207805745 56572891 953416236 281298023 828635804 720614179 751559193 967786907 108364222 205960155 329472859 649115541 119069070 72190343 273142271 980191688 208863692 337857319 894679340 525121426 509389820 974185389 145902138 350489087 791483233 815990628 320510745 402800632 447383018 936281352 567584659 84995557 128998237 562537188 405549445 745259164 728142496 12902427 430335451 217006107 250359552 537658276 647768707 874522816 660199976 672548287 595947606 825570519 726399142 560958291 405977491 121050563 644975665 331056955 541205157 846760683 950117504 481971374 411708163 528555736 2137855 721016724 164465104 364451242 296187620 487057001 953787644 210942134 342993429 617102971 97789228 48399235 331810856 852175714 941999577 598893276 421114599 462379464 10734985 489732437 23569128 82314087 313415067 922747867 595237094 35429794 573604421 317425978 139013286 770834444 89627879 89151331 346943490 580373387 238502285 970326213 901410457 99748624 856897545 737126737 586348986 19312358 473483623 429588974 82996733 262588686 322111962 905206372 22033402 330388979 399172992 462303957 837792804 568242672 11966252 895519893 596795905 285120397 28515985 26749966 335765091 994648584 679035964 27648117 817051549 829962760 540367259 43902606 811307358 178623869 115594497 515464375 713076051 45598220 515082592 591835042 998104265 401383553 596889845 48492216 497740314 298201412 697388050 759899061 165092028 530486166 452649218 404732795 24333857 987989277 14038463 132444714 656966296 855126923 161364440 258825276 117983712 381706195 436196307 250913094 737889118 551703231 742330512 601908209 630989234 44783076 763580586 389968618 878543842 897601958 780116248 128708878 885346980 542265460 55980154 51985517 443362547 289534058 958348853 349174806 443424676 426043664 730933522 121928437 99899595 1132278 842170615 595398312 971780521 272945790 472045980 844369205 275037130 234881517 469474560 586797685 293359819 724255076 725186433 635619032 397405756 960777640 910798006 860841258 221572329 28497618 90791621 808310955 718705367 661423568 727810893 384556599 455694871 130206055 950415951 768798619 749028473 872401926 570478243 736460468 991973164 754013564 468705047 830453289 542470358 89747962 56732767 107852661 598016698 675394012 217615976 496238085 955393964 588517868 328413821 41896755 989889146 306697903 600154409 202802399 741752458 319543135 946467488 750823515 459983542 316998477 462330411 799432839 74237420 823908135 848599041 599467215 952239963 247903977 117869377 690853298 743445541 505225861 184012919 709813621 980457200 499327110 301551136 150324512 653538869 920469357 610295096 878614901 617237105 839654332 549523605 920676403 27032885 879062431 305675051 289883906 805612705 110015597 442725636 460222806 660595269 104653250 825905962 665883302 805849060 22933308 321673202 234215484 360907873 778488480 946205050 728603171 119160688 71601615 204301842 467370416 941048585 354726206 248893655 238015001 653461905 237199670 972331106 601599794 809982231 602957678 435802442 999948496 366803135 618687157 731695149 174060649 332177176 233115745 297255403 86890772 381377808 484607284 312137983 532963439 754066825 706605867 146351516 556578469 565129682 319629031 554000361 829941351 294222122 264568523 530352515 588468287 498433267 97668612 782518900 698684565 479365699 287690568 832734636 510950427 321446741 787898678 37194856 486231570 544114800 405008079 417710597 765883320 600379800 482722439 755814285 241922037 201214884 132341874 688824954 313617405 538242532 55795206 268922339 803344634 438953765 542680212 87701900 678588052 382578775 741118358 176256022 135797686 630050469 229972085 916710906 912273458 713790290 626764976 206847165 495957766 968796646 954521916 928469766 134396762 709178539 258242290 83675687 25744693 683325202 81233637 641142422 398924586 26048157 263129507 524071855 87937805 762565635 678561767 953407239 836863088 743949266 621230539 765535487 282230419 677116362 244897945 587575259 138055547 669946391 161270744 78629931 241671681 720655331 184367739 2371402 957662097 316272675 712425290 365148303 800818562 621307900 585713588 759403227 731066395 928826725 766705834 497189573 167090071 444797754 818909446 674938845 634413280 540356473 928581023 924515510 338402800 280472191 73050340 412631700 760988753 236803783 362180128 706264505 782417767 551302396 468614820 615686873 35881098 918978929 590141845 982005945 909895276 365328923 781134615 666635707 802262367 710993285 501566886 800419706 481873114 328024696 435996743 91026757 699256886 835772994 571334045 135525925 539110817 726540759 413186105 779192667 939993527 549438492 715269338 394123831 446696330 297938179 746037366 280638668 364916478 868682099 10683754 844373022 758554702 629503513 521071232 173640996 134928365 893098949 191616543 473583973 712028162 145198103 466935698 526323790 137620532 705327265 460026345 641355429 866389621 173808043 353630793 3057904 104192786 333523812 552667585 572525684 224208069 458847058 447890570 929609882 523265945 694118790 126100164 668649647 164134835 900782714 720253013 595435267 944424398 581666247 650075495 925402528 151179604 845225976 72685276 984152903 319484198 463208493 851803418 376490682 788484861 525952501 196361413 54055546 560224556 867573631 536304699 988527761 230100634 623055005 364729513 970313801 292406275 519187232 326233198 820986722 450333464 320674160 387784053 752334739 85431956 596619380 622812178 692512429 430560128 863212262 685714158 568772871 926404488 199799259 167994403 562629866 115976339 54910083 711453656 619904521 600481504 388655451 67624348 185694100 491685734 797283410 811068505 276547109 739866728 129158929 698763276 43473255 904701299 543133516 523300732 760156357 157821211 857420875 747016684 620417651 813493689 390637803 652308177 13237756 816501244 886723179 762748028 472956262 711507480 164863488 23732443 176770919 879304027 862636912 941745493 640210906 666545246 833177294 363923759 585895938 380925130 923184833 267787740 693336171 900988274 604456596 563194545 154912126 754279739 891104366 137741626 258298161 21005411 116802156 872347511 613040517 375900501 375811744 715515952 402935886 653994652 191801988 159897874 834483497 781875000 774382846 972631311 626131115 820848594 524971591 42174579 495361935 79906232 975086138 532004648 126492623 650558465 201425454 316008536 724268284 114458517 607967167 695635162 285528627 26585779 221039399 873672759 605690882 861955792 923913875 442024120 599192336 22498871 959286843 628102174 958187897 818427646 770167707 842584985 873160076 437425452 142659920 168256502 800698570 276257463 50885025 420788655 483259206 121045161 557759333 673781107 98536419 876280327 157406546 157747951 808460316 186388847 416400078 700523596 812125109 705569995 668834125 394660942 61631460 592654018 312000312 979410745 501434659 23639641 939876052 339605023 587753096 392476489 52349580 54139242 69386657 681575079 108819120 687504887 255688626 838470469 22511513 150728963 369117045 520812042 225682524 45381859 242248538 265402059 484507384 947596089 775006998 312479729 200723079 98274798 145621062 504001444 972853498 136112944 551164455 808716733 339454024 148770900 698350382 649079859 837926253 641087954 630325862 128995496 485078725 839749531 966936391 90632950 832717618 718256795 833609715 801593363 52311420 16336935 80058730 97361598 284369252 756933194 800464533 680476941 565185245 459162392 662038673 320107679 182742417 485173535 208479158 548817690 119687039 668776632 10393723 393433022 35670179 504740818 888420925 61785891 905803529 917601 341487385 392686875 453300742 780854957 549641507 650827731 142905493 913939663 198112075 442583514 102647854 458784638 590829438 828383797 122296581 671498118 975669271 401672751 875414809 217757406 750639928 783596222 960283524 701937442 547640020 723490066 610742915 435459057 92033048 826196434 57387992 439380970 352355005 729732998 693176581 347243919 790417321 891181409 994247666 855807358 107883917 257764855 427862860 425768925 721340278 444273109 619092600 755095188 366542699 632735974 213609393 862674097 109216219 230376379 352348557 442255391 443229391 654470860 247575827 211397068 312068286 718135312 896082066 195085243 888016281 293983474 518389683 355214020 641410688 286976402 940895013 782514630 784390377 996137895 93015078 407996792 957057770 440168865 533271712 445719171 97015165 51595597 560524528 822145663 923319403 316975513 105019772 31142290 872703611 995761430 655653341 260944374 673998321 323337988 171763743 722454385 633507634 424537784 254520613 943580167 396452842 714825177 846630586 593279456 705914743 624323553 941866478 124601640 288056199 927011561 548765615 408816227 175064821 218081372 428145267 115517264 347715490 440729532 306079112 695964795 461135175 984630719 41580763 471589936 364515053 774301258 437308507 627946010 138234328 555795912 153246585 23728360 131319322 88308987 691576691 579603715 723277407 120342306 647465324 448120459 128177527 331011032 60930248 289111347 348261360 749210731 959397657 878952949 224062143 216975754 326414673 124816951 787195802 254337520 685468763 252790012 328884519 145791358 782273400 884723225 406922511 608590565 50149194 40381381 441961112 670014567 925286877 109830715 858649262 720442453 558519290 612804828 951335272 127991121 983776664 176717208 565271477 316122772 83109850 245534315 839367299 768069009 802299499 421868074 960900030 309336538 427199781 452759106 441711181 924903265 874943121 529656177 673906227 872137704 146665845 647953176 134415808 261421434 664851384 892051371 705923756 271628017 709952002 278454362 552371478 917771677 237206135 309491547 751838794 781479580 308318148 847404017 24230772 962459013 849036783 903161454 893680129 846995072 271289452 425403473 468848273 732451023 517531184 284726926 542808201 128093955 432142160 124034247 398491201 547716114 818975314 304819298 181217835 17362714 633350891 913369630 256965794 374029393 882447035 833257495 861156479 687249307 329802583 993335442 766338973 872090733 185882771 164449641 222161002 216022357 348204084 382494928 980873791 474514039 327256207 483556280 97875294 99906751 144983499 62049492 93098854 387486769 90093204 51840304 788812073 916463048 920068375 34155508 288216111 749377139 522163650 261349716 588973382 739938754 740029505 227249907 262446532 343757361 752281449 497739062 283997214 179321628 708378689 185937196 210251730 782535462 188812037 366035178 439973436 233740064 844969292 199287193 519200285 538956434 240463617 175370758 35163070 455235974 435684007 138745382 930971647 330757783 461495765 258991506 465878394 200210563 86992158 237653022 524874466 373111836 737444357 669889212 688368568 729227533 373561607 550695447 681483340 295577055 698468166 699987219 421251134 529976956 502297603 362657570 455593810 150330733 526397342 850310982 107263635 121931003 464650008 564975718 88886438 536849834 693996119 836817441 848707332 618931626 335954081 939810584 454428859 775360052 655008718 681772238 675090459 263027456 915173030 496374462 368715984 588915648 237670448 94139434 918952731 116987797 848097259 290131760 421040283 27083670 904526750 672409867 272644824 461727976 230873769 892914948 483252634 306905632 474343723 167614112 159471722 953269020 780660054 668326128 740241210 189402892 680422325 21381118 241881162 60399645 933029542 675440504 168122785 177045201 878257976 162683562 491231257 700869742 531830510 125297020 564443618 57453282 212382671 96045205 565980185 602626036 66014598 123622709 956955062 613407001 784807349 241255733 80857453 739170209 133457426 559446092 472493055 578365325 852134652 824903425 247070565 830697243 485831104 161708780 291267467 472354954 988860216 681023573 278111494 403189996 496743225 857380940 868139175 58437200 186091200 502785940 484224394 787655747 409004688 954725204 308311620 297291504 684815784 911549490 37739516 217771414 173838373 87494922 6719862 883905098 100705504 55323871 334086325 991692704 545297452 520935764 554226217 748218449 133504247 176330237 365388995 566814870 850844610 789324675 123021721 822497707 395096589 285571445 971147832 856524501 886758993 923787008 953816550 420736848 505032946 473898636 763039647 900527426 991217784 872214134 571984059 347458049 233780608 610333173 70581187 941922948 523389755 864003026 726118796 973669759 246889949 822728606 290132607 287923551 406072806 98096991 173228650 423141662 544876206 806068049 619200307 27543786 331751304 842590324 853717925 942962543 747314459 383797649 453649998 690173717 449730247 764932481 682099371 895468564 386201836 646378138 272574276 931561019 810513411 468805001 576019298 726865654 273889969 12849608 648977245 68672885 723518933 22992717 387072711 570690235 176238706 628095254 762684143 322707116 492474173 192072100 656736000 289662761 105478628 916116664 213722541 312581769 825533714 131915068 715087065 544651851 873039487 205268894 771971992 169819501 781147682 100461267 756758995 500167326 964893820 560110043 292227122 982926184 813548479 978755854 677166255 967877772 850532505 860927616 181456062 83222671 163880079 775285282 868400915 783794510 167058185 174843966 384207330 54386207 293216201 269020655 804507531 199216313 981260176 102128016 238402856 68417741 792029096 951556690 505910502 54509068 449640536 168028863 478995172 208646037 163442828 935849648 884001323 638793506 206956005 635975930 707986675 574618880 853103624 363160352 81077413 698820676 634402766 319022549 622927908 261228307 956452396 340546788 650963617 158410273 943201795 631647001 458493392 36196152 159708493 362592581 507888898 565554755 863872826 509138604 168821567 989093726 510627977 524351632 977295946 697192057 239876041 261647262 15048487 505777027 388677618 358148534 142025010 400606869 446614397 966676015 577893000 132268718 468119032 106020596 207627766 248618131 564383363 214254058 869803005 987175729 316725594 448766318 440212438 190347618 541396175 765379567 868709719 889223659 211104332 453532238 731673667 987478565 372092101 405382647 758152716 320643557 481829689 149659185 197038418 423056305 871167250 315971565 799693832 23093301 36544811 304944330 928767439 813800255 26899996 741914874 566250503 66177787 905580282 598983681 662110888 451927694 292076147 574909924 132191324 165855001 726380292 905230412 886578399 889321713 208815615 748204216 210034353 999857715 583796435 109145363 559157889 388962720 779672745 398821985 238326560 662819781 691819722 431410592 913574747 905404606 848263356 633123591 876461771 211737234 579288039 607790961 665226462 981799998 142961468 290981754 961324653 257072453 410613508 916342054 88061163 740594825 190642706 27755496 349389084 673424402 13950285 773869130 334997014 64717880 334869529 879233592 884854996 170368979 58954316 486785354 382125809 979843634 159786941 305224899 857685660 513101369 465534258 800037221 732276683 2520239 748310427 760820282 945347086 442456112 604415248 404172016 351390712 97290808 472957844 765104426 675676926 64392175 363584684 244157433 639995297 66855122 999734944 258073065 322532855 877852410 361815796 689613540 562627597 811356396 116791668 558133191 909794758 109233669 432739249 954776463 598692977 16339590 63324377 170320628 396891966 111096544 167500787 392769189 940945211 909223075 983934986 221912961 244043150 624435635 13584590 605355392 597845558 816149048 880168689 712519636 585435110 354260095 832394993 863750675 435809687 483930099 304172676 518535953 260779457 195539092 645937085 211377303 719864741 833228091 767165819 762058164 87311512 457885620 726986755 890247512 16783839 346020780 816872142 513702572 198888669 731552895 515120079 137420792 979661722 690855834 333653373 380960923 965233457 667499566 576336070 842363013 634264403 896840831 63183251 869824918 491789717 317252790 645091690 501298995 973468615 486233584 519406954 476301323 448227796 990656648 924611385 132866998 794560172 806884722 652673906 319940690 105375389 136550604 454849175 947114081 197922478 549993858 363895291 739736479 202133094 410421990 458988527 694343854 990186018 19074363 892154762 463236263 566809104 383561646 402317327 192842688 121378619 101977141 403078085 516250962 976697715 936572440 704090137 300093162 425976406 545838376 475107535 826435552 708936108 222398870 273279729 725963011 39927132 863443561 726071625 768918448 427876687 11552736 679800317 690868633 398708748 442260552 77443615 692119517 972910026 110526189 80840362 412157917 117676039 460584009 251205033 153541064 905996000 5622446 751751872 580225916 961715953 145936642 185365121 665344937 261693538 722953079 393908005 29727208 493414316 690301626 851107908 379858500 895030027 903401709 539638853 754426815 196536981 274518597 407627878 42846025 629363278 603881735 604758554 525487284 654182131 651549159 356832979 374542340 715221510 203585377 940014638 149884071 275868585 573984402 916198809 358022122 694096576 436064266 79595314 309575172 940094272 157001107 995415402 997366710 367830273 800168610 245661425 611452724 8830295 983513854 926411457 718560235 510347016 186839886 190571514 279148595 773212820 13525710 442052145 374940352 475600556 905160619 286603262 271406061 24966419 881269070 975146016 696803769 907408930 373092699 78387211 626095327 879825602 893940350 264793613 1336687 456984313 167831498 268714572 779195964 801345307 538256017 281141045 162664677 929946017 722399764 440711735 86851078 153786519 86257982 438697544 618223053 771121197 692215005 306668771 333769196 19076589 246444079 361709517 492958990 820816801 347262327 486506998 730922072 922463705 316754504 630128955 930974982 100352805 469132305 120808788 166737761 23830659 394795396 662590550 473948124 415443507 355209239 125340567 510104561 429579001 893470400 510609117 457810863 261153561 422319559 885392569 342444195 360869606 546523389 837311982 809683408 277885208 833846430 144600652 849130499 625525274 935169082 325105251 864266698 429758118 852131022 973896737 754611691 713830258 47265440 587376146 687674578 469959994 385361957 669406445 87412711 978771932 887329196 645945474 147149439 213632276 739156782 711638633 191744916 909403092 172212216 547823153 556036388 89405953 342936621 155843647 108498077 161130708 174542824 118463402 23997500 900762501 493344244 142610734 251406727 900871797 808537808 824825252 631997019 438730300 93517139 840494897 385870539 58452586 252279520 43411656 369250742 830485221 583687193 45223689 781066087 498249846 357644378 937201528 56494568 993118121 486380518 610522565 142791841 467505950 180892126 823381538 965332369 580908370 618453336 920506635 52952539 625286015 156910239 353253291 347990274 957105052 912361305 559836889 357165943 135097252 816352311 892146683 613675233 872409634 954200791 585506036 263169993 520875445 731602616 748290849 881046960 859906480 829886902 454499908 307502146 86079670 850843130 359347784 929472050 464438751 327529438 561886294 717100736 439737518 702140300 924897142 995442770 261251690 974150881 217107368 648585496 68825162 534950786 439507374 63274531 643283726 83316143 573092287 273764280 671716159 470920711 50840881 235383448 424482764 178840494 767586956 332376612 91137723 51158354 146486075 239408494 119761250 80640161 347070272 529769847 711486974 518801525 299721101 120182510 107800975 711026169 931768359 196178819 65802032 873367317 998496703 754830311 949275478 959643769 497380667 954142411 698667524 540014036 129809524 434014225 919457471 185324871 580218126 748775944 993763581 284305143 612838673 998285930 888530351 351922775 638617981 689916240 617235266 95061056 254139361 594219151 238227300 507764647 235896252 866831415 853908455 890113795 185355497 235611171 430760343 479205812 835863677 783186386 798060359 584181521 241436028 230796146 479519547 565066970 190013277 271988017 945568488 762730963 94407834 971953970 647605547 487044296 138307978 374432946 584806247 269312386 960404987 304249290 735506561 925758171 890993152 433697046 930372193 43074852 63541584 262554867 346597686 399804054 635042012 946068066 664644572 651872055 83012302 812470009 658638032 648818707 295381232 786404639 408445316 188322875 934653632 856386047 674139311 744172027 523310052 459890521 636229755 657837124 814298148 97641206 234730089 963695751 808597245 600725681 895543870 259908937 808169694 496075319 840307969 228228810 737587543 276829228 563106948 923990026 425377615 206641477 83785657 864318090 651960706 588573598 404211960 157963380 422336640 492573601 970684219 452116583 303138432 376700896 677955470 298570281 190490511 895475012 252904308 30623869 937446337 296413117 208962658 692036739 472101156 605595405 968963293 449195765 29590065 157648240 907032530 255895314 218132475 943380219 981009244 735898678 861683311 451031426 904282447 761943406 635156862 950562049 833270816 765817834 683141979 745226139 43899802 503218460 161680268 680995700 87127161 833829090 851061525 644350008 561512492 983564037 33263184 448456731 664224271 522072101 747024877 439710722 292374170 249933805 153228970 644777789 453814169 792447696 864835689 856350668 52108369 520970744 598497540 408847987 167863843 697176280 996565660 541299983 161316105 173150812 959760044 643054400 18877319 321661893 586290795 282664535 479572539 723264287 133931333 722988997 523738195 372519369 832125501 396684593 579946184 992261621 405796429 543124492 324492038 527449852 65606307 985850417 732613753 890386903 426969405 271117845 534765341 262272274 138953503 697187766 658511002 410942451 818662280 151893126 904028782 598649484 402875174 47329648 669152124 492537758 694245752 511275573 456152294 531451680 339542234 126677423 928407241 116590926 990323850 366597967 377155795 448229468 763529013 350081312 890358297 739928946 215091635 926376276 245343706 946644114 477261504 201017400 191014075 751176197 240124108 931102995 613822362 229808814 107341473 758497542 815714850 907790358 892570312 586382747 352875032 714999439 606357380 855973109 959898456 683061017 101620518 153762136 480229542 821562241 650577687 319609192 698683494 209090741 521235385 49049018 499223236 311901958 291165934 880463044 163769808 313404018 643982790 190008385 922565419 505553317 293443367 301519467 987083114 422756842 520587678 387918017 594079604 372569680 331490658 824702167 727738142 879772782 66458283 870558515 831002197 492779615 821558010 249264932 893667155 463860040 127618119 61320694 161975171 223990662 667377929 104088599 117168851 533104885 626642614 605771975 914965193 868894627 345601029 141055238 589134779 127365647 297479388 154037569 70098848 338610456 128642438 148364699 809188477 650454285 242416220 85782104 472872438 108538500 557231971 357563590 139780843 673749132 993622002 556677452 460730243 309440989 145625485 943804552 464437824 854033981 455489169 506010670 302950635 959985955 179504072 842896216 977177059 728944663 837467530 929101252 489596450 764587866 964382288 274745734 102219866 926256074 426449837 823117494 983464547 783047777 407627211 195768857 772084625 606361821 524777234 848138854 549403063 85311596 480399417 302793919 248627971 336193758 564949778 742825739 389901467 746795594 240104578 531800801 402835514 422591939 717251475 410908493 471526357 350610748 657695516 607784011 967991288 874949645 757558764 171674073 172024661 833479702 715290321 259186328 618137961 50721827 714767111 111461920 863310844 65913570 356133325 357311955 115750451 870206338 758743256 568321087 899695224 210591872 815293000 111447466 779032555 950202406 402102106 775276805 252857178 368985761 509505513 294907637 927271079 715499639 911455833 858321267 662434921 569897518 716111308 355523378 126053744 952683755 745045917 268603603 422132994 592004217 55996432 556730439 809633816 627338731 338600708 222905234 248165308 117605935 706848538 636281769 529550296 625721200 979667612 554689321 509205031 86536694 757107501 173097681 963693262 608945353 800716114 214877772 411888749 512292828 726387733 255480314 959301948 877201885 501824752 672401743 570280339 817316875 620412766 569674610 281323678 521863687 12211673 809864608 38887938 54196217 408751830 541051486 315222054 947677793 234279606 773126220 944407856 890421560 428993566 958412350 345376604 377554711 464985240 766928860 685964410 79970544 238460288 962447170 496541030 135691439 88349812 219347712 948165334 103306243 825145833 343755181 959794855 982728340 515783173 960096736 630531127 654970972 30080445 189208919 37004971 99402796 437161036 9834262 956606 142042070 524803664 22447807 65313184 707442431 93809985 736827491 575278061 701226328 595973752 560070196 243411287 888027570 512229534 925168338 195179742 865693438 600617640 683704431 933532170 914370723 62709349 119070048 176921764 515554095 149050285 485663871 999492651 209218891 869600833 44031965 997001607 89729144 602225794 572167718 447666808 9395925 850269771 969727367 494407886 188841511 17145855 218312028 915842647 469957134 867517228 763277398 197738537 84016037 653828780 227283716 395306359 708456910 438513042 453755917 164982901 364865874 790209746 486212899 233353743 572255386 645552805 598173847 986947611 933112885 155765798 382401541 220778541 848128574 554769644 891460217 683543322 520906463 423909042 340848419 311748382 824152405 94580286 207903427 270068254 994914764 595496215 734697805 962384708 969211408 743172541 341207104 576491944 124034713 465940937 477263625 961458151 660552859 551533640 382536362 259925559 427518574 134719863 34997035 811088779 145693210 119896784 937562732 620168175 516929684 755527906 188504017 783938184 500996796 269518754 194430210 515073155 91923624 734765348 642645330 607033705 245663889 378825348 777310682 839880250 53737727 351769334 876964569 588416675 623410954 692117181 444858863 731802793 317631693 262698896 932868438 599788315 387030292 151415332 505582577 80733847 3045956 788319339 29900944 935186408 454353683 970883049 462065937 523731160 742342883 482891631 344988761 829114444 307648607 702308972 250634040 241138575 480081966 260327518 69038697 564769322 685038103 932782048 997808003 941585914 295817492 568010189 408431148 783033777 700231998 623917127 927903607 72169046 203279273 689661995 333801008 241030451 340581402 356723732 591515082 324388945 662594775 472269572 605399394 104044523 317036302 53379205 979971943 978139682 668706311 878350960 748122064 986759242 118458720 974759914 313748044 702524895 778711048 120383092 542888629 624647461 443909636 362613809 149001035 954482775 495456149 854293026 888947771 291240133 540599360 857392803 692278763 959533714 994699910 338091299 985109154 246424555 416759068 725724347 620882776 172333898 64622285 133804657 540991571 506781408 109156000 373020246 389897876 815824716 868351055 201156025 721226550 544552162 899897427 943312839 354455733 77933826 652249677 263646485 980389659 249017494 166058333 626604153 890198642 458208034 70044681 455019187 301267804 245013046 611446598 945124865 381686394 269565081 639131799 298543787 240951140 623572178 114679274 850241012 884583231 173521603 172752340 41644966 820420211 955090202 813684117 595251475 885692590 657707945 803872122 970446321 827780748 586770835 320965823 617125207 106357349 821123437 969036942 852251315 6614117 985918646 478139016 496795300 514386068 535836252 874140194 392522928 851255699 73951575 368920907 30310979 843030147 333554296 890006688 373254773 586072635 154694822 855273715 250259315 633068657 689504782 888307382 144556352 15201518 426524645 206038221 707351368 100109535 442554422 453832603 285074829 835952942 865245889 857300180 243408488 774699150 408322552 731808914 46033880 230499067 642594129 92349134 327265063 772222264 81404457 738245502 363811735 23556003 606857880 388649358 904609450 18446363 288526395 503923272 458098708 477855965 648780645 979530394 214256702 660705911 50495795 182223671 628185432 560204246 347779823 411815019 217546455 723452273 56538500 78543598 497895840 195216622 215742660 682707437 39251016 552896087 399952646 900104497 191446515 824944913 749700951 793180177 651983188 597803339 93428429 942305113 275005480 342735245 587466612 250453405 501428970 319800119 425430963 486478561 970935271 37325906 265744173 348104269 685733566 89557363 931279593 985857416 848474601 287983633 246877736 567665684 332101636 982554039 146571710 298378719 551350076 767820725 303999459 450550938 645330772 311227892 622359843 294547120 888820978 447672368 88933756 45149480 111488174 496694902 348342845 550967305 172748703 252857056 61769913 261959595 976573278 690611098 54358823 849020279 670098518 734017118 602236355 850929932 653230452 281952608 445475735 269439775 666869485 540161638 862013500 840080375 821285349 657187059 284003228 918784545 647328299 973483733 711907433 650300049 424478898 292707634 776997532 936692906 521450263 477029321 874250766 52159902 510857433 600909913 381127489 961951285 957001783 418468508 276058320 186237445 819235080 773089167 562164918 974470977 205875228 639469544 855354057 702526182 407435772 290887779 427545839 159236025 430168794 439948650 651775369 882940919 443121015 902668267 608692545 614925436 745735835 959253771 231006757 651568826 661110472 438115320 757710078 743802589 490735898 748750151 148574645 684911928 715499512 22074723 163146998 345780963 77857767 76235770 451992260 493190277 894336480 334671612 479234014 342277119 536536509 105973124 501613426 116464668 92026642 229017047 826003062 335114254 263800468 758000867 125968693 598829212 563729627 9669253 137991092 468792331 733085434 817781558 716572309 953364977 468672467 167865107 61148974 761367106 603011086 567470038 257164132 679966772 389665091 13093384 765666440 13545823 888206678 330903873 398756270 990895029 271838100 910072062 319122423 155877160 660780880 883090882 772611645 194498504 856524159 108990874 139909582 471987713 492527752 60035744 379961942 211779289 447694344 848507326 510748250 390594735 4884852 954388923 109180905 607016316 824268977 300541525 493647139 171934536 639704051 710639911 504870493 236513273 428715442 610244926 713006483 912195390 652498205 216700264 494039370 431667399 773181412 894131400 680355433 499279857 261741972 508436543 171035451 937268274 115664459 1569070 520654989 98530181 848008303 166424414 814049949 489532878 162065326 449015592 68315484 240217830 155331660 819961894 217974546 317895347 794134154 393758187 604783309 723617038 722108588 831387259 544606045 178947173 328832564 912852749 867205083 127149156 102586484 23548759 136998061 895450774 112371503 834000792 678829801 989890920 847543314 694288582 84899821 510960962 863552411 964908001 305232242 550838399 527821944 997780598