1000 1000000000
793340083 821954042 485034627 261621482 451714 662818562 470254257 759730635 373160372 770139835 272698085 801915483 729824832 414006441 538305219 682051741 192984875 553615165 805124049 265521054 803365309 685689882 844282324 335582017 93134592 800282719 804781513 445212414 93780374 197162044 634918852 291183561 951373003 588569796 200874319 655403993 360379565 932737215 909511202 514651161 644571810 697910352 805504921 976375005 28421980 361376421 601747240 304324406 589156740 89687462 880078842 525263184 116824393 662741171 312280660 196224133 483744280 138105545 209885275 865539199 698223743 12522698 778057509 17058749 332912061 904437852 620265257 306124526 377404798 389165582 126834725 999878596 53822138 422888655 746313035 397764296 980973530 245311042 979256034 892256994 670217110 889512549 447194164 831259514 796098836 516686666 470929803 705672977 409063763 85930877 746515890 265819716 487663997 784029274 172128103 21873358 123495312 589415563 361049124 256312210 451533245 927597109 254763401 410571604 879293862 612177159 267937500 474708927 478538986 142185015 377478111 305673529 804740983 323390248 659243152 970766081 923078377 376042795 603031421 320113008 398281574 487998744 793439009 936612366 290789764 6192308 449357285 57105043 30112658 773572888 112141658 718507188 362011328 938440460 853491631 62274850 192631640 947391392 613432437 422111606 782291358 813513826 491694026 468899125 100155021 361972003 144958627 625593559 606580162 144276283 628007409 97322223 105431467 645570162 462713299 899585404 629197381 701370466 127006617 832663334 83543577 618121725 911398345 907729408 893294637 451983850 693800389 791332480 137072010 943401822 908774330 440886642 778498019 447078664 276407066 712478820 63670149 800198758 978076922 286070669 939671367 83681758 858078787 279807919 966220561 430696714 922163004 31913121 85643427 816371616 638572642 535501120 32712748 173293153 370488658 52065871 993040127 765197737 949796946 700686107 343478112 77594810 731519875 114035013 547125534 464051036 494530742 75181522 73971065 520266823 30475714 525423040 150300407 281706055 151001703 568436815 388309223 223082243 221595791 564057176 910580382 419131090 163183895 316498778 240333568 572363257 786418168 568915362 188146224 325263141 381081033 440943464 397511212 997520532 551058842 662075118 716372417 645143401 805257840 372224049 666559339 972582766 164128576 625464477 384698749 61067238 39871442 758965604 114592281 711044866 100146276 367615391 32180898 542755903 786407794 225578283 565306579 922278843 293498151 471048877 724148329 864222951 168612047 661358486 120058394 112223630 983248734 50012802 919800825 750113255 675936870 729440088 650964675 287026459 443372430 202141678 859269914 778810981 787543137 213958295 592211179 254943255 790535135 744774870 995113171 708194426 683888519 777016040 93678888 595364478 32741184 367140469 117119366 948471998 28013403 921316725 947883258 435627838 832464717 51750312 139399342 9828242 68087745 2580333 828331271 87521185 590734784 273229235 132379912 419216532 181842850 977183123 383904203 593819196 563543912 626869565 480435378 270152280 136773171 888048291 192531442 448419839 808370517 576058664 948075815 809532292 513568238 119911798 592696542 473695453 861756726 530796026 694260191 811616255 470445604 841895160 899349357 154350115 919149595 869743964 854996584 337763744 251822608 132830778 370987956 855028664 362883882 5356079 304923371 82530464 622501482 768236184 926622551 89218677 380402828 125860182 910416833 836964608 519805043 954041451 520278979 776422530 488055198 364262237 994412737 841701892 591681662 867226334 649442729 797777712 66723296 131500102 109408502 603113842 719658054 155119037 505137223 113596281 687570547 779027692 86669207 980009576 664896747 124878586 351039747 158249169 727963878 916742132 175133108 184032449 628882006 859502393 738956182 457767178 110511993 614123218 455559193 803776131 571903678 733984262 971098015 625987814 911673658 273960134 1533441 882403490 29875833 993635748 455744820 61283111 274658172 721308112 384071193 623836229 101930310 835643558 373152808 832775978 147306802 667299052 469014240 404420187 19333734 531711741 838047147 103875286 445764589 12455619 994115031 969509200 678414035 480108263 70377718 121067728 705003702 794501792 989081494 861725771 437915171 255293636 541840119 345905559 544800063 884066211 452951129 981211303 718356853 45740325 746868232 661540403 622039116 3287900 878893493 495300453 536784181 170268959 35435403 13930684 209852729 304152862 154014291 58212833 727405855 702487289 882049734 217639362 728405931 594477735 90104422 875001086 357287783 184935311 183276992 924345445 220768395 384316994 546989423 359149255 655974266 87661519 429932848 584545879 618966230 608959074 269249485 638159617 972203448 482448590 643994022 836967330 252340052 265634556 970228533 300706459 426089642 370935120 993159568 545075084 896139358 162448971 277627513 649738963 318263358 663259796 507720955 78134102 111796357 438605773 533614457 176569943 263172211 1197919 265929272 309227588 388351167 593209197 852702780 717324071 740762398 282932235 495567541 726823033 893797519 240430807 15053145 50880802 515366781 872237871 153363736 783787133 641097416 863830966 901051268 107325660 793707631 135310244 118713371 398640254 488784523 69747192 275663158 175488411 134924360 98826854 23763677 217549462 327280945 419862329 694445278 611982595 487803186 322889469 614646371 192889621 177339423 112977953 669254800 139279361 222847220 351569618 563960855 647541592 592328532 596108137 192633953 912648605 737098768 406878927 396553844 577017707 119486182 644173182 902907120 363947032 498987575 253102540 909577566 376682335 360634971 712700907 372471105 904980533 411245052 589027361 304913224 589405400 472211802 104050505 888954271 160414959 575768630 677159629 468666999 327642918 453652921 999543432 11896236 885052242 607247114 481070447 637820795 639732927 830297557 976538522 515127811 351295530 362446577 910615318 480035763 70608760 586657185 114923350 346755555 650796981 612522585 536487044 829540639 608428817 970224424 811491116 264205394 781515996 360981693 945205532 619189719 418124976 175010185 847904293 352681130 15693556 803176970 6525686 44699242 30389163 644606047 562097574 483491333 934994085 470462517 205713490 996477090 110224241 49638114 222781262 976536633 417652295 356869775 369628013 370389623 755675180 637955752 279381691 190392916 816125198 561526842 501714514 200798931 976510762 528513870 918255165 673897060 638842418 24388029 914123542 854585250 76424693 81638441 675199848 667704923 193046417 990955298 98845798 568904903 481948263 330193801 668893696 440896847 767185344 770716413 9341353 326215991 542407040 296383836 600181728 29134193 105107429 511935896 215007928 207696137 413010415 594306711 654151087 598561867 498197846 433396249 869298991 863476608 898420238 943122499 671742965 199400414 701730533 282797779 300675591 400661316 32727680 438369536 196328292 232835596 431198785 755585685 652168005 314913566 723026017 406165237 358177524 408616727 286033606 153564375 968077828 595990793 655985617 609844472 501337007 629415098 7495925 65380433 534618364 464647118 12193530 211097706 305108525 967685251 836670782 40016714 388702125 350091742 137238382 290047478 989546977 917239409 270163258 780699781 129950756 632100316 86297912 641711276 598140592 993906141 578413833 911750048 242387468 624566480 208673784 69059226 982708736 27081248 353207221 316363535 201498135 856456775 754055436 382680809 563465533 829790115 59045591 655424643 852571442 605639608 523853450 248345861 168489078 176628743 357455911 285611089 779786670 160077877 126166660 798046742 452603973 114455648 815613020 39743128 373045492 405427592 518100297 238573025 927238982 580883103 327034003 638335693 380930392 560405668 596859535 246843092 870991935 93386775 933383553 423880708 508495542 107023124 511605154 332140591 612385875 686305300 100511258 72703883 895868779 205428119 678021445 730417491 781750370 5527543 638339900 842068814 34894633 7218973 884427796 694063043 706074051 768740258 610924594 200876626 159567937 14960679 659365189 664239592 991591187 245203717 145311798 378494399 940728258 236908997 880655889 637433977 768114878 115413821 804430586 400158013 741685134 48114696 295856927 566047203 272508463 538474416 106380586 256928363 634115336 328725351 977677729 365791595 305024029 401243511 637851565 315358038 978945734 200031825 585968415 871745286 269324675 233090716 511251574 849200665 849076992 856499976 712819956 77960869 919440180 157226315 14787218 505702013 17578739 43374278 192901708 982887738 275047571 851771249 942197577 222387028 104667124 216269669 639001272 690498141 323987980 779929871 71244008 24349791 363009635 659111955 846136777 947099785 907670178 969969919 611994398 434294948 52175868 568946178 915841842 787452083 469214160 641483967 770612968 994231587 718222883 590372134 959100722 968946672 383232 964308807 292592064 1236544 297367588 128684957 3127467 803643053 372808704 113347841 722680349 200921727 346426223 406989357 322444936 734115608 191990332 812089846 458340440 429607131 330250213 918254589 241717711 415459393 261360538 122355626 21639324 681234188 813817337 317316845 439998015 816541187 54043480 274080360 735613758 247640104 249202067 529738408 272955603 156855754 52489860 983677744 810796254 241376120 116544037 520320269 537779550 935824222 384002933 131111603 846687615 148076148 244491115 219654066 870306486 964521698 381027790 631076919 703997255 453495340 808584318 315139769 734452700 164816980 141977721 155746415 178044047 962893415 245839554 654197383 13322729 869039740 745549161 666954993 988206825 32386651 761453924 120178140 942906739 8597363 313599436 550619421 471805687 798960769 67737329 888822700 17112012 953685626 786314995 16979258 55415891 118528506 91410100
