1000 1000000000
746952166 866874672 844621238 644973343 677590750 953814336 656829268 988647141 712809507 25876675 598360798 234938560 228699926 138681392 557685960 986376510 42681699 543124513 199873818 409453155 548655234 634656936 350151464 442340604 641973830 913752679 891616069 206271848 750070175 556539687 987037219 496155099 980823804 -1 414505964 260035255 974194459 213885725 614546992 426729720 311168916 905978685 481843084 196629579 887530197 480360208 753460841 822832808 34191377 629275393 264800301 686167454 656056792 4543016 885584144 851037426 963268388 993522439 206518489 956880769 969421335 173914855 816201034 798340187 109190708 234195233 163432131 603483964 119254876 224516081 650027298 863234530 701872612 764039895 402288573 93192006 455869040 957120988 771162676 79476329 909774962 154552542 796839976 600375008 46734210 263584716 889125289 82273038 668429317 889942067 12338981 961894877 685135409 817762952 638243990 446717687 102347507 534392011 702631932 421692861 933254273 606540141 78733729 207113830 610710331 20004045 843199250 858128659 978894266 5236507 590812135 309051547 126770253 862835198 819293449 338322906 805879602 705153472 757807085 708245581 939370006 125923307 761048080 506763869 731440288 605752982 913939064 779055558 514168488 496660091 884845321 850610553 271655852 603218651 936717590 338945892 130011189 636533925 825937788 821640197 609573836 207373740 291896698 490212349 362984299 106775441 503810793 432940480 908316829 957934231 126865879 671786709 737146196 129408255 185312431 19430342 283550482 825779294 892281783 832336102 426932282 424190721 236638457 713374858 147216340 585480341 259806939 281527520 469139427 625117829 764230895 671472627 982221149 81551469 811094946 346352079 985803848 662954504 761166243 452061719 528873692 221652390 611800093 438198752 515777216 567226706 189109767 107510693 892810338 844287348 503740146 289088212 600283522 619273584 90742063 337267501 259685910 945098809 106690943 341637405 763845131 760249817 582770643 929972444 507532154 623406316 429129525 385829448 411674680 437043182 720721662 743055800 797743597 338309905 410113350 256646275 767170636 369820922 234668828 51252607 436828397 184874407 975923833 680392850 144113335 554299688 436510301 177161690 256824621 816859145 559597751 512298774 437404743 908442392 396162380 292165005 416716838 370683729 818339421 851520211 840815435 744527046 999466955 904047243 277836902 152862961 746538701 220661242 493233190 637075391 374133026 71645949 687577071 300618990 281920210 596008562 582580032 200519694 963646454 281630886 317903521 60227451 925816407 386149629 986629915 949272790 240498865 611882026 577862214 157845706 486148818 781248530 235775615 284133785 441181603 86631359 576347765 386449123 860512943 697871871 212800721 737757429 628911973 504906376 684250772 806991852 589418236 225511737 94102882 431526423 27991468 704221029 860797708 426195530 930248194 194629758 73327777 369989932 53740987 318808160 445010761 558985680 582300864 558604652 205388070 399156750 739678267 141352897 773467314 79334040 721572331 738458629 786304777 611982798 746006478 227813174 398713359 539912472 795990408 478661309 993978142 255695793 607002328 236844816 612303611 136679653 702680682 299672251 200924732 280327100 387431208 591766080 358415641 889098284 516673931 240615533 102192222 975576502 528112470 922104847 304754347 379713580 375373315 640331893 965319502 180532775 654227049 222841515 433114952 640377373 208834973 163174350 453847633 442139662 613146607 623249759 746794627 431662488 196279432 73324477 867948843 492325047 278626496 821813550 356758873 367157508 67535669 360279133 586164705 89195010 671725553 411723752 51320156 260235855 848625748 75230055 943948086 282560038 358234397 778429424 996423902 292423540 423332851 467652538 613648396 379564643 93383868 58981198 258217355 909159171 419232792 914540104 729442045 894351114 986833384 173471837 541714942 922232205 814293831 315207166 186377077 660445537 966866035 874063287 735744378 211279919 444309679 870549333 79745758 345568648 396453780 948417799 298890262 25450682 78625234 220767971 366840572 744501580 532778835 530300700 191729542 615650030 981967324 680782640 315471730 342029367 425856490 600075382 514288168 566062348 196500753 706363552 448044539 442810598 894905890 32103627 178920531 999342107 480124904 443541709 130543484 709236698 327407969 920179190 998249641 908990615 418528952 725915417 874229719 265559306 244526105 342145251 55098554 85306802 169217720 167006807 187823977 949972154 342096568 482836034 748862404 774285044 378954402 828404376 36228172 254232070 131723193 497265284 232434725 177700857 700719813 676386826 41392671 678909976 146751698 85298785 215287597 906463343 435946510 466755882 200512229 59403729 851640377 375379042 560198855 880676311 82016368 447804732 951610555 868016376 488552132 802640694 695927481 27148419 110160777 582403467 922240997 296883017 401092593 960172487 574167148 89879594 985548148 0 778340519 51588518 21434910 244792128 278690773 303098441 124501655 62959791 12551797 716243021 508262577 297474464 209803354 287458489 130483235 384121925 90325027 478815276 618458019 771065227 570467234 305624942 185465598 690115343 752399431 647033338 408372038 752210789 429733936 44476467 745990675 652495854 712897337 469629742 982543152 179233942 901519243 385242973 625293695 74584582 578687454 972772254 637715015 688829340 914587727 757209145 42255735 783938171 77681767 300996799 499367166 965887359 286337013 348804070 712170497 687198631 796297608 371236965 397038337 419452825 630046793 668387194 878576225 467529972 251438184 190219229 370467728 877942505 878275964 477329781 863983347 464824491 648136755 529811220 705378212 591302701 302112958 376424746 370177930 329693947 114672285 620377978 983331546 518186863 846258234 11508130 777149716 341198585 824534746 374789567 490880005 87035679 414729750 595921801 21424912 127946696 837412506 191832853 488135898 628000520 50476811 176538892 148997360 769360620 834961233 900125261 184872622 802114995 39484499 65701348 615690474 670221549 632036364 548452233 582458633 734679053 708062274 195608945 442975381 315467061 356941222 723101218 356490866 472826516 129047854 476240752 451087617 99940056 736552701 234202244 57687559 732950107 815935355 122963291 136271893 214505015 198110464 730475074 574806630 74882533 619699411 121192800 629205644 528933283 28291679 70978174 790100492 566464525 35882376 70772282 866300722 959116786 799077464 907434559 114279303 768676544 278723297 254444243 680584159 294571281 876845752 898568499 529408473 478250580 432487385 594553717 71326291 199074543 761850855 153022482 378820207 269809637 348224265 531794259 109251341 964533863 468377834 169135272 274454785 708574130 949522239 123333424 893258632 848881657 711953326 248354328 736342661 352298524 800874729 401882512 54337337 268333607 941484348 238990140 381832924 868138681 453816976 325635252 249197021 655879162 997504835 258718734 553918052 424706007 716158246 319828551 234554810 915699544 176620516 584967181 538610383 713629441 694026564 932757385 429350482 1698504 420977769 804812434 280875152 62845193 938408630 493795788 717419343 346778672 102784595 271247220 177426742 482605231 27376208 480464126 586693603 120067481 641854503 814924847 717106651 780898849 413905141 686135030 894962445 38841459 120700705 905937052 122942424 301322488 154322874 235714150 519811313 883329773 298719314 732148669 69841621 717854947 912902938 336039328 849642452 159439198 124852995 150190561 81967669 127899209 228699052 28023148 555519400 205316531 298553858 859783085 119059971 377598176 23918468 528284079 489320013 215313135 762304661 956758230 298359016 219331583 655351610 834901265 3261342 326442380 886354812 394502286 575524616 889122359 448297861 535045834 572087906 95085391 841045961 550610755 365650290 399537032 244692183 887037932 528067728 157915599 937230430 509303711 951533298 3469773 137147359 479573353 686319014 662382753 297617006 279566731 163371188 299264298 499414189 625952002 452471670 26422028 121888511 278529606 571502253 896828397 107173043 615289690 846079979 946080613 488102285 28691848 488823779 581030018 986741701 879321694 950525912 626711691 784523409 529497953 400474941 708345676 133345116 402982416 615116121 629927907 997188419 607845160 859372217 980931334 499351675 772835293 342774452 781167045 557831060 571968469 126827411 96116699 632496299 794693015 327954229 23544840 321337052 504428791 553240032 830876678 569604094 90844182 113746659 140133771 656315984 285699357 176360588 368603125 934698922 476138154 971055563 324539005 796868961 604469008 946347701 587321835 291259840 46695632 105487258 977523907 389253578 372615912 337918174 995992602 158991846 919906362 165229396 626012060 735858437 594726633 815789200 463944960 743265369 898017372 868235155 954689835 4301996 815366077 978732160 696869044 5224703 224588971 748645593 383329273 279525897 52488567 132051510 684688846 42990619 423926949 586974313 321462878 690635499 495467564 360542529 343462159 300962744 393838413 341622378 356957404 554690502 694868666 777703302 477802976 230894629 654274925 684260882 560223767 891374153 358156761 302077863 498232736 288107145 607322921 298273307 941031637 279972022 224451219 997252943 631651421 563874284 725882715 933407882 487813399 28501250 846479322 348105206 967998559 509839370 41045490 246150316 922683901 637684792 70202586 990731037 153691540 695997155 695873998 567939992 815876828 12390887 333937103 735819426 212750558 38839405 808058629 757469542 287283609 263575238 826263984 459933358 726050242 918682099 983214979 894317154 807730928 708949359 909249330 569637220 202221692 951991188 492162263 255824369 324658221 836179990 401470012 414166194 321675304 300481663 976239342 102205302 732505166 902385834 971655524 364607943 602074043 342141514 743031189 564143687 83783818