1000 1000000000
620984499 901640252 783414653 722449838 191115318 789380590 382880915 860390135 867659735 513596911 887388485 784507776 314517996 219413371 210773627 475836153 307550193 626616437 507600921 48906230 450000332 846319765 898692745 637815205 456016848 3918072 631514585 283837333 309258472 768560699 706972373 919066123 532834690 412190659 986698973 757533736 605397534 347565309 729196764 381505531 169947037 37473683 477052488 215737509 762872496 603163652 48294201 943581267 304700488 58365820 806713248 449578403 86748464 232685703 335194707 563826974 221267121 874965035 777883928 601538662 961775699 25285482 45814580 860258063 227954120 122511140 578747432 642469588 84246476 2713822 52844035 818532335 487279807 543327390 798066238 696732119 598845774 599404756 816080297 796950457 578676121 86656371 682332733 966189777 126137917 106353149 739651236 838655457 493662015 262741944 738883931 752668822 835714299 187295910 292808321 773517377 873763398 420169237 4350218 510650950 610823129 334686900 435053647 390573677 556993701 626400433 684126731 422914298 866788713 299491318 145291204 316384630 159478379 425738126 343876580 302218291 11130345 443571555 759448689 423329008 289727512 607583161 250262475 740987404 245866000 584617623 35513362 210418331 605608092 828035584 24795772 50014382 748166937 300072676 372812187 709885562 618125729 565369649 700909187 718936059 586446 145066809 816700928 283432582 337661973 961833098 939557184 501790397 378066961 514260275 193801091 325877023 690178617 571681640 153297549 797267634 193180262 386665633 168435163 224546666 535914029 929012884 56870616 497904777 849337883 872346844 182369407 818946906 390828780 975862744 259298359 823976919 823378802 979579863 842518120 591509262 325976553 60766053 930723976 897324897 413950669 462685165 754490558 683489466 892613643 376663763 564120178 995452179 264425107 156157124 287284474 136728679 709829413 843383076 82871897 293423776 477555009 720436777 840604463 723067472 894526309 150544908 544382495 170939350 727261666 238499807 52391257 947816303 886927148 926484524 439239858 38942422 541121710 307473901 803469511 121685098 258699382 276870328 492570540 141495550 798291051 219019758 329257181 9930278 51690613 284459718 623594892 774757064 445393437 795160015 861269426 139084616 656624736 765497354 999275749 102801752 958267182 147623477 986692732 324920609 111320492 182332893 908940982 39546861 148730512 165229037 224681034 713773301 903145994 774964914 278267357 496055495 676763544 912485277 990106169 66495949 204749146 700831103 13201006 697184941 637511723 636814273 383553806 786691676 711962794 612670771 843842225 794017257 861949879 281543487 697774749 404434632 11144971 230492259 962393674 204950309 731258594 594048031 207204556 965486681 616788573 55620550 327067824 36996690 634089429 20823969 198512347 272368325 485378852 117942891 678893409 558577468 818860788 952464902 163410720 189517118 954591020 482072779 414656850 83565269 533649798 978206233 782207124 455752735 668254989 756559171 236920156 546305285 725314816 472728838 224194575 605453231 500524763 578229937 918536220 141745273 851810683 273700677 388893383 343091789 787354569 232844329 61997309 794960017 874151236 271541492 396971391 746606478 410896789 457337245 950372766 367967658 958045615 113483345 305461128 683177600 601442142 516835679 670297368 389355476 798975267 10330100 961668430 11736807 829203925 124799990 459844981 111545266 655321235 985862064 365907836 185155386 935141919 864341366 647812022 264472145 734771497 784649001 660089153 581705316 549530749 643780982 888951915 16432501 625949205 772880630 622884684 744569397 632770214 151343794 693437100 543235188 949321845 73910391 92129816 447984313 603327048 549537312 495555091 929298759 506991365 211979958 82666515 406663416 472527244 831448601 988997294 552831007 974634241 667337026 620898451 429136571 845471895 124477989 259770392 623195007 361795208 127894894 446036044 389136757 471952214 840760811 657612462 520126411 704368372 157528238 300266026 716083797 1600599 364041666 388096784 876736679 36569192 801690848 511642749 874151606 968925631 296209452 685408444 325740627 548265342 892519270 353304141 200682088 348062567 603317564 813951182 188704149 896014005 964449918 346629025 769465686 623766284 215378290 385688300 475868571 849034732 180882059 933515658 77300760 516263848 615567094 768053994 315548568 317812841 206769115 604280968 713623153 116132096 564275836 171343261 249279147 783210957 924527451 581386529 788580513 615937103 457360163 2220818 643557721 936677410 528490870 805768144 929894723 656649271 583644207 622381212 848015730 818152367 937044066 37317571 44069754 24701047 65795601 751131997 215532897 620583837 535966310 631182683 717288652 740571063 904581230 180400909 927762430 571727836 65679049 820871298 636499425 515308988 167665133 338077474 195298443 996360191 627020765 323418386 163684110 475846614 1573848 277709894 869657671 14585113 942742585 982691878 185085090 740426290 115081158 380466444 882906330 468132720 925067141 895352392 215928512 406254313 232437176 276025994 906355413 94989024 14089163 616366501 49808953 309698891 719218253 659519528 485824675 504514369 332556256 864251743 690747183 546822723 552677077 902884576 469784439 877261955 730681226 166193235 760889066 518780458 640388034 667593962 619626585 282972684 412673638 848322982 410928602 643852735 506160611 892280266 544267406 300097221 175808616 591409294 333064565 36126583 130989136 528066981 565317791 142706956 185703757 417565529 263583696 524193872 733344160 718621104 51653218 353195955 453604447 950698752 599895835 38123092 85984230 795279080 224339471 144440928 30945783 618807065 634277278 948205087 728210211 398076143 537967073 966702430 49926285 950401098 936123529 456381804 449380867 209940777 793771661 663319349 575878763 58474019 453937332 274384851 367335525 579569954 291687269 457355915 606730103 318866175 208477822 0 353644657 653961075 21570388 609377563 398424745 821132383 824392504 262182249 171069728 422639157 996881689 916834303 783272219 674940427 519536043 951993698 53614754 177383938 540194510 678262484 729696156 551849316 404691757 151194593 929946231 548020780 497431361 389723580 488521688 517470008 235998226 485053026 630302835 144787955 439339235 237995924 215859445 312725901 390810386 780830593 520119986 265266409 200515284 776004509 221359114 337208653 -1 603510975 81633474 830109249 240311645 596334987 545695163 453324224 438784736 668056121 880139869 699375993 334874499 113521835 849413552 439326921 855828479 599067395 985758226 356737174 77986733 789790149 560047166 137770429 576587283 440071448 286136263 810546130 700351906 756595047 720751951 555625110 374922883 35530783 874956426 492038194 447809359 579436214 22875243 267290205 134967890 74568296 295055050 991087604 624200249 322648160 147017517 626637638 173651582 76516057 513592264 536008024 656510976 717740550 226299145 233540055 91192776 128575486 193464953 660404773 186414586 604863523 832360010 35085325 135345886 905906365 971984468 233457609 222056470 282492008 73649648 117179288 919891381 64795292 161754452 431932938 175618733 877987418 915093969 16856532 565415135 932648637 81216254 903442746 248566316 997554849 430266150 842816855 663211049 120345315 265068117 836698013 166025733 577825519 3513841 383413335 820315981 927838127 174241083 948565911 894717841 570113527 426768613 170375489 298724979 214343511 120592868 914643311 968091585 664174434 276521775 794168967 67990440 978923996 509531648 614244796 372606128 954994598 464366924 409739251 272183465 482291889 279424407 908579348 91760458 608965380 181817033 956698385 59926751 61948403 29225625 642298028 292327277 621033662 460837263 433465916 1817267 618117273 528259362 615069694 604647532 723887646 479368594 50759440 603853753 59869223 674447334 966243089 147106799 6322930 898716278 80520645 883869688 716416424 824930312 708742247 822265542 146744231 711525022 691599582 679618003 629039099 668653654 307833441 345635084 777629874 532042330 304617832 455744875 662418736 393457429 924695348 396494392 278398807 397237070 61748921 879894046 909751230 574701676 679821499 560097947 179467659 85553158 617461061 629013045 398799348 738242459 250623291 913759573 444876849 736146952 766669752 356107955 611039039 64913952 71771625 415927692 250463831 707872430 535702344 935071271 107277298 759115873 310255064 575236321 577116506 68284627 329425022 347932397 938003638 944346290 450450685 143913135 311708394 787965570 192065966 925836437 777212943 952885004 63113764 337060441 934501765 960190774 683106805 516598306 173105489 5454984 408733931 63857474 434015325 957725414 40954500 790427885 360471848 353915273 454625311 290110402 664694345 440982137 227134310 723877607 739797629 410270542 182359606 974454149 440864576 530194943 114628256 519903625 953790334 616776619 631705308 807823372 295583970 900993040 104708712 683356811 65108375 30968063 141524765 323650492 632856357 649662736 655466416 362477313 956526327 51899841 642316833 677976447 423815865 904350629 486742344 135532553 166487562 936354562 213338632 60851668 385484282 861924222 671446287 184069095 631561823 7940149 190369834 437610515 923437667 902562541 804366462 974073651 443452706 738481510 992490535 20169547 356361855 731775832 707066916 223923649 331743207 454625473 736899107 73997643 356585443 642814164 650388969 537279032 247920171 910745168 54173237 224906046 446903201 775387744 121075164 788631076 776576726 691326731 855035808 624021816 487602768 776466519 998118345 290490285 509021017 107716921 7842253 994212825 343380114 659824539 408108630 760957738 179882838 743474846 182526214 735626053 163622093 142030210 601383108 937276583 405148504 609984439 462402738 649248976 407559816 547409737 73977115 437656862 85917907 404354040 693242954 697510645 768874702 150358103 418892768 639090452