950 141543586 841467500 428540802 650535342 655810121 851624834 524539594 616440206 630223659 733062556 695484053 723372513 863699072 881574296 265710160 345127134 605001812 838376227 262212341 895114259 166217252 863304828 565764034 656133902 354348887 760399316 449676404 726349485 410350602 453716498 291317241 876820392 254686503 926098535 489852707 819702305 211323563 863426269 284782281 609656720 980358670 980380895 140563721 340276894 576435608 842497841 762201957 877360393 425289839 548598983 596435121 730411674 84557217 864796642 129247773 366384024 103600595 734859031 404868192 724644902 833324894 998018432 238698702 727961343 167478446 173924498 45941807 807824130 744855773 949497556 504057090 577405205 388583695 948538830 913002478 976678415 496147059 586751056 789147117 888639926 607603065 880838097 161014153 461067693 749629703 758259303 727360406 975222245 505626015 836019404 848883514 892746514 642998857 799973848 153047571 512616799 935085696 999128498 332816569 989836702 43796796 587832485 692545584 800231588 526924483 531744723 514696044 577496129 317115091 329504357 473043580 548298013 477415906 590508859 234530971 857257669 907232362 913472178 707953752 875289124 346760680 514167751 236898110 567501336 282984177 996107881 339689935 549145628 867151457 943474756 63339719 205410114 83345599 351502957 941592637 960715390 603587352 892446199 572545808 606172880 337630513 373616542 552321893 680376528 544306623 678468522 904600895 933723661 34956400 735662362 306943206 631146901 134836960 677620803 963377059 976839685 344102091 605386338 115535056 586170032 921256471 988975663 416264011 575506801 836683519 878183744 266132038 314529491 895671878 907571960 758482331 842817522 288709740 664967907 895736103 940535227 453430097 835745701 18247668 632926902 702855340 838149084 801595903 944834879 76858079 320467429 208420064 861376441 974083456 993909144 962597043 998712360 253161888 788712933 884277281 938467227 746181518 808644948 212072301 687505968 452009596 773575589 137823332 578028924 165974845 778425146 320733292 500864897 866299943 988427201 657562226 943101645 456379405 967773175 783172764 848459987 344374004 975993267 689361279 962263091 915643416 973098393 743086000 971715320 344844584 858147373 982856935 993227221 37376655 763403913 411576477 704314903 553675004 974876548 453708068 872667482 428964306 886761577 789820977 843499107 358564356 567155202 727216268 917336415 713511914 865443773 654360580 691614566 684679110 946454948 266858942 760593163 631534055 960895479 956798724 972960178 484787920 497692621 382323688 772721825 394590114 675336608 507805924 811789206 971788614 999851012 97264278 440385981 305360478 565670013 869083080 877014411 49716588 421735287 155567103 628970993 233043261 581491356 172495590 331993530 996887081 998676105 371966837 581609145 799065542 877582613 86037544 727129882 492787556 956393084 362783902 728212356 913210973 992776022 675572148 979576015 348722807 604597609 640010313 972496375 769248787 804727662 601710342 759638794 467021369 754577733 441300335 827082059 652921436 856814422 743861712 928863433 33007971 802452897 672142146 720299920 267866251 824281497 86633856 636034249 945725325 992981784 774332015 794592695 633930634 789155152 418353144 594752767 154510602 675181715 608417360 623464130 194869197 566926317 728613779 851616885 667504605 859657067 670822581 949010415 690692304 914499575 803791939 877017119 73531810 732621724 48831840 467574798 836541007 962063979 58736725 958288174 643539437 996773277 48035472 274584618 344781229 864809645 573031384 679215304 559968761 610755369 530883328 850259580 645774049 892828360 714761556 744957647 456166030 731538748 874929901 988845158 323526631 804062360 674394989 844092130 623485603 830051561 747981459 823532635 160963962 316344578 159890748 270866016 56050603 394320533 874496590 879570098 394614611 408934229 880527666 902532921 656692783 709508665 249782567 788394139 755083079 792393685 231192424 838028986 238518023 249792469 165151752 203660464 40857955 438827805 33437636 242416822 984470954 997143934 626230604 822014193 229893969 493614984 155849302 426346116 271831618 563424803 328904146 876248234 526683574 551386237 976222280 993427468 555189426 635063483 786141006 822052891 78438092 360045567 385307601 691090532 425337178 815787265 800883476 856224416 722575309 772077314 85433314 716749109 757534181 852310043 613977667 644993736 81781030 229406791 88655073 929390341 10504156 12667829 732077341 948350054 103065314 354775538 822491996 996986534 99471776 869982034 67672591 927345836 456455084 626220035 135018784 869799376 464993748 942135851 558182245 762917542 798393749 853592767 426947329 661555177 654840034 849450003 176845397 340912186 541133337 897146140 702995498 950624422 140197992 581060787 631273239 882910462 192698139 834088456 472315387 613177548 385353494 632788670 383759644 636228293 685794871 921336338 265709129 430919514 731737606 883310278 109414123 660680889 517234347 643748108 795960350 984143673 615068134 766745741 367399111 946683252 339182533 790499273 699204842 860328784 283529105 535642308 108011039 578826747 361609399 724837155 142980949 372830606 926589868 987396050 192154139 576078795 630923754 810935306 624476156 890944491 650395664 728971396 978116708 978212930 694682412 808895102 354212381 769368411 906115822 908215063 962657739 982106234 646955478 839814578 256060720 661227728 564973488 739912753 748518222 925438797 706740032 969957676 372617021 491780304 634421492 893050536 436152374 502097367 328510514 410506160 713631478 993872018 583410695 973144278 387259999 870498502 937529336 953781713 542362602 617470733 470516905 559301683 220265095 868115968 306407169 960454901 207983622 841968623 246415910 394708399 425637252 781760653 130765378 894356405 91045110 387929975 645887561 937400520 774034124 867165984 577031222 660786375 927546598 941231906 356891265 571248619 706419873 773419354 793841952 798817453 190254905 374744599 271495884 495678207 108634021 303091933 602127187 809816284 222856303 304682143 993200667 996445336 617390181 642383114 274411775 596531195 585230564 889753635 284530640 484740893 821778080 994400896 856529964 898080823 98867140 925151960 330212439 666128752 710169881 966831213 607293430 774156677 114889924 276037302 15128784 976748636 779845126 871461163 127004065 164444598 957569574 963015711 219283687 853976460 173380542 730781714 121025111 653463527 814263274 985256591 769354978 905002255 936481785 988528853 618780824 965375699 835582836 876734994 129081012 971406953 193738415 853299118 326711536 698939907 195973676 213957001 381726431 832375986 328711079 659515288 213386447 760987432 974259315 982519117 899457887 953867378 866648854 911559454 599782581 737143640 559934609 748988496 386080808 472919993 809275034 819006566 655427845 691626239 477665352 864951098 420237344 763378874 501939887 530375910 852101369 951222868 346547897 457264387 378488382 696190891 766869140 921513886 572237181 792027153 235189440 944917911 991518096 993732502 233032429 629525801 497364585 743606526 133960728 610663086 191529757 355894171 975196190 978027537 631155303 983199458 937671216 985073804 947989611 965772928 552449929 789337133 476902408 685166343 568834793 973188263 639821663 948280464 507855884 779693172 894389083 921477128 523885281 777751625 663261884 814942922 63998957 877632773 350814285 809272909 982336757 994146534 532143529 869662806 714917477 827226833 822052213 953595890 805409750 837183504 468927631 493539288 592885543 654664245 392833635 594926013 691907743 705900886 203421375 459755739 896672333 958943517 258261124 942470975 947251585 948360878 163164585 387687335 169002607 785972449 108043020 791188376 879504593 922580728 156908485 365741623 119768553 123168573 561591931 740419986 861341823 923148794 831680272 870706978 862780695 890170685 193889839 618483017 509529964 771174096 938376648 953929319 522879743 763006209 529900942 855937048 81584445 675945702 942966095 965082234 921697843 958356051 874218915 938110995 167329103 774541478 275649315 474969616 633545566 725186650 428347514 614065827 953452794 996672055 964441704 972942924 213745314 998325565 734756547 965270693 44581078 137687450 930336317 949547441 66883955 261968644 262523685 709284859 374831234 534040345 616462019 799481301 922524644 923101255 111747716 579709686 436440516 633032032 306392488 782752139 845822997 859258641 887040883 888546317 230435738 404903504 593198406 705723190 956939599 993268353 784641104 865349592 554702376 943387753 560523057 847998097 362152992 865406057 588654012 665090173 378634456 875062798 708448482 987855401 868313650 878451324 61096015 116182899 922029998 986981606 947271329 971310771 502630269 578362704 373775794 497167197 446358800 559018503 943006817 970372426 550579794 575110503 115951759 734380143 516410478 992582534 615180819 981448220 306998295 859639755 681883733 816742359 635104862 768623642 56754944 875461918 362147513 447558975 646241161 770851530 462028581 636493956 215814166 567360829 543445858 585246527 890702883 924002029 751291538 990923858 348929411 707377830 329625888 958909433 903029797 917035687 32945963 490875734 235727276 782939617 397996626 851851777 732932238 814219593 31926520 766512371 975690089 980373480 900469892 941404975 857720833 991096965 768739163 870831921 512698873 742303372 432325108 895068965 509833788 755903200 961579332 980728840 833969192 928947269 150144838 215575704 161426645 441686834 560780830 912949214 98831876 409274131 886899619 916536362 310205200 348598848 467376280 635852729 84873011 120302319 75738950 868320771 455077172 615545261 483901052 690875748 734117788 828257698 794178138 823482087 281923486 365029332 344194150 651249466 93006953 174708193 690655740 747121424 365345046 424559980 94726933 957403590 993350935 997996473 126469256 623338269 881551539 901428206 109289514 809968891 370259987 965396699 159488364 748921315 179582321 804482498 619932499 970597539 403516570 840144449 194212940 528899909 887538851 955105929 186422209 370892186 261945115 540794648 481674884 855602140 497670421 696874774 257271032 306344685 775989001 992471914 188551027 628341468 302781736 318851092 174107747 659601752 377028611 634670966 824531192 948236726 588482714 932942867 587381873 950708182 251800280 490729184 985021057 992400437 242929275 787911103 499998093 650388839 936238374 998019298 43558527 477039846 962314616 973528483 723466056 757452569 990225047 998611250 398439323 657201914 470751293 658097578 183998512 725709351 389447590 656515932 232041128 845678190 584663753 966841328 715991754 837210254 73089732 541319475 443531711 622367173 906212034 921211972 114260881 647639537 55031002 824449417 493323845 673811232 915134521 946618456 650218315 979309907 768673724 884751480 345178319 494554708 782735640 816242878 600358481 648220220 532619741 622770652 508322983 614191204 52438835 748962786 968828864 991247769 437218033 863489938 660925892 914826042 786298556 865185096 874748452 960916241 353408146 466707038 115443354 433437304 375558807 643374107 743235946 813071352 715051800 832973664 496226447 919912217 253530630 686296777 262115354 489625654 831349377 946090982 422567317 662796015 997020013 998140973 590543512 921810842 483722704 954179616 765919584 830431635 624238685 677678889 63456169 64010387 420108994 843141333 51259170 550234363 61703100 598391727 367405301 935796044 472909325 484970650 572598858 930019609 779046806 916899262 694363966 830354614 806169604 996478504 608606393 894318486 453858966 988684710 874163877 992150589 68079961 434496845 782575397 879673345 569308073 785759180 611826606 985473195 952601930 995869842 778672310 835299148 196008548 750943583 377358787 657691855 869363600 916243007 599467556 744409612 944262074 953268774 825325385 953380972 561152589 847808921 999497601 999608171 37411372 855508536 19261871 552460855 836887723 930462449 132170973 922390407 69828074 383322804 791915916 793232538 729218156 968612870 637096840 694247088 156986628 448903205 799157863 825709710 913049898 948436735 617310284 963104654 417254182 599350469 182483753 295967066 513418267 669536104 767344768 996291259 229488353 729481313 234449511 581833888 53268423 837718650 217068375 858032116 915035810 995696245 862047671 946171446 424647331 495638233 775587652 787447004 539786440 829832774 94599429 776279500 887160650 980940667 692155388 801698601 153141337 630035490 411071588 514702902 516650132 627500505 431564748 644416354 464218840 714117696 982170039 982461827 896668815 910533070 237259417 451363170 940104939 957527459 312976960 682323960 182614900 834437363 823168309 994814928 680340043 963679715 349419916 573285169 802080110 826862451 179643630 215588868 164456403 582848088 574167788 615189522 217952287 302888426 537332454 785927388 302039489 718920077 678523386 736213843 714924035 762437287 995134912 999800225 859671556 885345189 604616312 891492643 260426744 887234472 492263379 543789087 532542037 647314495 233412689 536508604 897549452 904030660 182163088 866051673 988984452 994928421 311243560 751050661 378042325 910582022 893004636 965148938 184612367 841981956 301898681 920233385 589534133 872543582 815809144 849695383 318892140 867313920 819447032 972904110 747701537 992018446 784580259 823449022 647492902 910083210 179119139 526675018 773161304 898083798 660932559 837823747 102756157 909162406 963951880 980058212 422066164 801006165 433379940 620711001 845982758 929108091 921399508 970274486 61100197 376119964 802632089 809541225 166316619 390541562 306990993 949967105 648003420 787822495 966614191 967720345 577016457 962372725 256429877 314234609 603592581 870617167 117067501 774823673 627516039 992379645 60247212 301225276 12668564 752830964 949679318 985506176 486402067 895110687 117356508 781211149 498264308 847987810 260753583 922642964 853488931 955044410 245398491 660527428 91562874 387883202 251443080 657764540 556484755 837125720 293544397 584170158 669702274 757289982 131936231 680256638 397902553 547273829 706999694 735610746 130555591 210388045 208702474 387068219 130239044 408893215 213789133 228882673 292475994 364377036 106662408 166671459 377280742 884001979 911303794 914535322 620473520 755048546 554476813 758426587 701413228 880189510 844480531 876531916 583489546 876452276 835127192 970005355 746120133 849109100 780095247 977187485 896965087 951142661 290841966 977533191 467274904 833860336 762796477 873005445 645439718 893694987 974303991 977529183 17234150 263317183 93392721 380328606 588523399 605995262 461129215 481524896 517579278 828121597 998437318 999460415 335855366 420338091 686360357 854454658 939387484 998896055 730737276 747510451 417343883 995215101 382514692 877573207 143880515 283308729 575457493 819447261 458309450 644908186 139339176 394050398 54379040 738854042 542832270 967408003 280851865 981322256 339000816 794021057 807942474 816029314 430257158 925161759 151259846 514976840 290501735 339788177 847530085 938762295 284689311 306414504 181874050 279437678 121781006 922026454 517088647 874193236 72902484 252839326 241061286 340205837 998248563 999608122 501851826 845278565 349707940 905151650 441741879 565717439 941302308 996050494 78353066 485767495 896283585 931914357 817664403 956726578 345785145 853601283 143693882 445572814 923922123 998816617 813691966 960087610 195190643 866771372 341314265 802026314 80132588 296169490 429319424 766463787 132462303 363951890 848705544 894645802 317833353 677682365 503601673 987087721 699036907 754508304 907165648 971765566 933256671 934049756 823927048 830811733 731665407 830209347 970414064 980195247 694547107 899939482 302094313 519375334 150323240 795247647 455542349 782161718 868706345 955165528 678496345 754046499 90060898 182085887 897325654 974390403 742211345 900595183 411225956 774681820 995365273 996204327 861697839 915580790 219704097 683820140 516267683 560668449 405118868 667850921 344944043 623374141 795752287 935404217 692652762 765264573 785589946 871817808 728621228 765191270 821330357 873933679 903676783 974430614 588031806 990293519 894000583 947306236 479281846 860057298 349995405 744663662 730338892 967910081 437016214 467397580 381439167 663789857 76020708 275915529 862535885 973357753 634223112 772686654 211645709 878553761 810836424 856291279 349789357 584645210 358294422 650451517 597399432 630020149 144510358 804545980 434709397 662044993 841708650 868452553 897535501 926653999 367145731 664422225 220877292 686532520 651139757 709455778 656595578 995671695 726391552 963682354 521838717 638798991 770000658 904242347 99231343 623345629 504430829 960405734 596262494 719952205 321292851 583255654 913377965 978474897 796804895 830070374 352886225 540195017 658682010 707212971 718073765 879331823 432734543 445241886 64694008 244679840 362906174 990369323 156675867 764178835 433195556 519271805 687053945 889872152 120172999 629720660 200445290 356271369 530079049 986848511 822455318 835025895 109829444 927028001 925565027 991118892 751974894 825348373 549129047 580090186 14369977 294511811 132180346 942203606 547388289 595016298 671410614 728541972 798332474 979440812 713692226 866763306 290833776 388717472 602944743 908971632 761445268 845900184 568151335 602084504 768931908 873686749 556416570 758398729 957334623 981524970 926670376 953583736 975352786 986203078 210569582 256804384 909233572 942784103 131267615 529921498 948752305 974552009 720529913 910710871 562902792 835183344 948112146 970511214 945208479 965725880 263994139 952686125 609005951 704122571 143747476 310209289 621088695 856603503 126075581 140184177 722553447 746337215 882223452 892246998 367818261 408660714 889628203 951304320 176255075 497420642 551025745 610791977 984911032 997707231 343318294 838678283 247876564 367016916 263189724 823946682 451548198 739654914 965913855 983565572 543982972 571452468 992322050 996025207 528905971 619785646 370332974 722648783 320958115 702199710 69456646 714506307 934673637 950112193 77513696 862604971 167049152 745481356 373829401 959253783 74843990 957154912 462973235 798985658 579224489 695985100 297709547 654480315 161100311 976642804 878571759 998419959 83509327 86342673 823668750 963410090 288958820 742651687 64797212 864038239 667740304 692153653 162489930 231693716 135440165 274122104 520975671 749303644 803319630 814350998 362002174 851183873 36276342 425103797 118988347 783399696 956495266 961830556 642388785 644066593 378817442 905091818 765103670 936013507 818854429 917624141 342221717 864412051 523712675 579984200 323266493 911781667 415984171 871253001 515846913 672666691 980023233 981736845 45694523 163050968 79271404 985586353 276516142 808395296 565091553 743073582 422645153 569513963 708761573 834118184 182966369 940184913 401990001 962043575 783283200 886192939 128186283 856928856 518886349 553936736 124624022 220943455 664735532 670602864 561614259 853095402 374965105 446480285 796900844 948657266 967322153 973890513 33144636 220988003 521728833 886054103 973984792 992823968 578774739 885957948 471144568 931956629 837963192 947844036 759658859 896093753 361710368 962762778 266859488 523919562 423379450 785538812 251703325 784528748 943854093 980453500 190447996 909201408 497451640 788672033 742338708 949572909 178420978 343573469 486390916 584998608 480813643 527740286 374440345 863318602 104593884 958997452 244331439 680011529 412200169 844338140 639311949 804137912 163584573 620952807 412157238 602811609 813461084 909800029 526493252 550569111 23872029 754855419 80189923 475397659 232020994 811586660 429531461 814735204 123619530 771166895 794035358 863736211 749877648 858979261 662121250 710807128 661332850 873560518 382965962 927617689 333497429 725641050 31144383 673536150 564404728 770083217 945882885 983494168 571120787 853860306 77389731 664037033 982310822 987423119 339472649 791850892 94183907 177089334 688766196 768639868 625769688 753366526 381268000 716935334 83660290 709284492 31930879 892964304 88940835 865583900 352311984 966687021 911768256 994300288 560193910 821606083 322283787 946974451 607395094 867463958 120951568 961314104 490273028 673359993 959445771 990954394 161873293 428173215 569537988 806634287 186602588 700921265 519052149 898058108 539277074 847443893 688913620 801640473 143406566 543451699 725030415 969132669 417739309 610933524 523384737 649793290 542635998 947403552 851084745 883064718 179421591 356580229 477673011 565286642 465500798 606357510 291553338 444001647 164818364 597972840 135533156 468072427 504406047 593598666 169782740 796692021 108240585 999110515 226101381 631220366 181648666 811473265 222800066 295225810 667365344 879917041 773463043 937077408 14980830 631598252 932561652 946567198 258017010 319898405 363945367 521581434 28124466 950369754 628023245 790530664 175559354 825871264 555116902 886593251 853034356 924091732 78194559 497824704 18050942 334316147 668747852 841984137 62201019 496616759 677899944 799419787 359192718 706371382 742132454 899464286 914050613 988604297 542433197 798069599 846687172 901380223 745971272 927535922 716024370 741747217 464808236 829190293 889406462 980380776 265161168 438934306 384531555 691189999 145875005 612699065 162149396 530739022 571698096 851327565 281621400 354046655 786297712 941280737 586367868 641623098 766803517 955962577 171239874 447327284 761114315 925682231 57049640 156373452 822016683 900427580 580537506 984346342 779062194 868987370 487149884 887262505 231998853 807972874 488844801 742064623 730684001 815948298 772296191 850221924 122648095 893783563 674029180 676055209 478674109 538429670 90960653 868824227 589304079 599057894 22839476 672165569 943387172 954366261 892440815 895244598 283754043 739552198 709502899 766674720 128458714 326083091 661518759 695628365 403116114 972029785 833756156 955481708 896522743 997683783 273967922 337871044 67550294 221248693 406223636 910383450 109438913 754891911 431460522 697075705 720109061 842287512 19537333 154190392 948800021 990002384 863281819 962561590 473936164 843999214 76553450 503210979 207643244 858658910 478200700 965235477 611825851 982222197 149180087 210075015 195191743 306173075 102957016 839663079 687012883 954715709 50625904 881467367 391050366 589514706 268264364 875197581 90525031 786395405 554849119 584120007 39219236 242848549 399051309 468925005 564118229 710440942 30881621 856869346 683870609 938101482 448021431 823140139 241712696 540832585 732427318 920860837 992113390 997459419 806949387 817446908 363501412 652322058 412506205 786107501 471928717 625660453 326532789 425318868 459418456 724662975 196173409 295068538 185804908 798631087 591013195 750614402 847616307 890632936 159898337 916963646 416462194 507731174 524782364 573727975 312549740 936563219 690586796 984104415 185248309 967954703 213072565 342553949 945361179 954398192 206171234 810054080 13860991 323964528 612010526 841386781 443499257 609374212 234964878 841563684 947785711 976685358 25041286 807748898 159347162 463750484 455200095 514118854 639484013 700241610 272745314 493764267 206537070 215670008 277121378 680062500 971387862 992469694 442731096 558116214 472359726 490198402 114270342 455979474 417780873 509369273 292151390 350185616 104205489 184191729 412035512 693566654 970545497 976598506 269334053 919704037 251613630 956824849 129621999 322459308 380957122 861324803 787225472 936329175 697002115 985320969 194229560 887790226 178759549 711515536 255608570 389054447 909431728 919129682 797923833 947166181 997185777 998983016 484438067 778847389 31297458 621953444 413472753 829184361 824135394 955708723 142999170 818252225 876149405 942402276 996737304 998872415 227428003 869416754 79013270 929382810 538807741 905334869 974651567 996418362 350099312 384458994 916670077 924777342 116509877 310949175 638662073 713149197 842580065 875506222 23977649 412523715 689240606 713901965 189059759 456724056 838828634 909143052 346576288 934002705 692974382 866674239 252618597 491892680 563138100 810807954 355569243 941422512 446007502 853712266 276453757 832727322 57110870 875091292 936891859 937160746 239599129 910215505 877870081 896028453 914455772 948031651 434508125 484613879 154693943 704817244 845655979 905074219 703598857 727257373 187362422 428198196 27085563 778926615 298374335 608748743 216068181 314466972 24798476 938314445 596158170 898869651 221289724 656795377 922923216 940762217 177883639 631602859 998196528 999032757 701789832 921603882 191745413 360486346 627385641 838037083 559671201 753589894 977465576 977938726 180236216 629077375 112957632 311408387 795178109 993700367 866214117 941387433 465488265 605642473 686483663 904899691 861594052 991534508 897552040 910939457 672253206 749478879 704349038 835822804 362479995 373203577 899920485 983921380 597250967 915715475 988348588 992022298 149436738 870077796 839702181 908458055 216558955 823800749 48763203 186815582 429277953 536903169 334077009 958348325 406241800 571609995 96837299 353173009 219807682 869556976 672982298 816532063 678087817 953535699 405929827 784257317 393703467 923030297 269581124 975420825 682896182 693683846 699668680 915034604 28221747 252358143 58203200 549018889 520060922 870910662 890781636 999091086 620907578 875298574 651857540 691686649 885183573 960241129 833438490 999164110 787631126 862755453 908438798 993825101 929802871 949490104 544442667 791002761 80972695 228014024 282374722 602268770 323427045 555050720 712720153 863966084 855149372 895828190 811325879 817810745 56432684 312417969 330907017 917734620 958701290 965494560 150082407 674443803 667844590 984236760 332362720 855077704 613128001 931395212 737958795 937252993 858980271 981632401 341823201 530402896 404689179 726620929 362022313 654314406 951169993 960296581 37733191 54281186 974498819 995292958 307950562 478040449 587792924 672931660 954458065 995004520 782136172 835962232 812359402 820670810 374663871 943089871 577446046 759897228 851117563 958407649 950557151 988439635 62651573 350692641 502024752 602102461 578398324 632584330 64951641 507915961 176023366 586044209 56890319 125575449 808633986 841404444 459421734 966899028 16777190 796265852 785007094 892934941 770213013 886813722 526281803 985851764 951919384 977406306 269015783 758680712 48960332 191834906 373117663 939730726 758432426 822094418 850057106 891954549 794679240 826391363 56919387 437240602 583435628 733663282 944834780 971906791 816854228 866120542 751351716 950245433 417437113 470756147 442023833 985959443 93359591 909551549 762120517 866082732 875336111 947248809 658397984 904963064 327857703 687846390 449921298 777774791 882158631 992450701 235879508 308753374 316589671 681257466 345242357 830955888 289078212 768936160 298751201 764656517 713700561 747968310 977199412 984463283 138420279 172056367 846132400 860825159 657195661 897299616 252869891 332994100 272101756 528150570 995531413 997455423 841477387 903876930 91022590 181404483 411830270 447634103 717465242 968918370 607457121 704506117 137198100 316939992 662963975 723200226 602665262 947908116 450642172 657364740 66342019 662655968 504089650 917551128 253196985 528789307 974555142 984649097 317138345 496342045 30443386 90070323 220560666 292053321 700252666 881683962 150115600 293977210 243201719 297059994 284581232 495496918 57405556 561647631 977005504 986335621 859557896 973944122 318162203 821289031 447731941 647041013 444311007 471713021 98547772 187054271 787466868 865708476 634266204 703248264 921836199 987784917 359650127 548104663 752664735 860773760 315576373 633621502 813948762 932687459 872609296 927180024 239656921 347840150 516705838 987477177 414080209 473254074 936752360 999930446 362378042 401325046 496821190 623869814 640320151 835705437 658426752 718868436 512653432 766813880 900495447 950330343 189782688 912665153 122148220 153727464 937085201 989183009 699068660 850616189 498145781 526547280 935838171 940219571 402809022 807309681 57980326 581807450 667219648 916836213 257792801 811598466 996955694 996994270 685815986 740616425 766530732 850692394 412234172 991348272 667403615 985589654 682307374 930761079 95787147 420175931 650843541 857971732 872003804 971819786 177836513 275053800 377368978 859695180 764976002 768269830 992211294 995734467 672431968 858082684 148716247 276254181 363809777 748520065 633726900 906170459 808530159 991027501 589499811 640155584 217008861 604427400 67910894 242768279 96368578 151119519 548495392 859100445 540172169 780792260 501575822 933746533 46157541 555711433 319584405 921518376 985365805 999302229 137909778 895495631 153942042 536910396 971366629 981379211 101034854 965310360 399793059 539570053 144925028 736597961 723798108 822662938 427378292 476746012 480696878 837218201 243795882 966750448 183131006 939199603 793544897 811737045 520860331 679429810 691568760 823252432 820879154 988864035 807498800 824799673 971057458 997859199 455852216 784796996 962854757 992144884 335275475 620552850 899152905 914354587 982052610 998155889 702557272 882637014 181873776 443715673 464620594 897656459 966874711 997213122 34859550 620164501 756843911 860953197 547587454 617943486 912591872 917249003 457357640 752323171 726464422 919102084 196833572 560995913 397737712 473087699 777293828 942227755 333169612 667458342 972191556 992213909 67932842 626966438 845131227 884824465 684354889 805075016 426382292 963575514 506233456 667635201 798414796 984043398 856966873 981947958 64173305 832944764 121566390 779392843 772575210 846203718 694338138 763151971 32632325 629009400 227274677 491985393 205728959 720737741 995472094 996202172 476438183 897760729 915488451 972749281 312211450 449501226 408762049 752739305 153684301 605548136 242352591 890778481 973668677 988038482 239560158 919195907 908486333 963929096 922382433 941829790 575689452 866683415 654270254 988485769 924136509 955169798 912944204 982056481 564313295 664638000 67076580 330604640 714013521 861623205 100458472 864970684 942644126 979719415 394484762 645172496 743294608 923894527 265172632 801049890 846922838 923026655 685575817 917642104 556667388 916422389 996491159 997453985 618801691 856059691 647610314 920008860 450938236 799111521 278375973 976288119 670048830 864985763 69918051 778189733 933069737 948824001 244970956 782195385 196711883 370185492 667132587 906875120 767168794 935207075 672684662 830185099 737056543 776523819 497704866 940771713 982939747 991789452 832620924 948564923 182514203 883685803 353385696 557458528 81184567 341748592 496984089 620792552 53692465 249018991 896783852 948976689 355318317 699714298 74323999 262960727 351765252 861507357 141226094 474088900 232928881 612386507 964845461 999090002 826420460 938708090 159949000 920437326 607439303 714969013 76077765 927754416 893411743 999499221 455444492 636295994 538841195 839315320 449770182 581622212 808782648 912239859 823420442 935878978 815134935 929824093 590721941 672162550 748324301 749884683 784673404 845909273 760532634 775000150 727871855 953107299 897055810 992800012 347745935 572916924 738735490 765905200 788213919 834062743 99785719 760661602 789249027 953614867 952441768 978191759 921042428 952425175 165884733 944083945 54996661 677950662 207997903 981727991 899233355 925625053 421093273 709026600 773569947 956516957 72260051 988909718 212851256 513321801 85402636 819986499 679199383 868701567 377498408 406631342 896935518 991673163 699430369 886643021 184267348 932277468 657174186 761817285 200325102 428151156 653558199 962054158 534636181 962774297 886043582 937420442 769301579 893830586 565411957 608222416 195343164 721334942 649754991 938995018 747634677 761034041 256572080 805333281 891950888 974214738 890049157 912632685 537665295 652162063 102600532 366970179 494408632 605384309 37114095 264386571 865905088 909588178 897458922 898955849 524328291 647414362 243608453 331461143 861160582 972158579 771232301 975048870 107687002 868934577 676548882 818196774 510268939 705670035 551844956 869169035 709578154 808545699 194576714 455749072 735380408 756635800 887515452 985916749 509271939 750379962 861828289 935545168 493360723 946956975 597203696 961702893 752262134 754848817 301371772 857557337 27233970 821965966 706553612 981707363 191987553 792432253 206904486 500501073 365236705 708052470 328632923 702371439 807390474 855860131 493042748 774470768 900959520 929730335 241710055 687163737 950702683 995972192 113898820 139744942 882009276 886335428 827747276 869225160 136463990 949782656 666144544 891885906 745528434 870259648 781510754 786637345 465230353 895541366 642047053 646550226 822615009 826816857 561916138 789595220 160261492 748670665 281225389 546602869 774474665 790885287 286166850 926260298 255420352 257484587 920269808 957537261 382111844 952226875 276939689 914824494 878579653 924625668 667135519 861383189 373134551 973878746 489767278 891843607 166149114 810436931 851006350 883441224 519455221 823431083 26581806 306086701 363104664 777324355 67860929 235760389 382653070 904346547 656185420 903665516 205426822 673834161 340412167 988596503 736113007 903380660 691578088 739702569 568769460 985309507 385846136 745183827 229800503 298034307 900451814 986584443 67884687 304927432 369061731 578903494 498659076 706442947 519496694 727737653 973049772 977456000 754933820 965236278 407201938 653383583 784475126 822494753 269185836 527027207 930726218 949724895 232744557 724392441 353939882 412628861 597907771 850947628 628976964 762553823 612029721 698345792 540495347 954941168 684328494 827029349 449768334 614766889 314885068 467052229 583696450 842675714 194382585 979893209 175946762 182984433 683663855 981330604 955225387 990879927 270870827 300906138 188730620 611654798 770440207 818173138 270776697 452999588 414953175 763936619 262699636 505671913 292692953 576725052 352806737 735454217 286049787 832555001 169626285 865221359 568547655 928751677 936851973 985109899 182399375 256668963 772624075 824621180 779069688 939538777 256624578 871655126 279904096 961138278 759171130 768972305 757746849 920689896 615055678 735435278 584465883 724421678 587162072 954680450 84816965 215768403 592132713 878186763 268081621 965062928 215663717 331419706 790878413 984063063 900056789 987083928 628588312 949510178 665735923 821703091 200163599 388155196 923289849 945630878 244301509 515259234 998625651 999224273 232693367 882234094 615963726 909722651 923142022 995652366 167622309 364497054 986311842 988594486 297411735 721864294 499661515 819791915 855439006 946800342 740007594 868836007 56476624 564172129 953242988 995337694 753256138 876318217 56480544 800364088 206096614 330800797 774341752 938932523 683419639 933262181 630163731 984554914 482693149 554617872 843752425 854320052 233486093 412814405 998888657 999577954 711052788 974627324 953867027 965220400 576572192 767169507 893583232 999313512 941788304 976843350 665453016 784137269 443212936 917287015 394103677 521010558 402981167 736704302 501607509 638759603 197194227 329727721 573932809 870748114 863137158 945678709 494206193 549457710 440925605 791394728 931658758 938240176 793522533 847075928 951097153 968641625 202573365 734723971 720428855 943244233 822272645 859623474 546699891 780974486 218631386 944879487 348924031 519178269 71166970 601394719 451343958 931872845 668514410 784424807 406997796 515354283 718363483 958765408 875410879 942185465 399919306 547232537 482941571 957096208 427546307 734759688 441738343 925406391 450545873 450644289 683773151 796153630 145616564 209243808 185812996 212756170 344260233 818591037 749375924 914188977 469268415 812338997 75233222 387444353 137436629 364184427 867381738 987160841 505744634 998240682 407279148 812884309 979010194 994781548 532846449 845485779 777040965 966968796 520340879 729499212 965350918 980796588 571775789 985100452 717719893 845679623 66937441 508771824 779155351 800625763 603610041 737573656 614434934 651031326 207963328 590230724 953075802 964520669 688737231 865348233 862783143 920120582 417712303 758767235 659529291 908934121 105334490 929273657 702425755 888347855 966699361 991532365 572527365 856072027 912738020 984495045 327714147 496615057 567456932 815093517 357688409 807772614 908964195 916418829 493774522 653068050 334729226 871246712 581838750 799671732 894257624 944202605 925812888 991618649 467157057 848471291 434003004 977724686 505513841 645900782 606068861 982408828 244437069 369383238 742603137 819481985 287016252 522958629 694184941 768537477 301453395 715044349 251245293 329727790 144562620 802556490 952259472 995080776 983370311 987359083 949332304 950149346 474018771 746735434 553293587 703749412 917442818 984403395 722762196 837528280 127242294 244031821 624013203 864376865 628273144 856359358 761132168 918511726 157193109 848209062 924445329 990117914 452115224 868374290 329669774 651846346 665859707 861444685 205516392 741923967 53793786 755461609 663870133 855577586 890747035 997118027 733892111 995039459 438596696 735721396 302546823 602000608 674473108 691390101 837457390 897939969 721233790 838802523 284033671 446693571 519858752 813774801 335003381 497770886 501284957 528058582 946273238 964018463 712135837 805058834 342199325 562487617 14323146 205875431 118822006 202828104 57468115 955641624 511657210 590616261 665271960 853225398 38779497 874341983 255030376 886130333 861945913 936005254 340098893 417824796 77050971 587177788 426264304 853935526 66581794 986855659 552991902 791480806 614844963 660055455 327283315 493761094 334805431 404505871 538194433 733925778 206083381 933070697 112991897 558994314 976958172 985512875 198633601 277150939 791381072 861573309 902628094 948864777 92034369 242583249 697602631 835951808 660500045 835786066 419968519 667855394 229271585 405604358 98596478 836543751 891700026 892986337 672865541 735079844 741763909 793834276 525641644 918311777 136921640 822578431 788164597 800119758 226589042 960240298 225130804 849533521 839163162 942554951 868512766 983718140