900 1000000000
336137719 761772860 848197367 117180270 211920516 419863987 125571824 472736339 108391954 183803481 604899803 936593202 88891390 922080968 73567691 926128980 748554610 638147619 580177799 29873029 357876701 126995793 168276828 780705295 59375518 348986813 613184831 791805193 709664387 106245983 78416604 898318457 868018842 926613970 868015078 932455709 198994309 846103254 405192047 307386262 29906734 862608202 96495815 971314476 784689169 22579857 749959807 385760130 660727475 182653957 415633158 871120528 309649749 583909985 651825822 221541618 932896798 117527004 13346810 495077536 223772986 91763413 245912344 91791828 870893735 113927421 876763888 69888043 960030674 134472287 229790656 842453760 997080488 326286470 666284587 634286008 348866326 268760745 20046138 862110152 303931054 435679295 733230679 613580802 872105632 237572852 687638772 657518781 355099856 553501933 5112668 578872841 497781698 251025011 523181020 221191784 364952431 252461260 143596178 177499457 386933546 373386833 872469568 384014033 552189654 391270506 18300040 901055979 660031250 890862529 615682482 963962303 179058176 201429513 430059457 51163807 439002364 117698228 708682587 646618571 523716512 713795254 78007764 21498209 964820264 601188783 242689992 182289046 853650042 386286169 212304854 93099939 612189353 84774421 477113971 164379006 476044926 347930363 917951336 988592528 91309243 533633818 805071182 270367418 735063330 87646990 321531224 26582045 57861569 882730162 673200616 581578081 449041767 751208379 603076289 266378382 204913513 698282633 448667428 911079907 84568801 660972281 4179845 549274506 598263054 333810168 713653511 74307979 681740530 484121199 915416858 773049772 17755016 720488040 43417190 605334697 808135029 217464765 484433093 865996598 100194927 10150060 300091030 401753045 761358438 903167318 668131427 818788303 453966302 116798854 729868209 391051455 630287486 586564405 940325960 81066891 920374572 506495822 7891222 454631453 990617020 923308079 80197577 860888387 496312470 123614766 318739435 156963851 193595882 803172528 22960448 146307160 813322587 175567829 548060205 427197377 78735146 68707983 245985679 385217800 38023188 828370239 776269254 668310673 414934643 716595213 749377564 187825567 75607386 757268785 642457019 66224406 533093215 722654595 927112792 29405685 698785712 98368579 186369535 892381594 901541106 61846334 891205105 714863692 237414162 291781661 142061068 168665659 360489643 240563098 553883458 398512830 68933336 182669063 66823503 336384331 899264275 668717418 524209897 974871661 278502554 19183267 893612418 811595768 741837862 673241561 693517804 440623573 771610139 879887338 185521518 673151244 794250023 76726623 240531288 31664184 221024635 235108707 52846195 581514278 328188157 459246004 980027107 249637844 641915067 899366961 586022174 393695693 420600730 962748422 221083705 699103283 981931689 114696122 363215403 723769550 787937683 56733206 16909474 412064173 789136896 54947344 85215417 435903270 131673966 178263056 320083806 205214952 265888114 372930000 786729229 594076270 832176003 766756336 843714114 326607421 518639648 282252639 720303114 939240378 245001061 941386818 490860012 79449101 56082940 854075414 803218650 696536974 763324972 672644475 108601146 404978219 727591818 46332914 840881488 711782135 77112321 13481645 916997087 343000435 386411644 703726315 937076704 71103999 322999002 633307169 397711419 841638650 915559808 118014532 633395379 13077220 911917702 124255390 92526320 820516993 830847156 895744969 369570318 446688479 420905795 330687815 851666697 148497613 229537081 545064536 860279747 306649401 558546181 629793185 502166187 797474176 186035852 291759243 868578174 509034853 925066411 118805945 203189854 840626218 89336828 836585232 853703437 1254529 813356974 946229756 674287873 644204129 694491076 43858190 90892607 115396871 374546005 795075655 116410835 604083085 192656542 829206933 763248837 603719074 459000118 265415024 401193250 645035969 557174266 122287775 6587173 334757028 93610071 62293379 27899598 182946899 898878610 881603034 36717779 564751935 680349142 711005652 61472415 227356569 607380193 4881373 195269791 981926197 799957027 164196977 438525633 845129921 993403910 54290822 448848994 304920379 319705845 702558595 949956347 729396462 824846370 809059871 64153489 918456440 871353249 92053086 953919690 622748211 826172472 990637469 187500145 359037965 554159472 248972560 586394533 14056016 253853932 634180676 995982213 906327311 798377652 287024197 751457231 791781561 341315018 52822576 96701939 513537214 755381171 899174637 242933675 432743892 560750860 159603516 203716683 432104108 251656601 10152725 54852318 77829072 790193 94868815 289383388 407466016 196357726 875777921 421522031 450211657 362474948 270020595 209055319 160852599 409561144 960512549 805150512 750876161 865851477 754368802 116929727 473748999 506059791 359863401 906492890 66810650 519466916 962725924 351431109 623639869 972878648 258799779 553985292 826185192 353668593 843368680 86167559 550026318 571662952 507689590 852754326 934137899 630226536 61809645 94990497 39787679 874838545 752657360 643180192 740690021 507026162 760109918 66955371 13085952 119973318 973448260 932412953 491956586 788690536 283844061 115596454 761569183 542643839 522098097 440270727 748828783 365466776 526438285 151371452 937129727 34127874 4125778 723783977 516870762 65935422 671290826 556658440 793290318 423948185 52354983 386496691 783490698 812464900 453452061 649093001 784954570 279416673 581505953 129427507 68107208 717866366 97540312 682192742 113026556 619638408 122463468 861855339 985105184 648901753 13226790 774751262 535545978 17352567 351051591 52416739 935804340 22342416 461591531 581611010 298806952 513946513 968107700 82297650 178927765 421559760 731390650 963882334 700976432 165412955 93309840 621599991 883279320 190850151 303792733 996305875 810488558 278772552 710677565 648110093 927674304 723904355 275377707 315736634 593773273 626429297 220669724 382093965 501288064 534777606 963704974 800095015 48724119 784329025 882392664 80168235 58405136 466299666 44050568 759381568 484228972 137360407 233497910 220024643 180726909 537290642 68846869 843731818 816063194 779524434 344358263 596253849 355945140 619735969 764506834 949718412 98681617 985176558 184328728 599969680 372470515 550053 252581046 273710985 784879077 134973710 353879219 843284213 453789727 397929786 455182132 938018698 387806544 688680041 10559692 421049804 78487035 79406560 264781622 747066580 858930993 609139884 195836780 214876132 81392204 960343614 17110896 32590172 798036523 53955975 632559851 170507037 54506028 885140896 444218022 691901456 872630957 798097240 387702020 178937035 48543378 842884151 969472084 288866273 384080544 980031775 709916077 315083930 59438335 974697698 62150509 918369327 436353933 257987288 985761811 370262488 70847253 2872706 402852659 868883775 56828680 35412509 39390812 963851059 773069756 336125185 655752515 498217065 986738776 43454534 529670451 35282153 738855037 499142535 176664778 975451932 331690661 886580854 290535861 391128995 713794903 205202721 162014674 2665187 463190008 292836 372927674 534037261 3165541 775780332 255437387 912510572 663709192 147344550 728877983 289295299 483469734 237146849 787512363 322724862 133117734 169699166 210523366 871972770 668841700 387188143 699941053 532360 273768996 990476913 244177707 987563898 48195985 258708732 990229084 511385993 259001567 215673109 897939605 114683459 991453440 153376991 27194030 655162631 300721541 608588364 944457930 636707626 845735212 584486644 959432487 978852946 754185809 169955853 703342067 275543860 557143995 403283120 128592572 683429343 246276384 225286630 523509592 294472369 483995361 366255028 658374713 742996927 581928136 556314317 857680385 573381576 562207659 737390766 81060558 862929199 345979130 878034839 352153177 44230693 315037835 311585663 23083638 69223643 334057867 726425705 197283855 891201862 982225176 178392778 427147556 81017911 403679407 950657147 375490279 887674767 316912174 33864991 630671693 898840310 442695659 340868429 324738237 4903318 78259194 258315146 720348868 276754675 136349985 72502044 320985368 451387819 236604059 344069005 373127813 570661925 923011061 422928019 314380138 905236236 601320796 741527693 986254147 5000202 544701192 214260777 892674968 861613365 100642120 375863012 612970026 395854130 716731440 790224614 253273799 647506986 48539760 973622667 924261660 37406096 898641062 245247027 488793914 987761472 441832384 714438078 410939749 364843444 137366097 725319886 122596032 738686892 319363931 961366530 596203446 864065122 28143658 341394765 578194838 128785777 717257777 43681216 524639907 286505568 833905829 777913705 934012553 734961940 604052723 710790565 772368035 355210137 956037591 113678300 195487960 250386326 828116378
606427708 615229770 965482474 184263946 590342153 556685717 503627876 551708682 5405514 220209349 579852339 346800279 650920538 561154468 64058055 694601753 85794374 203079974 381023934 716224430 989608879 115985873 172793505 700399443 740870260 380519993 508953385 854548559 576007952 759339711 682664936 182435660 227085832 500663761 366699605 817427984 909865830 722843832 221653017 915271343 943053180 654021707 262071621 446490069 215176174 178646027 141091822 153486899 234242353 374632107 722227681 223851231 343134331 895021185 776767025 84004590 128057529 138236761 791069501 704065480 897576471 326250788 886501139 977178654 826914549 105717095 647122989 589296730 828560926 868776005 504568072 624130457 375314064 619156045 70620526 590490237 797802071 64228699 596493488 32044423 291377157 318721168 108412005 487027839 66258704 885179029 423548781 194316232 23415790 214618281 898381711 773508612 540869068 637399202 603203618 220299968 595632648 250326606 809596697 276709926 971618963 166681121 900840382 346933026 785837165 823977259 789939614 436155587 740722309 386433101 320716362 884615817 557670620 281644718 371643656 623929323 19340099 795192436 670761906 42755888 862327068 421659969 668780851 255712487 59059170 124500820 476012455 507208169 374827426 138125503 783918094 198962740 157322975 537274828 545895765 943160139 213768438 188351730 231832078 954490747 574784831 405064791 691622915 132455450 686709508 63266570 608901125 706049606 710975357 132179382 601321845 425818776 553839350 122619048 681531263 465414871 247119867 10060069 972623040 621947292 148185571 756541133 820910031 305508546 146332312 219322147 101185036 360100750 407673877 185533465 167107848 834975059 590598255 858730762 819946860 277307763 774513684 281364336 983357368 338005392 413543718 437195565 763824168 967383067 559814612 445355430 432797938 806934478 455415498 257937329 281398122 456117420 14478461 102308152 761625965 13327125 174146651 715327353 373427874 434336879 900860817 540535721 269311937 491459072 399266482 89258796 621283186 26296517 223139484 457156905 364301909 636683201 894352469 128126076 604066267 454167080 425997857 889380556 113617910 881413354 147317884 395016031 190047125 14312697 349840534 951673090 27639821 523987184 519516794 401067694 958324062 420377610 941603414 80152350 764353033 193386247 21927498 385636218 219682764 245066981 842793123 583984672 881750181 589661943 564627099 338332799 43829023 990624955 80229707 9963284 724554660 227547590 404979314 914601784 94376638 754819847 718791225 122016458 131323383 238308018 375600503 89647444 511201980 169720268 22316146 275555012 363106515 44243643 513707582 435305630 141826975 209017056 19290301 876093507 798678998 436433751 66942657 695024372 427058705 147172363 704987655 4129716 374719953 109966968 918731499 469096590 864786815 637522724 443629400 996110197 728347093 819229902 938273992 239549072 988950170 813106489 367620436 204573036 709866483 881328017 639878665 851693457 90345072 511685317 580303315 889024069 948119067 647245972 436564793 227694123 794418334 141552447 231823838 21654638 104035767 150555336 490751228 968822581 640594411 934380627 817449129 368941504 606126880 608239472 461006927 595077049 273862313 828627362 799650084 983728795 709955378 292045100 687938604 652816801 803730416 268241918 394357222 751849482 915487889 830922014 979543604 562422575 972474460 63883793 584077212 76510226 214439129 74828439 897849158 855033539 861725417 567814638 76491394 320368649 28570462 537498321 915445697 302432774 218642034 567612133 138677920 928597412 859657232 826616523 433930564 515904000 94858441 828287785 120269833 862862681 659209798 99813437 277801607 484200610 16213581 861878819 413227187 230652709 789223609 163592697 938202600 503465378 583923686 14693993 823834026 612494147 404708665 591796074 767443272 623350699 11924558 906121192 404464462 871581790 732737714 838395025 240002141 680112506 519199162 360271973 395491539 30925311 312601761 673293145 515125920 328815342 387688315 780869459 559468050 176911924 944462155 350187001 680377301 380902192 217397346 356727678 993396339 622106010 948523751 613355962 97973060 960448309 519477153 354953873 684546450 104731219 45865250 924548590 637360076 565064411 284820562 32851614 595989721 597422323 558661111 111115641 926237664 946349425 744501451 338222065 975777700 541479957 688409066 508671352 922382148 905806411 865399029 768294838 380428772 813922780 381650800 330918184 626887440 753644304 685872056 311433889 858375522 731737305 88498830 348251950 296801715 373319391 233619915 892791436 823258065 792281025 856423428 602012080 591146802 453441230 940234145 419440853 994921186 481159562 928112205 917303333 239482324 793511233 538114523 472427447 459950364 919765322 803345630 86837803 525925977 489217686 250788043 236817851 73471342 339286872 585069800 370273057 565122615 818689714 115580844 388380679 463487091 824520623 990392759 54633892 277961852 783143255 326591096 125399389 116819168 254703300 42702721 208817843 900730885 433333595 681245289 213197600 205615268 484590919 152551755 731541245 826324956 403339797 968359095 899796297 595143021 553428894 122585705 160265635 224634959 238166548 401162665 688122049 62687170 244071775 595272292 193165373 27215029 921863388 318564761 996550548 29083039 213783834 205368390 929813923 647117428 886613679 143011523 852732696 223720949 295563277 436790292 50045904 551419425 405149386 802358552 146562445 811094631 924944257 159344431 35729589 15627156 560507096 723851638 78314326 804578870 171640281 123996050 684310251 93503668 295077163 680860798 122586707 508860996 738745540 52400629 8494775 477875570 47928503 713743822 701596518 196008131 150534113 604158773 747427556 408199850 259033676 893990000 219294480 183977932 53334431 107540421 199605088 466357878 831392058 130435765 270936747 3032338 106948166 955246997 949052358 402025328 488624147 71639064 910886323 79886038 976556044 771897450 557761607 877000899 485641271 111874476 73009029 488691736 716033248 820436584 896891585 975066923 566942936 116186065 11561207 472793718 76242837 63682646 939151595 907634894 194118410 62604693 763183583 301066575 870368042 564752292 703091903 211508540 488907707 466494577 291394577 317980103 90908378 849156183 194981001 576549649 961030658 120506381 65241384 529580257 940942965 814649320 357163531 360402252 783351736 368724737 685712321 859594572 432407382 477380267 619745817 479042143 539984959 235445752 780108718 262869352 800198043 335716972 474377891 289105750 654727900 765772467 607085852 745636278 614928649 654583204 174702278 428475658 775089584 92460013 958055914 568548900 907109332 315219445 928951151 690461068 536460533 467179823 402571991 968867915 944560089 22317808 300426409 337061400 257763559 80535126 599930751 57961601 268768449 74308642 199583702 923496349 840081108 659185905 521648978 307526109 313769108 696351255 736001766 88858692 788811267 546574032 509923943 695920598 861793476 291391446 238898017 250770360 758571268 641470008 72154626 703131357 516304167 372581035 40192756 774067725 305632512 492639858 684545677 574400961 566948499 736645731 350413661 259545959 395831635 872062638 419588419 562117095 420930244 8106536 503492138 209741510 554680567 13416080 758178459 268990394 304807525 997076476 519760754 63378793 491062835 591915379 619026501 7367001 964496413 511735608 633951077 270128925 4375465 171013105 697046237 423840316 907658835 47459897 535902626 156006822 772038886 955491044 718123916 45485481 963597579 74132405 255226990 518278146 87548484 13405448 787268539 244872361 862998275 159545644 160767505 206577461 751461023 779794005 66460813 715957435 144045964 552928241 838602711 937780 723941346 535648947 277294447 484116532 435625195 813197072 492639705 60180432 768688115 63279972 105665912 584802046 137412376 213409253 103080191 224960860 79331053 742865081 469833220 942329327 902410725 630600724 1423140 506388099 262911080 67883952 74861885 259473395 473328545 913464596 260411174 49786242 301629894 537705621 533902773 737255089 203419044 26542478 649951872 972107159 89822449 755617784 409425556 79751177 969027036 365022098 304712036 48358088 107887178 627061607 843203767 862814254 110178682 697143258 221718704 373089761 617543561 296580589 632563155 90872105 210045184 745490680 140658346 511675077 135712652 527077471 101446517 339131696 406136300 751398389 163755206 348475100 359532524 573180761 428226276 181075911 938202858 732938311 81950351 898606387 212516269 777670469 613936993 322694950 474813726 835655696 695784710 92357286 132236284 180864216 35745743 194797819 926354896 28920440 706472896 62067547 555997910 660435764 253715594 962134209 264350504 417470799 310609309 623883027 990651559 738835584 657475290 928854416 324290247 739425640 679977155 536806515 369612460 293914147 859501465 844426185 129569842 407802526 789299822
