5000 453
560022656 441227740 446681920 779044770 988702903 682575863 501025823 261797676 228534528 382874004 338832733 646007594 759844247 232685226 439634976 680302409 382349361 592771892 444559367 438389214 458968570 182984486 453903522 164620678 32108532 95756329 250968738 320265516 123883834 823793231 202991120 155158764 450842634 129276898 44265608 747560079 401598518 293466231 602226694 437174018 435046693 251506816 255310801 680747281 914335553 381315640 736289570 89250537 134231625 648138288 494961133 675653344 917608429 336507589 322458123 7915390 867194331 696270259 681576059 245298401 359678690 855711684 214781999 668403464 865323189 928871561 743790709 360543875 147545548 849044627 400314676 802156996 117433248 128774200 973350749 773062411 601826841 564342404 977075887 292468995 810105017 581191190 663578801 533874333 824981715 518361007 296971476 153182509 364962250 368206044 432430470 429478607 803429693 165759003 738259568 981806148 596794380 219233292 114289481 794089085 840040937 690205490 172983195 147734220 158433259 320599590 202431107 88708914 664507712 797697420 550387243 302175423 425309142 163288346 954697867 836227067 388408038 532311520 2360075 242947717 446007872 678588313 502648363 767326280 140435211 755417413 408527379 794263470 285554783 448141338 919462932 291008266 138515579 424688625 516001069 41966821 382963372 802450761 378250667 507814139 623444687 362041885 66217860 926565349 646869522 68767860 624009343 186237165 636134589 155697431 847105163 374523909 696889847 663004573 700920505 68990238 606363311 311437043 715137320 389012518 837328230 198042112 367402396 365716934 533549164 30001396 530214158 826809995 298662522 313548524 189074669 50183008 316031229 733553782 427662740 330973251 200502457 579818548 622983124 747318734 592144211 544865499 133881696 595117883 693141321 248465624 761222089 942032626 941211530 208288212 296451372 746386574 503015747 448112951 745761638 602729632 69494131 187493043 823667915 966013135 578073596 945916074 140198840 847639694 438240122 534325824 756834866 43333195 992974403 180302923 208591214 728782386 46001788 705438533 334117259 15791156 654219082 453330818 731611859 544980755 919883267 666006220 433561033 672671091 740798389 384262711 998814625 336303947 125362970 566094195 489920551 940735322 611937975 910088701 428376150 2833713 43249916 887680352 295116235 760028202 979887082 531610005 655281179 693076827 900839436 425317271 184694078 588520203 846361452 983524275 416853913 269357287 641437526 936937654 346629823 830434882 176202856 13682406 894555692 200490940 173636481 776639776 147269188 119092482 346793084 89778725 885067891 990942359 510140929 228945094 918762522 504199193 268973435 773659591 419062411 236434158 489121216 243082148 11973160 54900249 103626953 454240799 10194540 327710367 314252291 747371062 338182955 222414031 164383048 987337567 22295790 931941138 612851517 70527345 237626335 210304815 779873689 294831703 760894772 941028014 148268585 19918544 455054529 158383797 831829712 704048248 750086088 413759763 83532535 766686787 663240499 297900307 579084946 87236763 281834980 674484131 782379873 715975412 52773554 356023199 761742157 950634681 442034584 426812402 731701911 658894020 43816991 827341270 75906184 120390301 664059834 834180562 695212657 848952615 811551714 51155046 419466381 290314398 310096403 104233861 498017150 268530956 624356945 99299338 567198673 957314323 49138788 942842642 618176033 914556540 972579533 252588599 829549059 161377672 951710004 249694106 778545436 182966095 893095106 522966216 529513956 24837940 688059913 987142760 98500986 814306058 298075850 927144895 689324921 250288674 289976238 230424458 520695571 281479940 11046127 719075595 343226651 85232082 555983386 263174437 353114195 420786774 260676782 39062791 174572721 499243290 230389133 623541060 11213273 171768466 466036316 840154114 870695541 499727982 184173388 665929052 440553592 630696312 733530781 11864369 885066616 620862980 971383095 570411455 570036949 965723390 212316076 400199457 973864110 557746784 916215778 811310807 537709613 313760102 770411794 8287605 624326532 913534654 949722152 826917227 342743576 407436504 501017852 766473754 49318620 679256268 245919090 341266697 660002057 248669549 378347378 813181861 718745664 962048592 493611773 381517590 563263796 673447827 745387872 725641565 679745876 589020916 838196620 463665391 138997050 849624706 714106332 792749607 591911250 154217516 953125273 561790409 269582625 344571427 631831311 870291613 484094112 343924404 3337120 662112759 611277306 641916428 830891217 444899032 786900784 360321020 584164749 940481534 272915127 851276065 242300906 641965601 25055446 998382997 282045076 571431079 400630036 786553745 297254177 402037432 566006672 625559649 412637258 215776343 603592375 794574187 768226475 108900086 697208915 330859808 855114507 757390222 611613771 480730152 627944924 420122986 660500908 613483279 685245450 938597982 717726274 718773835 386534868 908312086 791083985 405851139 226173121 925371981 460442709 949371057 814133001 113630642 211831913 29612865 328693599 567627999 596847664 13516633 256356048 636546344 652579494 846397921 198919876 745476185 270754466 812778115 483710667 639259227 14733649 155736868 151315003 345392674 163842354 585727470 355501008 213995044 658412113 471966949 278564430 919947348 436174050 468581264 179823033 254050635 209011845 802622116 901375879 168974505 770401541 875377921 384507730 943300385 121020824 389933994 365760632 997811801 714344179 780987329 959302469 259331746 381110581 161577479 225345668 727083281 75705633 762964635 400377830 721559597 628285225 310532757 829184866 923358580 742785389 542067157 644036508 269926770 891000703 746356526 566854781 619058613 952711000 850673089 391910901 804002904 691855034 782503526 837212620 786507723 6190851 201964772 705969606 7657207 943314962 580833843 620586747 630667186 705571005 467187735 248167454 157427842 293765132 973434037 903983152 665411531 859752952 497085308 181970645 194327074 470664949 489682134 618672349 980288853 699230442 888914966 865267170 743093295 905692101 636392843 911544182 494811310 844253358 929942862 7609205 501165311 939873106 244585534 573697577 24267352 61290694 294833184 55283037 859867733 142730417 129546852 470328653 926634188 515913286 584863588 245903549 583812926 131266986 400024255 76803971 72847082 153147238 263116143 858517155 149681897 93974828 280114008 291175135 867745426 706536402 659268819 9356002 491904603 397128540 306462073 985693156 37001737 749080010 624532039 963724361 587310738 102092628 635792054 524395505 564844807 137842623 674564673 900989575 553216477 585047944 195521323 710344552 188050472 626615956 880673347 970712599 281577668 130970728 367870494 67020847 626201882 261710426 701447290 808760197 270905716 480562360 441802071 566344835 348704402 193854079 115832579 640510712 781951764 900708810 354028004 990669793 978944271 572583313 121964137 297121581 74385302 761173080 254211841 399968903 722362053 308226423 659537161 491851865 530061620 415396305 799447085 572741349 221155588 876499403 478181660 926732744 257474439 606113148 443549685 131924793 898134829 370957437 42345787 377445674 742875463 803599175 183854833 662163299 177625340 115132369 867052431 65913877 735844296 218536101 804120959 953600668 116479066 883380157 227879265 625017213 18380546 241791143 502538653 864840537 929611018 817248516 753106106 451167244 883931279 391859239 825232807 376664795 41508898 16404219 944031623 644741752 286795204 658205068 128084118 473086679 699036026 602025820 982150353 663938732 807054153 214496756 79766608 563900691 262824310 8888697 870229618 817814170 846867362 54653219 420024841 338160382 752483555 28543621 436302577 465052834 166892712 491142369 408657397 567787980 897990021 471975584 680194978 150772122 636322188 89371225 773310414 155820819 545756712 339483056 67860957 658264884 835548876 314103289 931758209 431340987 512262528 416357068 345542855 93707378 468426224 267719517 689586288 458502965 436967662 192706558 664292176 926257102 656192229 82715784 591998040 228963541 866765747 503478806 384758059 26546380 62525789 150658791 479975621 954587681 967088924 367730844 233666937 560701762 994672964 571313555 692516092 281584387 44469947 911660113 621998032 902855323 924780885 277107598 653914996 862455908 282486457 289387226 41597330 808088034 510636327 618707702 214376646 546112574 79750407 161592331 915175031 986399282 999250481 6323961 233408987 918312432 284133298 596999885 413853379 124606452 375728738 151832885 472658554 619095811 965483943 603272054 979805984 921312260 511570914 289021490 760523247 522322115 892105669 975899683 852361778 642767703 86142330 432212405 32780032 426204449 280294313 465674947 975115400 606868588 958211061 182751326 189858005 83871983 442376939 986120283 195017976 183306200 4106066 493824147 233418774 289128500 573992418 908919135 88515528 955299361 956992734 953408217 785408441 997086174 469599791 94119478 919891706 469369210 160426056 870190089 67398260 974797876 149569891 670958183 409507875 12313904 972094238 853606015 848441699 282914211 731796448 156900571 18807040 247849257 145644467 827584241 268695168 248656498 561310203 833987848 61920305 677146736 423647000 754395684 73161684 737243858 927261812 39831956 864328802 730629639 358357662 462444832 313671868 229037489 361026173 175707834 131522032 907658400 319167313 735610315 750223935 698077349 117198163 149640985 268982676 115522554 317983074 413050766 847285839 13738795 260485096 946183156 316575887 336605273 387387334 500548850 318895554 809877100 244246618 47668421 342699318 649473228 119894835 351979575 834499524 628014651 977423112 19033073 13108034 655137952 79718284 448127527 597806271 921834952 613648973 30057489 835118507 580685871 156186714 123678266 591914519 435740758 653591923 990418582 23552982 320428273 80795286 786246018 68943469 550695162 904462606 563519292 193743193 525326017 562006623 23237440 234106436 525712640 590146989 836788988 264286045 945014529 932378408 689059182 963601045 464436061 891202515 399459682 776023739 115595021 166716336 195273652 206298039 166669347 343383751 150372440 182488125 565664937 150866323 344722207 181947821 674973675 830561002 294986449 946842814 252988902 190972430 840990793 283476308 189484114 65130544 892698253 782323641 154666475 261808120 865062031 432547250 368233053 172158228 49245616 402007284 402384409 205748868 170741626 324874113 595795453 386837039 53239858 637972850 452187509 138737355 383614708 870365658 279391410 164135446 343731471 320555446 152227002 206043123 758463665 396121669 309727958 404296855 861075907 750996379 596820905 473704053 810906687 66869543 665337388 494211517 966986701 964309925 157547523 694895989 932649061 971596850 106332169 552209969 852049236 576258146 489992275 630027200 522080339 227350943 219345943 405795906 561763361 889211429 902181482 851190266 959251448 189675364 585116453 342458680 334322364 86120766 372096107 730368259 120075408 216538226 704523842 710302858 624300502 26676544 120365593 692631016 592105220 358389793 237170234 908105845 929940075 741989871 198655867 955858370 443532073 886305497 232973200 97700547 2513428 988798533 751078131 583904513 962826764 640054669 173357710 876977819 239190037 880429383 490630626 460641889 262850773 878306869 32357874 971618299 547866653 144381614 400786615 346248126 492515140 899675980 403046907 319244105 353813967 797550248 774376384 895318455 741773804 958422457 555028218 997335257 233220630 613444401 935727028 607428083 769847014 179458064 110582673 768213753 522925415 319827742 762278758 359331709 772118254 24978413 681942092 778225560 313503444 552634499 264719111 525005014 222759876 845751690 55468250 593644508 680465695 374186821 23500040 619863994 339799494 124377048 471985511 964427999 193408622 550635721 880991704 606708201 380624645 997245500 313282843 682789102 502065461 11823488 725807937 966927973 921998152 396673488 559587024 783284521 903839122 468391598 805811893 36454444 885010236 313494202 333855061 642694833 81925956 369005343 109730587 121977682 597186044 866524337 969205844 419523348 108562279 79415152 411223029 247095737 929067425 409433095 391945473 541675306 378350761 741203676 470523372 474049264 260700552 949105728 172543005 593947805 418261095 212071651 277811896 141081608 23517220 936302607 841025183 879139749 409148498 994108658 61448225 591025409 762301242 871423817 990516436 658593518 730284444 570100055 821727764 775074705 846345684 443458816 933388458 154559845 777180688 5594073 737792760 567356489 572885416 801978624 21405958 782168066 617118106 10652344 43946303 43640405 431718297 783114961 766638306 88707998 210361070 772839582 640241518 370411315 295324351 260900733 110009860 499214166 347931578 251793315 985472332 464762896 829976120 109442719 687739998 351719301 547986248 86131914 132618191 980815734 272217262 692898823 873300839 746372207 644732587 526907915 181006209 336578923 600762081 977852821 136055376 682552499 662733887 608252187 587164388 321143566 229332794 483776029 990656228 48692733 197757318 348859706 932743247 473883889 836458626 206130547 742811813 623230653 541435237 997470060 902725093 167055899 123781760 812526883 29276950 100941466 90232932 258888335 944311620 273979977 351208275 161034320 272614095 311053405 217212858 949512111 532227013 373295387 468164836 787637551 360074378 127728038 440321512 454480519 263926313 710391366 430159655 429918414 431138934 315024749 393356546 35123170 77706303 389780979 317451921 457259225 204741876 517146124 248858868 605570847 184640412 330804477 68982416 798531075 451042706 652567656 438930397 906536956 91947428 820807209 272588910 600002491 799178183 734179205 817636203 747660044 828957834 757801021 935863912 570656574 936439219 259291268 719760320 618433854 377120056 897058074 817555060 914684296 454279809 923631121 964213430 474562047 233147557 743520492 971441750 734774175 170035517 472452964 750087542 919860163 47301401 352991965 315002846 447937810 217819283 256255078 639367838 321559719 616750210 270108732 80710730 917405056 522931756 685612235 388664816 21700326 396597620 721530624 251728022 595201688 716802450 996025403 391463706 260413281 81474996 246097463 868943428 733780756 189560076 554072497 212813777 990501401 924700444 428197684 488892350 148387916 182973887 940569804 756304710 344911129 170436946 791463137 861914918 226151602 925920742 1286582 238494984 168686898 593907195 375226201 424846159 191221795 179106808 837418727 500165692 593989865 870046678 243000178 702320373 708863138 296198397 248016252 862780652 69055587 684787586 947396140 946035434 383550463 313728300 908356828 590196575 403078138 11806629 444560956 194369593 85530080 693910261 869027227 910733714 257036092 54130033 383022203 445896065 936359162 765837528 227908870 341191796 399196921 922711808 837779917 882337910 563196359 341267567 108748762 112672957 992915732 893419014 888878468 310179424 268893939 159381001 932820532 967346450 112297665 462774572 392495402 314361396 616087203 550469338 99047014 288591304 745235336 326176619 764902565 830426651 720573015 321533729 823953836 32007127 721052979 599833103 535962918 980895351 562988460 600363598 595617958 554054456 848614398 303617919 55777055 16662153 310715059 283287661 790863825 297496297 792215166 87189686 444250298 753790012 658249987 290737910 225998406 513047235 804715159 608325426 15971231 305910022 723986601 124550645 398686374 656826843 500666359 469576567 598135080 760340504 668839585 779654129 40351128 790734776 337490028 151744515 861340330 308266233 771278125 415648821 464047541 364264772 436385096 840195529 109349897 347070398 95495641 104945729 64353255 554373668 231899175 785341565 650913743 346022428 877319917 406509355 51436950 837850241 850626956 931859415 51858920 105861545 547692945 546621276 450594632 801188552 590782410 948044836 897033221 10875462 264063206 941100566 771025232 568197255 907703642 525718808 482885085 742594416 412931564 898089244 388421587 375059127 785968241 598164582 828395912 83465017 457036931 95739133 120528060 426590496 179234618 277436795 112420631 168362911 752408081 925359233 963042334 68406307 636552157 872322819 357214916 704300320 574915163 236313979 141076311 385302716 330010717 162385784 571369066 882101659 119193685 996279996 134977845 749147267 313608832 991171837 388653787 787869166 266399802 32478721 752210119 90888166 219702936 950643013 905764327 259504256 798535607 693467406 559311788 215179305 461269536 770133906 69928657 209027826 177772326 949373953 307756340 141460221 982807897 508236128 263968888 937862477 520732845 180393918 412461080 254068022 632978809 611214387 741393954 208870825 506847309 964093013 147463262 885521716 582116919 50048367 990997621 134922014 39115356 725099134 741536899 435223317 783486955 711294196 305641341 634110335 276236199 755252244 97617747 502392637 369828364 169517288 911002700 465332656 256390816 794211571 680686410 754543980 999051107 765313776 44923948 906484259 750470972 256399416 834240797 581100820 272098274 348393303 862638536 846630463 648542149 272975986 796655545 769339395 488534770 128125484 433294458 363903672 902041144 573354265 904523640 618643264 422516009 27322740 302779834 112844491 698111511 579673360 635914560 273150081 245733634 346810076 442523828 398332015 993653470 901497166 561803957 54874643 836669331 248538168 145101936 99186292 53423318 43690714 88558587 170267730 560816582 539469525 569641964 694637713 939409199 738950770 640514505 841913330 871746285 527873578 517200687 593727506 968135377 78211254 187878320 8508968 682372607 927193061 571098611 287525926 140843081 883930494 463265274 433920977 385570444 178577141 496783153 281378473 125514206 738194515 724011051 283325500 873543730 170882872 56856749 908816177 198432911 490522423 743119204 113787148 616887016 946772592 988839199 897709785 737479449 236325113 230894516 771998587 434499824 536533948 863230554 690853931 750033602 790379611 489186759 950445005 148989184 686890057 260276087 366952749 972802747 767909805 493182783 381431556 837890327 808914483 282205267 648839636 59720945 896464590 168503548 305078169 15112388 230859586 517175345 568273707 225392210 977151202 675307742 43923344 482294511 220648822 751555326 991495035 144053671 819483523 173887982 305035037 37119712 787684914 783745453 459215405 95991536 465233621 557400361 451002829 923337816 664312044 831715310 43932898 675567319 294508292 434491604 175494962 21917228 220709627 630274278 281804082 682263279 817449392 923702769 534223847 984402648 13731991 583928374 911592366 104174610 863868049 2755239 588793817 215991672 504252245 272412388 554461620 106262065 245303095 623828400 62030253 95768886 302636421 962405074 385261338 98484017 468614690 805983961 994900471 22471858 384916323 317753332 866347528 282272726 672508287 698091118 984954185 98693151 505288236 955820696 956419761 348348141 596843366 57472397 581601739 258331179 336038313 842388263 873361011 143762985 55665928 866809930 554178841 38005147 442612651 598303785 192334074 875057107 361801497 830665020 363244190 502951891 635584278 173003088 632501347 780997488 25618031 710478779 283794625 334621748 784491831 896721627 689495892 842832440 494595189 937790538 645224832 237563508 475983040 823573499 584319511 856116090 376826677 543644973 631724354 110863283 716800411 494394249 486161979 431184801 313627577 751762619 203859287 329563728 497164108 301255221 768614275 8280729 151382036 160529225 550148977 334573534 72345680 689162161 424131125 949954800 670320726 267223469 457284928 510429699 663341278 32149623 121284879 279091980 374605957 134463760 312030021 459133460 499201138 349812574 749272563 311084696 815601945 405133306 699640520 89340642 938909521 81241788 249062406 518331078 683967713 234436896 981242056 309171299 897076843 12495241 394891214 125118027 453046677 196513868 352605008 179744202 768789877 142291703 329410491 689820280 82732997 933012599 260525478 391016898 441537950 457374826 750229185 870783022 268947792 947057474 85641142 741489152 527288574 625063183 362042239 246369005 76687463 45242079 421240361 590642370 160050554 552533248 648395455 905682613 222018794 285506895 829714256 518303654 231853038 672217004 661898635 986633617 280083798 951486765 807065222 188980312 105505552 680220713 470680599 258490579 836430788 894506146 216210667 364591761 48226400 362068499 918505558 803137984 677428932 206022676 866195818 186192605 496657279 734201225 924339532 27108375 775591987 195284948 561845008 678987737 957830528 50397272 807764765 321562557 453995986 135865322 479669440 485756189 672161790 619126427 55342866 54750499 666178330 826330778 49641584 788302497 789790638 938340429 990504012 319622209 51677458 377423524 801537997 978384000 665086439 96519613 478949531 321427964 487872719 387408981 485628464 928367160 934137184 810994653 200406507 304896128 20904055 184687566 25454091 327683049 723081492 775124265 774831695 396279312 516013006 64773486 912372960 425276634 266972432 456866041 819847603 55183078 625838817 469978840 586386590 550291225 106094696 300960784 609992683 492178851 278067394 640174582 143212704 455179767 585549125 483034981 325279636 484377059 913099169 434478458 157821780 982394249 342140914 30451423 468685821 513917492 639978215 922462482 480462198 55327445 338726887 334594510 683405809 242033162 731431794 219331150 534851518 694869483 1453264 201604238 766196150 620473344 854051797 786820275 662424972 137166590 349567022 791674954 908265944 910415339 99853220 259565917 187302587 429734242 763911441 605175265 491183522 313809902 149454516 427189142 948462957 929090780 612614335 599607301 455887599 412564076 989753773 206206166 798194710 787904359 968906260 44822283 97633829 258731550 53253003 952710880 809242930 823611952 120389727 579338148 170083506 9259876 175618430 350601943 754090706 141833082 515792641 716808392 505000121 132889946 335472737 645046901 224607214 695403884 230535340 750217454 290895900 378846490 300410649 434869182 222871520 420191274 204618188 240057456 13394836 172611824 273717758 240192724 975778215 923087709 778876794 732748936 186072699 406981054 883600789 78589371 225385702 444715389 381888698 999017427 621802797 996363530 557771067 86662286 946780225 237226158 442455850 180264884 593291329 660444029 204361950 823791604 101323134 952703031 578548774 77179475 579851662 604020724 831637860 848806251 814706884 850132247 931705975 464167799 21312625 466720490 720520995 62007997 365726130 20430524 452600091 152071811 873514150 209037155 705554719 608257674 383818602 697032243 85237744 735950357 529176994 856353232 77535874 184312431 927176464 983272386 482970264 443154934 506365287 283497854 981577002 76814524 823685640 971679512 341823194 238918409 504692441 70983270 221535968 643808952 541813080 47303518 798762451 835175901 378231513 744911368 985170412 640676570 260084859 821836087 636983930 666484631 787384676 52336252 415422252 9705442 144546032 662819793 317333779 386546869 641107638 263089235 469314591 307991155 472123249 696944998 906556237 792895929 919142201 69639109 124455642 325640932 501079478 93396703 420144663 101772699 246176656 547537347 519132572 540748216 695089670 516227178 631399257 464188881 224168534 424824420 935994717 234495476 157110414 963721508 711242681 457499857 297764967 879358264 396229814 358850408 240860767 355639906 27252891 516144767 586444934 663060190 368542496 914354183 111963749 461014105 402394489 539677958 194354351 78840932 715011051 952583374 107329073 862172404 40427167 323898933 314029799 469723819 145395424 889589880 613279174 73763142 597614285 834036431 344245180 172385171 714369159 206161231 585312601 385624917 791635211 722937299 925284490 563147864 309377492 308268096 741394336 480912867 927832735 551936816 122574862 949360466 346782423 258160070 338795693 777514060 738085398 914438976 938477078 625874633 622070600 13559111 44653734 611972989 440518221 730345906 253919544 501615792 470844042 643189402 163203636 485015672 919278989 66804040 386798717 750639983 144262131 567300539 515590612 973665893 436373649 624300230 943816233 307024989 546262275 860138432 385850265 56329914 792021534 637587048 402673322 656561609 535642906 705035194 779767039 239194465 788170138 286190985 281573760 697536146 997867639 569294871 60803945 768696081 357428386 664483887 342304577 363783505 921876636 910480577 236970940 934299101 15660092 575760604 35744555 949158088 696461505 681819117 538097805 390980724 529457000 270583825 878580418 975875993 243096611 225730830 705910970 177487086 734421444 311067023 573555407 637092001 259502400 586076969 657683472 834084652 843607362 596378828 698593436 684232538 647940614 497468402 93224281 442739004 231880736 237781564 503464222 887227810 508255800 578822394 69042793 424946337 190368800 654737517 246498009 258020872 509430143 590405082 223171051 460725421 557623260 877542176 445352733 424182312 3097337 246330724 77624200 648711172 428854596 133912947 620259926 13149684 759433444 93355126 78873471 368984538 477153018 492046547 833017744 686126132 114467986 165915349 242931878 686659530 52315137 62148016 198149356 298741635 571971504 805982028 896863134 972192053 608467775 622722076 148027405 388052813 411312786 489894015 155108152 937059764 814621249 165350333 380845001 735238180 764220513 802356452 801136799 542692545 384800789 579345526 343876064 699428399 487242401 179217902 38182309 348519188 675084936 317302674 745301016 353434371 289522074 353449929 381242372 607823444 433338665 787740762 460413890 341767217 551979245 241855677 95490839 228223249 703892109 503922785 12814197 514378300 333723472 47561994 943864590 138800668 748695708 268162340 927075254 989632442 200737538 539287339 45513609 659614702 437682966 435834928 575953414 685328784 609972151 465968728 557851159 925274507 813968348 657751690 826897282 197192285 225457719 869094718 799792091 718409585 236256229 642572361 721578364 118636449 406665678 389421629 285603394 130864128 250946977 531148861 756287220 123994062 223532962 202206124 897842950 815619941 885891622 911292157 550161004 90350111 828974979 792545793 528831301 767826537 162004197 765056354 403047884 352666456 151284735 565921765 337102732 966966461 365568357 940031704 968977787 96983604 724469694 762188422 683406021 24082507 602144680 666961702 770266485 135673545 483722091 31882578 676263202 666483711 302607735 304883204 114564233 514482511 482207972 816947058 865109756 224233527 495987397 188352444 340104149 566426267 409385328 24489839 725743947 453297536 754046415 633961116 552222115 709973862 674912211 981541665 210290312 540977737 520467506 237900869 590931182 862470155 99339458 767199885 752983130 138372855 77483609 691474858 859277111 729151778 287046652 241844361 586792382 922093753 483252781 313679612 5226469 135171255 506434200 372353641 511764181 345310390 139099570 26703770 909656615 222612713 36377357 44438038 136658443 189464516 851921642 77956522 912960491 239052977 471378044 103369939 572334297 729745098 868741488 154105781 664151798 177901132 637788801 164665037 235498335 891350887 286579179 68956806 562203745 328669630 697716196 50618439 709899496 677772961 538172671 314290235 404873297 386025693 344490473 808042343 568783303 777972687 459853076 639270403 573892851 384577164 443594713 352973203 459795521 822692194 724787681 428124405 324825519 124751581 808718759 728755466 144024550 274587992 311632608 369978846 488016487 506180291 123353800 712039984 198938189 75473500 286500205 710165702 464506637 494146875 446330502 746347832 886851584 788075167 421075228 300484047 406851991 931243794 58009944 176017680 95920504 259870266 543262390 187603912 431113255 766432170 454779858 310136651 958470430 59033999 828394138 65680120 199423884 882834202 136965653 628208417 720842872 611483666 922157505 97845412 848367788 184147700 704327862 583775143 387636902 581851211 910875767 128762485 181155960 136687134 658255283 700836701 410192732 482169167 769258744 526042152 432825898 474299295 805959847 300770169 619792161 467442067 501636541 730399216 594148337 502754767 943556940 41177457 677361281 442184460 379376960 872680877 150476345 717619319 934247955 632977376 500607909 329605619 75493266 693152521 619422856 944888835 731910708 480881504 23207064 908782169 33455024 438124397 982392432 752729582 790352638 167284102 570888242 823522221 832796272 366930962 43642678 72070430 487574373 349748159 97626925 412731456 319736690 544750574 310819610 226804304 2967643 415564241 698869745 737506425 580592159 327378270 718754226 717650809 252916277 208877387 922161856 156129784 1768476 263109363 365742220 654248248 216484169 241999575 366297963 77155647 689580287 732416189 862616676 307630792 668370814 947249062 495899895 977993478 476451007 698015901 683953808 572629961 281120915 131484817 349482713 47493810 477299778 511363720 84716401 603416359 634686766 813838875 748420598 397143024 295366324 885072711 597392078 803921690 207451025 537492298 903144291 66824518 190947473 304757493 226372426 308212190 82293412 943629108 186119634 621034613 858607254 542001021 249716328 613653583 959490058 168533318 703219225 463787720 402770067 676270519 305836462 465605169 330832961 690673275 383895159 995433087 845924396 254942621 280874731 65550171 65330637 652132629 772130959 149811598 273302420 36515377 146479602 547199423 624549444 872376172 945219269 201626099 670059437 3148510 282691045 818115347 657680585 705324929 571403246 300717756 363413254 94815546 918771795 91104548 178938483 415995527 474408063 633910889 165488564 802689380 740944927 218488 553860110 277246881 650023953 668845132 217406986 492723565 401867171 386352926 398093452 121043987 921531210 533751775 335607946 592665301 54555993 323694140 220464000 574897434 937427026 298318997 417317998 181094747 655549194 506494167 130180521 795733908 317222251 623914306 332064717 605261848 661814211 699351911 24409139 493566585 274439860 615342118 904250610 479236944 386543641 482648300 705059884 628633936 731845711 545738548 323888619 983713206 572959245 717055428 820979768 851331732 534544027 740909045 504622066 289974855 679917680 606759035 885369421 309966923 320297467 545450483 740467526 161676795 474787139 933580500 791891919 427537070 565845348 330666456 133857796 307724462 509227611 774987040 129902355 69185690 283735241 319350350 624926794 77547824 957127402 250511491 522946888 130030851 663531471 540681249 197148049 689555810 30462253 993215727 255853873 383653168 178265854 603422368 761216773 135877577 626858669 940326918 329815902 756217299 694796305 277685999 573777209 577019720 713237375 526062832 898726473 784495358 389138021 133451281 853094003 881559639 740153724 908725211 727796650 565512041 420376707 745582597 806608312 532666217 569271921 864321674 707628986 89107601 10436078 58747921 447997254 721058933 723663145 704222682 816538230 982718430 267332421 584824131 250246036 564195165 427082368 127134650 193446548 784713707 958438076 627506094 737873560 540086631 334597976 292381133 791347888 761278048 952498341 69625411 632542700 95143733 613565504 492876176 204037791 343542793 194941079 942147336 959859882 204498610 768264789 534021164 888628230 475747620 742455312 46249590 167889865 523595744 536138344 393093977 553975885 968166890 968539228 101360586 441130242 899794508 825331624 774921327 386642088 480849577 153052203 123308 804388466 95769122 268467560 980903296 894235744 924497978 14235823 581832939 915078566 679650255 478326935 192140754 33416829 876660735 689520387 948512998 391482228 609310358 512701500 264666859 828104587 116565621 886572291 508188394 514082118 884252177 525725472 87381349 194142298 798223523 660288936 866167423 374614244 835136000 681814910 557365908 765135506 280164393 209449303 585790080 800609549 847010169 857847086 2865600 484580598 627995348 279770115 581823804 436363500 103996512 956723656 132538876 687552134 669459238 285230150 758267496 548202146 723107746 285354998 94213502 402603470 906646007 108327631 194430523 300487173 838938478 83344222 7804926 985162539 891438170 608525676 165356150 820459233 136607968 202358988 768401654 427797075 156237903 820855961 818988744 467753997 560836730 625170965 743562326 827156288 444597205 277283742 719529364 417668796 543448809 343515725 605731257 52601052 527134774 325414669 446859040 346567546 81314243 947947206 977289422 527337508 549752530 838552172 196497907 94483970 674544611 976022498 458066456 759777437 27311234 966050354 170122248 148388466 206434975 405570529 405964732 267270427 742974005 4706893 90673606 738845018 238223481 206547584 875492021 725360035 813463722 345997231 12012457 992702921 608198717 437498624 789236746 993215113 926089802 1180920 65828567 328086936 266945900 824390373 592035368 229555319 64959884 506424137 102492245 316608167 427937595 255263516 635564944 533977137 7250854 625551459 628174023 974231978 151304500 39855822 982947849 268954492 949747625 835273755 397393131 581244805 219538340 308083077 277687982 524062981 910600112 787042971 379696254 512606778 834159433 459059687 338949130 582376123 171413157 983956409 472391719 283236655 522644128 841879644 106890052 325498120 764095525 10228892 141181007 42587574 837438283 967222673 676095243 620058934 285848441 70962915 356510829 46012135 904942346 686315457 720198352 176813982 157345825 84368754 257584657 215903680 808345147 647914832 113665768 51740690 887556124 158643124 259948106 840803540 44602745 419729005 737332554 314963827 935494697 304744459 67452653 213746652 738150287 542623519 399433631 252983092 790180486 484709991 83363972 58964573 425482717 268371073 760445031 857465026 682658772 240889685 450536471 267585050 324983882 345559225 932906616 623710438 324845436 274689845 30464139 904771305 454189926 104456310 525739098 418519210 175029465 534308809 846656832 262059178 297097149 522816497 105797572 665803779 717467723 573221075 358563144 551408573 270948939 497277708 267415452 393519353 292871276 823703159 130740435 104571487 696434724 540292504 831849679 977587071 415594252 182696367 191083109 106202523 564937603 114265236 506521304 327113420 58958623 332282974 149468923 316069398 848658948 270238585 894346746 384642374 594918043 628722615 612465287 72874829 690788993 987873580 283560069 661766665 788487720 553051943 189627304 627751265 31197506 205030395 582567973 303473614 713714874 155459550 991341555 988459674 637707574 173211792 45945705 609446738 73747744 427006985 335069742 187765540 739532954 627682855 428182156 65671896 685233410 21403993 839531568 169632856 500952156 775338318 661581844 84166495 408621912 384160918 896976040 79078080 869774803 969434212 707306214 250091075 406476284 883825511 901997892 905070329 808299998 290819720 391331066 954575317 591895690 120528718 154548454 390552799 315347672 861833265 868627796 605969876 203054051 779875742 250517405 693883280 302082178 809971470 420201017 495632444 521382407 11211940 108084164 189197431 9777912 85732527 169654324 499886368 30238419 556560854 678052584 539761539 447031619 365200031 197892341 62883085 20601505 310963232 953080491 38516518 42372399 622527322 336345674 558414813 6946678 849881798 323490729 719530293 510214116 991575372 955887203 627711657 545092098 287320735 984288135 891495408 991585561 351453577 922678322 604372221 607687152 630420243 489615353 733244621 191751359 539010485 746062851 86802250 653982290 395548429 112432118 964063059 400484020 580713088 580614113 488804020 425447965 391870554 334493600 194164675 908316735 565678044 304803584 147060484 803737823 914326297 524699860 188806923 476243115 456195085 560714431 817590132 787513441 699454760 8835330 797573621 730219110 775540453 959353123 73884864 971945533 816403336 952910861 773394583 716386184 440678086 646542798 272346890 487635077 515420725 661196835 80308655 304867774 47849405 119836318 292504125 232122280 85895075 174270780 863954473 145632246 471382849 475126512 829430926 429285613 315894726 429188380 768275848 620133969 345138248 501287440 13125635 588743871 65791545 318357448 225363531 709656918 470098086 463420003 249431929 580332133 586534185 837413615 914835630 481871237 786620993 485764142 345834373 635688505 786500496 44000175 652405881 276361170 29331476 716658776 122122941 648215171 34752616 456068282 159868649 682850928 488549769 708933476 849070002 96935081 411448114 774162531 880304513 358204759 269634751 937668538 892573983 328589187 609163820 16422498 728083493 820871938 286029851 538015312 257618120 689449768 789273947 403705634 708740443 923778886 643830943 902590380 332372692 373076141 320902148 1429221 512311537 507863750 952824550 351846093 31857356 110230678 46355450 897235188 894139887 738567272 984589855 293472377 152531962 371522170 690859175 884459702 805630404 269227345 448783646 130451109 735309615 746459005 457878719 957563331 314482868 782774018 913681148 39437626 752817321 885317901 403298009 766565672 830418660 347803485 227202325 681093612 619364494 356263262 134940381 219178175 587283047 973589545 57291664 848495254 76358955 648261666 910136815 881358864 711276839 764553118 576289566 742000076 195928752 237393180 131661694 832903207 252175985 986947193 101193429 90743906 841037553 794786411 113677070 73583468 780775682 336931506 588649791 334794716 640213891 86440980 184263954 761707231 126884962 548842546 947752310 370769998 635899572 23279909 548134920 9322188 684513174 63664227 337829822 711735792 488182164 798071577 757021188 517112527 118980526 922597467 475823822 289119294 727163541 61071322 103584821 420446339 649304727 82689395 587943920 76653873 981594748 355453627 215157972 631202785 70496443 30993390 597046931 881041703 693886794 217360492 610219232 609587661 296886182 776022252 487535768 53478891 189154679 94848318 179179134 789673821 245344613 144010582 548820494 657333593 660627708 917522058 949031296 654729404 439537573 161186831 681294617 591124696 753057047 752454519 909672709 759014320 951761114 653484203 66075010 20127380 463523772 853245335 635602430 353838098 238394807 282845513 843443856 123354351 732801107 905503537 925404574 119816126 209052029 613091672 574909003 680542375 456038943 263956578 665452087 81169703 137317681 837451532 512697869 914602100 36569531 861032121 802174185 174801511 11961841 295105047 359479309 9467525 432073088 92498540 202168973 862565284 840685533 42071910 347824571 303150065 81807588 557865497 665985780 958663089 166661959 389569231 330383357 244292206 991308069 938900178 68807751 713219903 282131537 201376089 459033466 889416659 780271692 47088054 124436730 117167716 473684386 587327442 90812705 428916609 936583265 745416311 80875302 438150574 510766596 197488481 340107680 566508540 804598405 316256665 20113829 824263108 134498843 805789940 234433503 923049771 207799113 403733727 401395054 602788464 189358379 573148904 182428332 762810452 90734850 638457905 475055996 858811263 106527943 762151993 833424266 552782333 799318234 659565169 946279529 632089869 712241348 650065588 199331244 17951682 721803772 190784410 584894669 948476413 37240344 807642112 113926469 434614109 377741757 330455869 424988351 118143796 717241457 588493942 416460195 326655206 530974727 140292180 827830352 136549323 513852876 567884554 797063961 94162679 507757187 409603275 739705772 313920818 701581903 555767589 218577825 312076667 919160095 173080137 968344167 755563563 990978539 966050799 689906647 671505780 832274806 215371919 267543815 71972938 311645655 863131943 461948684 950187088 767516705 936411620 220396528 292428464 173455985 6598052 922532565 989336491 625768821 620256010 365269806 576851328 732276818 437683533 579117247 388077178 684508942 534286920 124404500 64069658 71243010 266821675 323020436 723549741 857144694 501881177 880440850 79581523 740596839 466143275 633475037 606990668 398900888 101621329 992434076 323740797 713820899 858968328 503763996 441159143 446045656 987185956 258059315 34542006 131101542 781400893 287347329 744684929 240725113 946988833 851027977 65318506 613126174 184660279 116441454 243024256 650420915 833078978 549575978 754743834 687079448 964402324 340563179 273016926 713538594 405012736 36336797 920370998 261436410 101389354 660955840 303312812 147045263 496707951 829959776 754928342 461465944 372879225 978745588 582917508 757702529 786172467 395329770 243783852 168944239 478924558 949248750 48247944 717271509 396641695 184916870 592330442 107968568 598574393 3896568 715450760 881295284 522021187 111158069 835920618 416554280 711436771 455789460 37569414 969233877 465620502 372990002 219765587 921456664 280770273 979098467 697728254 332059408 799669142 653390756 4541912 721561882 360528255 861184719 172021782 878855700 155169906 280274590 910708737 297404224 519136778 976077376 805372373 139519602 160807008 388517133 500634238 826126679 472085086 951578836 595458756 63662969 271353468 134646739 376386082 263569265 802991809 149252510 564225412 20045837 354292546 655546510 256623995 831158909 260697528 109886862 420603425 492100112 358405868 466739718 380489951 438797313 861553191 660180261 436886563 615772280 694834135 285380582 784595387 751088063 896067868 8116436 814286500 363815508 839020079 954004834 848860145 166348405 401768555 878967899 656209282 137257792 887777166 344826702 970196444 592894904 879841749 25426022 880016530 514257083 24981734 311310191 890383465 353224486 606565040 828386373 112796284 928509778 428338726 597469153 59130609 438480559 806079030 339157696 151711666 252545412 965985206 375337747 794684772 321292061 346897159 6535661 95818726 731841061 432524192 607268693 231108560 20383254 593899513 700715021 556602248 975193652 79837466 71302408 195701715 40596208 530046585 90599695 180524413 294342724 883756166 117808619 418360550 185134646 79601247 55417135 102879620 384409411 292898656 953111252 256747195 90186412 526339602 399540120 919524435 175474399 594780057 74764125 588654050 374537867 942392674 408869273 579976667 859101599 904672892 246976486 973875361 126184846 382490699 9686583 122513850 590078655 955697694 780344656 398024620 961579221 439798939 4537499 33182522 500561029 884109109 361239754 230382654 706503279 129585802 985637753 864024863 462123690 129713245 813888445 941620947 8823655 250421224 313636544 976872671 73017798 527664129 917626582 778259450 225901380 455809846 905294525 282180401 452239590 251094955 265821648 397761054 673112490 414188658 89421050 700998553 723080677 147433353 623744348 657338921 839838355 445263999 479602173 373255140 387296229 843530439 12753926 754365721 654949430 730760861 608733578 246309791 342355874 485669906 623668905 710039189 380240156 241171558 292200131 676098627 497169390 500204220 868693616 970028105 516153876 455804215 178819766 482126922 512952296 820206226 946823190 862569586 11141855 604742620 659993391 660557249 552726133 886737593 570066451 666148804 331588813 955011920 335039658 975931890 927898153 719419211 790873080 631709993 244930849 28092500 397318511 11068366 237439426 829502626 444578108 984567910 198197650 543308725 681282381 354744535 35050667 989422673 303924225 566614617 237760487 929073708 647263259 959108117 621170896 258402108 264052606 47625767 499855863 323758652 827743978 959680114 903074769 770142423 586542842 60662292 338547182 456391585 544389351 966322442 186915285 904769589 960382413 740932597 238116 159796563 267503178 460620688 102263620 159921871 546176953 605598973 395276938 358539298 932448597 597173515 151789936 630720102 294605644 474895231 913276051 552928198 742555501 22876828 803582143 402285551 38942816 564743756 226725560 459013440 786026993 946779345 815847451 948826653 331581015 453482667 86312702 144130535 476979705 762324361 309753585 342454293 651376144 80841133 259713587 808484764 872069519 407911190 288959473 153406992 921099917 662369695 846652032 347057125 488759847 536686946 944902732 719784666 348450929 807626279 153262016 454480805 984622980 325038121 900854534 927767394 779815531 641440180 253580062 518989793 915137348 424301641 182488397 648525255 140042906 411422867 364081076 86671342 990716361 525495069 206010033 899947261 364013479 916540351 678116041 407976520 334053484 733315317 48367139 847549933 930735035 520389116 145516334 137942813 336711983 841218459 43504754 986320750 446398504 161662372 848497167 837463010 665612359 819159098 743077968 532034904 615129132 686455510 642201309 617924543 309059418 812514473 789845819 106466603 2740999 927891885 563097502 148760897 339747686 165511318 559547612 824307076 678326294 630292228 757162468 620781746 279179098 256373594 286287590 880994140 834978653 471924894 495841034 891592306 346509011 138860450 342312131 58125124 104337676 502613155 123314049 697093917 685716859 93056024 909660881 420456668 394853594 197033567 293606506 130907561 141643292 590535728 124044537 727099412 227505265 536915281 564928660 170319892 762199099 252434392 149087712 866040351 987715154 930145975 431922128 325210088 609002681 769009240 480729295 390910340 396766978 57031239 286963710 572239473 980856241 602563304 138810138 558013442 5131442 766788705 243698941 186889921 773163514 705575041 495680405 208098141 764827013 440677618 904154331 21397008 146245916 200569849 399557157 821986789 958426975 318260081 840873278 170286633 189980879 656072867 221125837 546705883 547809239 792136209 581209353 155666103 426535604 352735871 38256845 56660282 376403753 617245052 578499458 200989889 855578742 932619208 464644278 233524621 318814540 85720383 333551379 662991760 206419306 266398922 611100014 487804807 25539743 285404479 346066571 390551265 380423093 974093876 984066462 210908771 213030718 285182794 751205239 537797545 962678625 66942729 821304324 184811194 954643602 734986313 153488476 655680617 37369724 422135134 534359877 255979664 823136057 923672743 298264865 503605163 627852226 304698542 920159238 690109625 574652999 592944895 879516418 542384166 103197566 27218451 70436926 272362116 433063627 845237899 143176799 747896898 661252009 78263113 720520227 22347119 298869924 354180342 680271135 210084495 350029024 229223186 419266705 44465612 407003663 21923978 349150072 552506325 128446510 926221833 346505409 610976163 442258706 192867228 158901322 222649756 706340786 113315845 776248419 964167505 344750111 315157162 657313737 153429786 766561064 385670945 110066528 920106764 991215018 823367780 16868718 880202580 897567548 71931435 978011638 147437200 786488758 741406353 458750811 66036111 243095042 134954791 695016624 434591141 739986 786691072 8844038 176673758 300530827 166492461 686671043 489127503 310212925 931688157 664846823 455327414 50846632 276243769 510854461 506773750 193096393 626519347 471233563 663037177 674855300 784728003 91943299 276515562 625869009 202461167 776539513 978172251 535539950 389357489 874939982 809089215 470869141 502025084 23810665 877224124 937246054 330096357 551235044 681114959 244806055 190904139 64417591 223016961 164641150 616062057 780857791 975118867 300647871 901369057 762690544 460686647 541082272 570956394 657783426 652922019 146199691 82004633 83108703 431785465 272668313 277961146 683730264 44448309 91219473 63261167 989477752 237930226 787679907 359666774 690102763 180458109 714235940 80925026 804056596 615887666 109907086 55467302 235775736 933607537 111457722 947435860 289789207 844321948 256017400 149281585 716393392 734964457 180106203 345484035 452995242 364730667 683275927 606216681 772185330 321967041 713014682 838172356 479733838 750702948 195646031 358351189 624156657 921574196 372890653 869161881 405783667 537095328 252775119 89500724 632272855 921516197 223183341 26356387 229865558 897833269 433727745 544902405 476227021 669225873 276852525 808785233 912662550 237305616 300730665 111652272 504332136 592432580 515245865 88677496 389552089 835562887 256982845 451861193 438491354 297278665 179017408 911009992 647897691 385257189 215042947 501937318 73723465 195266669 209938502 978033984 533857526 246093975 145096175 670471536 693606615 304945220 298859293 884692142 152536232 205012007 594545336 884093149 471303524 443307427 86945258 513188612 567745512 900680172 64069722 561327794 131928250 446411891 294513179 720862254 832584907 47365152 549068931 650675356 192030867 638238431 972104720 978094241 976623813 613422986 763327058 794885945 167832102 788241384 597374586 98319769 446121250 767479595 741928106 225796674 498793378 959688970 658400725 41038337 750439280 948885727 161209251 404589341 69411720 199445548 385962130 269645485 361645309 865473729 859969211 882230991 872765411 609391883 367037025 544338095 730114349 506211951 676042700 127443315 85296154 693244555 307725989 566111050 976817785 853758304 539662174 286725311 632726411 863332434 572215433 832604985 629840524 889930825 524234629 638577698 272131389 649525023 744527248 753334248 135216216 878000546 797788549 165872771 288433493 129956541 169942620 593090872 892643311 146262626 47030378 188302914 96542671 905097141 707417778 415337701 43707465 361143337 449840727 725327669 738566726 175540853 500744009 945765205 110770725 171262563 27827601 762897733 598741104 9797189 390624770 942540362 219399182 498282342 759455337 466585091 926203451 286263821 578719589 333979561 51335269 638827783 798359117 773702510 793897111 519944525 248290656 742496694 276638043 296498137 832685022 136793089 284071245 599298299 988400455 365663240 303106411 447950615 896168682 688125693 8775676 660057288 778826576 494229677 105135530 289950892