512 476329725
999981472 999055162 996965287 996703160 996055096 995760996 994887774 990517367 989637372 986559134 977091456 973435995 971537982 970442528 968880090 966733044 965788847 965100193 963408508 963327852 962660987 961519304 959394301 958358825 951515013 951362305 948399807 948376706 945806447 944663921 944426691 941554440 939521209 936658917 936169726 935168651 933755218 933700257 932033992 931892662 929909778 928735731 927788891 925854796 923551557 922561821 921234698 920895254 920092697 918198401 915733388 911815793 911319989 908076510 903058533 900419902 897179972 887352439 885779490 885295439 885089488 878669146 877819932 871620082 871558340 871225568 871142686 868215162 865813195 865126561 864851917 861279599 858425225 858397393 855510055 855350880 853608944 850676844 850369994 849975115 847669421 845843467 845416469 843799205 843233648 842338743 837398885 830814963 830308189 829586065 829376838 828358954 825836850 824314566 824103588 821428661 821294773 816735758 805857604 805494076 805044879 804475445 803683097 803570804 803107219 799930401 797684499 797174303 797064780 794678740 793000948 792461336 792214151 791985829 789588231 788716019 788081819 782690228 782430167 781388501 778262696 773201588 772504751 766261493 765712182 762782514 758649224 758449970 755182271 754919547 748731582 748515718 745101848 739940077 735410890 730108181 729612582 723244565 718900737 718198097 716696390 715650617 715179164 714803471 708349284 707283288 706387719 704403197 700874892 700476411 699190930 697786242 697267024 697011624 696467499 692403864 690058963 689114477 687957017 687875608 686952932 685864696 683123681 682112696 681274574 677442892 675579294 671923072 671745762 670149688 668374549 665231127 663682397 663579370 658366680 653675839 652497387 652438644 652387597 650891214 649883052 644123407 643371639 635930954 628131564 627144147 626152398 623741149 618491951 617551954 616953819 614617837 613210994 611798392 609952610 608324945 607708352 607251742 605172371 604903004 602627797 599205841 594490851 590234611 589411491 589092426 586070890 585994338 582702008 576991801 574364042 573895523 570793914 570708792 569448947 568861448 568694832 568325796 566573286 565429876 563277640 562092317 558331243 557979020 554235497 553548953 551813827 547360358 546459621 542154234 541509730 538806790 537930051 537793725 536652784 532142954 527003580 523854050 522345753 522205410 520841395 520776770 519546445 518919658 518642457 516690367 510815666 510713513 508902173 506948677 505496602 501517064 499866558 492671064 491827808 491142528 490880572 488527907 475906396 475674475 470336540 467616619 464792267 463754205 463532439 463398846 460930756 459728386 459323176 456833666 456067857 450902541 450482293 449921197 445098755 444800202 442674432 441855686 441809831 440060732 439562873 439223172 436253714 428353523 425994795 422365846 416547520 415573600 414770864 413185630 413156434 412516550 412032666 409102302 407915723 407478110 405374330 403117266 396638462 393433380 392725312 391452845 389277621 384420486 381492586 380481433 377603471 375720437 375708460 375363083 375273407 374981073 374571227 373640462 366437182 364452124 362921853 355174029 353432848 353088936 352403072 352261869 349811362 348679233 345555251 341258456 339192067 334825576 334195227 334081953 333674331 332731546 332031321 327470003 324916289 323566161 323278353 320916831 320717084 320446497 317232788 316177498 314800357 314321357 314225209 312865399 310116022 309382957 309178397 308065155 306527491 303915033 301430167 300732591 297734808 296900080 296562780 294108698 288645695 288611542 287726685 286736855 285770359 284649288 276216127 275299175 274731873 273447508 273225022 271853370 270879973 270003400 267180136 261086673 258639230 257585190 256882298 255915965 247874322 246825220 244342818 242982070 240610638 240435219 236527802 235740378 232777581 230451149 228734976 228323727 224763563 223756706 222088263 221123905 220914477 216964507 215821112 214180916 213245814 212650312 211650128 208189161 204190173 204065119 200471090 197736237 194357808 193766942 190851290 190194824 184554139 184182264 182493750 181956105 176717301 176566464 176017346 173914895 162554643 162496817 161449316 157044922 156362316 154708931 151792008 151019697 150959562 147385196 146829388 146029598 145281099 141849238 141545520 140313483 137535186 136129732 136019914 135545645 133657576 133022806 129501046 128547749 127573301 125517639 124319565 121686499 120632000 113774338 112767987 112097151 110155928 107983631 107862364 107514066 107494275 104902867 103015276 99420871 96286889 95258723 94826305 93788283 92276533 90200396 89360514 88367706 87490102 86664232 83700114 83352528 82705258 82081425 79837681 79810508 77986536 74400755 74250213 73104662 72149306 66482389 66250795 65257063 65129398 62699734 62458775 62219931 60419245 58075043 52788300 51428794 46626971 44977195 44898778 44684747 42474822 41227921 40711253 40168421 39778533 34345815 32878821 31529041 27526987 26897634 22642238 17404640 12845045 12717763 8989141 8060731 2534682 1783361