1000 1000000000
88529401 951240359 833012078 48946155 352968665 43403090 245696378 933877761 943848312 637786357 437129419 300022410 626286324 646774951 871742093 532048942 169908946 914470950 327426703 518145063 183883825 472041212 807239674 867535311 732115521 249677220 690571986 580031869 776289918 307730982 495366944 406271496 947980374 968642541 536564674 462218485 739486237 185525077 552510448 42851674 116495172 466629614 41450606 450089256 993712813 187009121 732537755 230139010 356593049 764074800 644331280 96798790 800454915 720060805 29700104 672801236 117910816 304924400 920675978 173770888 341843920 764307758 530527171 890472012 601331882 938465996 846179458 245969970 868557363 551652943 544579977 587662821 630032165 6389301 552202463 562934859 588718522 76693782 23035774 306270770 3198217 711447921 326659576 685432363 996645784 48822234 726467239 500114741 239263512 214415160 288807702 523395553 594007520 803508596 664610226 409781582 533975010 820473806 23539818 297585104 387699992 169394573 750185746 850188728 758231408 883407285 532197415 717921393 964431268 570697034 512886216 376978863 566271537 711907108 840789182 409584273 127341714 114893230 706735748 182197417 244693109 53329878 346562396 768905654 597587146 554741852 82703635 830178962 784410189 336283316 568832271 556515283 35344577 558947148 19016504 688727806 492855190 841601895 93718840 921696894 947597003 66687779 20378808 907370375 760113684 831685657 587642214 958219041 590178704 422924940 629314092 477346454 437606619 63590598 467826239 497640596 934431538 941504199 198670463 961791433 485025727 708305811 697453048 540545235 690554548 226869892 593670424 166138564 290355887 789430848 721348903 710951747 515346184 412150958 883376455 899105386 622375890 298501808 957120291 672181213 944266751 531111270 771468762 119931062 349000549 697985849 531887959 378145316 332027402 559600900 984869383 432573590 466786375 554224060 37518890 324284120 987957982 610505323 26764442 590159909 34140201 222045017 932963810 206823509 810703150 382724319 15389894 659546964 642193102 69713726 42513575 229893365 564107512 604939090 923277186 564897430 67090950 377080688 946736538 152424521 307587237 302151962 443607823 235760007 747178765 397996267 787323255 856706768 843405518 793883602 170310247 960742414 800881520 447729028 467586676 524069403 974564673 385665652 357248602 650385917 554734252 352800805 808808027 488999429 208665165 218116579 108836646 996457453 390073385 535757323 55380041 860290729 870123344 402291630 106323451 243083347 295258320 575640277 944354148 380881926 53683352 235649745 397691299 440383495 417682465 72244962 372335250 774295 557585287 715739860 27122342 615881682 888743306 545041318 495914498 587751444 910584475 879120687 363669163 326121652 230354551 887755471 728048482 993556971 870002817 158283559 505081673 144347770 335061475 691623802 328578351 635593810 688797524 526401348 144660408 437444105 404370800 92865324 973222032 165520603 401218413 493115384 569147838 232896553 865546566 393585554 279704560 753887020 720496020 244437088 342266052 328949320 527511497 597016429 751640249 586043639 563228767 292773008 16876571 935665879 87678844 569771482 536706890 108029186 372681102 978713130 15180439 102559206 645987290 425743599 870741034 941665316 41649081 530508609 674077723 511708955 692580531 944840828 723579764 115623036 134524966 995082795 340471478 11563320 224426367 723120666 764272104 34939764 380996175 383692779 432532881 457597704 965606318 971863660 356484758 568642943 435472161 727182214 31334927 110735244 224395454 224347589 676068415 725098156 384132152 371993006 444461332 753862083 453368174 575135811 250768019 688956210 491161708 -1 112289448 214412815 953095430 312359795 63506716 886079987 944398882 861570979 872171592 72172958 541909044 772399595 519640280 640015686 684958215 675399010 476635877 339427438 941671465 232943665 664468163 23145639 672755915 369302620 811029122 194585851 283523081 365600747 646480410 434198380 497371357 330609332 362705892 767628063 663086775 273842603 325992450 342039861 643264727 579665031 263682634 773486138 882471706 375080288 615391085 148639217 142555661 209309751 984912366 638938979 688132166 71577026 866093004 407753958 270433501 817595058 737544590 890707648 794390593 208326166 983342513 86002488 318766498 884381371 545969807 391232683 270043039 954211773 697565107 45307237 113360389 790967763 808185611 178436213 68843080 170103339 796937890 919979065 861568630 793010936 339783871 145477769 28943317 744057299 855305422 10906101 213224066 946981613 14788287 81224097 844320901 30757734 124768306 500304329 882580936 144823825 732833383 978253072 434853132 796889088 819614957 340837218 696396697 381214649 87635092 794646083 213690763 384339603 869564624 494908129 248405477 419181265 858549141 286879208 530876938 534680769 42658737 635019671 68146317 439785929 45697014 187364248 280399049 794132686 837045980 92661715 952063962 116697965 0 918165660 802999519 77306134 581938600 723053360 128775107 159119638 710206250 800614347 409602508 333573498 765571411 105558147 725875479 662061071 512472983 451073765 222843630 851316655 749854661 196862613 754862841 318675808 886078627 410979026 654845368 789925924 553681039 12153048 550677064 943318337 66148330 173708076 936633156 614855435 753055800 206611593 457996968 548312856 546015827 463372053 985346989 572176597 741419480 546914638 638893833 728397542 538387211 806339114 469256458 995845665 154470365 671799407 660528187 991938855 649177762 292092863 951730509 885063488 981200735 849979058 32068557 95203799 262109154 268524054 903250592 349457974 18053475 877043573 86257134 67619040 982012094 431154456 194465140 641391924 233883516 52012178 968249180 80674511 225176988 507105939 111455122 216354036 732154313 860634995 430536063 237753407 820918407 459220380 496121148 597687945 55730424 447757664 951397895 963330407 418831715 215168490 615218757 710483896 977171365 187294648 34592936 436000712 203802874 925208289 939582530 227015984 385764703 200633147 218612299 752457149 21677161 60639326 22976196 130977853 377992304 127906222 204609749 230190350 538201121 213066728 623006301 982417153 803339632 895009948 550666744 216336927 69314336 154268701 776946506 536539835 178292187 182090391 274134774 310362303 651834959 469914111 630706363 42555273 239313846 704454182 528656263 697799466 436631402 543698221 311127262 393209118 546370738 186199693 766336087 780953663 885310390 661488660 181573895 780722718 303764605 525979804 507408408 661056346 847871739 997244989 673372169 395206278 390991412 240449052 568841452 203126552 387568299 354062470 590940850 585117598 667221251 926941405 640177119 192228007 963074355 943046369 53030541 236134669 404918528 800308453 849951843 440608413 245067376 959435599 922796588 773081094 312270167 967082411 621209560 762653636 222672306 569958329 250176524 400417265 869055768 480001334 800252116 942927858 854114804 301639233 860408598 679724351 525783127 614792660 724225195 254280949 319633066 382209774 336556421 372776768 529235866 355111495 813933501 801082822 767567810 798323347 665430164 873774019 240835211 830650679 715968210 363098603 793456806 145807340 391423159 636361425 286836076 507796435 467683837 65848937 7500587 774475930 288914371 770297313 97032446 240311359 51716304 676945151 914940203 426364369 188745410 951814258 608846240 311459934 678853035 213271304 345085614 179911763 247858782 583495224 558043894 284133896 500476430 833298794 215687680 33018320 772476858 353518570 109306614 166146 653714244 866771140 796869778 832277943 753532419 679924080 919250499 368221715 26278763 914052881 618828352 901456762 480091325 678726899 983433060 845386931 520752966 615523877 250680151 483853422 214012377 141264343 367372083 846508875 29041030 738787431 240546422 4735585 720976117 703135577 697060674 72451085 987417619 423760396 212466870 705220270 298585404 70139090 130767630 58627231 890199937 817505125 649703935 169864482 594914373 378788702 165071539 952546760 511892439 7342973 884319533 783802679 509249728 68459420 587557587 423377738 296588461 104143793 808608409 531227380 74248560 983887603 968824912 412602244 189827818 79376776 889331365 403576375 233720012 544274035 59066012 517714364 480864903 985470290 916321839 863427458 891135635 307732609 252393832 478389128 515571938 76771073 449403335 691127153 827799202 484750427 509527958 449312107 809265411 894356739 547043884 717029565 543660923 278482606 917294620 970599217 290550572 328223103 935339262 982936939 982425182 802921143 304751119 97649243 520694103 450575265 190204003 851329773 58264722 622092078 527566667 849014209 257916434 824800278 521861224 348299994 393168137 441320022 591980265 137359304 719230029 28381278 948371509 721073569 901125520 817867392 563357208 775664468 254612883 186123000 873959593 832436323 74622996 332730952 400421407 990906224 249010128 619968707 363705640 678865916 351021252 665647004 721096611 116793098 378394048 499772775 276265127 555656845 581800763 529576948 852613940 706830405 521432530 345467857 721449806 583049646 511414357 260266684 169886082 927201344 792666434 930289627 457988286 689132697 45966842 729516292 186030327 154094977 936029287 961690718 493345534 265081249 962165306 743862677 682216993 382773432 970205973 301540304 735890431 423624420 849317850 50453039 167315643 924100356 187440328 564207383 381360079 956326815 762026531 558298619 320743367 481874669 699964458 116557302 22797331 558372480 528918207 732236042 394196378 710922421 65826763 686661423 459287567 153805732 666468985 20896210 25382539 45081864 435760502 277398253 672276944 666988392 818139729 693034270 853500271 754420550 848932455 401609081 17044814 486288275 797082360 207007507 705029113 756933100 598341902 570738125 841511629 212326356 868841951 568622138 488891999 189265097 716399178 517464645 425822157 965421083