1000000000 500
989288635 888719842 131179279 116378836 770568250 644399407 764951366 169421604 24798345 6406520 593523697 511262116 695688410 316635457 543342059 404854350 952427896 303938541 202749691 67243699 585221513 152516028 269549630 500809038 496402142 60299898 269302964 557993749 51363519 127358836 342758455 40651155 16077678 326456083 9548340 639164278 970855489 627018056 808585881 848172184 485942925 402108578 359433300 181630335 718744035 755293708 439003035 523689281 59231250 641752725 443451329 644452762 794268753 565519308 997780149 143188245 625819206 267082113 701181993 677182724 394440949 43939449 570352228 263036976 222913881 432418918 902201253 46286721 911955323 710786134 894458904 397897248 965413062 106409554 432045932 536674447 861703261 871048966 60362728 920934510 512800692 356332406 417904622 159586795 921851714 268202121 155293389 400188270 535284234 856475381 77369994 782243532 752933179 500240572 45279508 975847060 785177839 947480761 22132781 697132162 510784245 769110034 947547759 328714657 875519587 379592691 865389103 737221848 103159008 778270180 510673709 615959699 134601587 781096680 628064843 908971650 49297802 783358231 161677270 437100385 492350962 91565613 219342917 97801492 591806184 117140774 73647552 229501373 64620535 948299681 926633534 427923130 569927065 726698643 756637786 445445652 106290335 474544240 35184850 61967692 252813420 398376908 677927390 239933356 179472589 158509583 1422356 81288740 941867813 163099625 518389124 434217775 254665238 737732040 532019266 698989771 854872813 458185167 928491144 772011698 259002198 707642028 52452178 828929262 434339672 661608313 126892264 393148356 136151553 14595464 455116047 241483323 412972371 985561786 481416678 592444959 144070369 335357384 673733698 85937182 498457008 44640172 372673306 605640595 782372211 757210922 304629367 489762375 67913439 85637861 114291423 326915637 793279888 19261950 8362249 80136910 680870262 135254513 473285265 817021815 2368326 780919661 58504138 415340696 766480447 392439165 7784656 763069165 727796548 534036703 701524696 78770907 578676875 74197003 684411501 213566436 683926274 841559217 555847160 751839712 927197077 670138582 78754349 720475966 689400531 939635947 800612875 222788144 927408809 126415491 39808959 929777134 907335151 950832445 345116830 526332949 195788960 205419835 141919464 776103858 591974888 843444160 854874764 23169113 770159512 391803615 236735548 454084786 85880183 792582708 58441848 13076260 315238640 137196197 586070575 857157521 929350493 239200801 79944665 856758302 365616291 972272972 639052786 125468792 775622767 984169615 504320090 971411726 42106801 646239554 600032934 634081688 489682714 307425048 657250800 112359576 699228663 746504697 566444361 785108845 391604755 624886208 650703454 706843395 614600754 236773030 416518266 396468597 475973830 496462930 105744249 694108470 321253252 744797034 819577261 96875019 581484000 176414702 920805094 623590800 822654255 520837029 110189838 164854319 828262076 619958987 277213894 380008089 366462684 843658254 17634284 758067439 321061812 668337738 317428184 788180916 757629117 733946449 184648513 86120297 82926729 290392762 780228766 404179980 35188796 452323377 353573348 469191145 628738078 274377442 92780945 451391333 647732820 55489132 616245651 328512247 675448118 893459544 708520335 894429152 589635148 578672969 505013941 763215310 99528057 822442124 551395226 857157173 408905923 588562088 943277469 344351001 878954849 723505235 748530980 766661995 28345962 102103328 88370490 657084040 228999119 33669785 108474373 876731939 89158916 577238374 57761536 617125384 323215268 766281870 511553536 765368766 197472189 16566477 528583076 297000245 691526950 932496651 154156418 952951222 521057739 97432887 297301223 252529939 673456471 898350552 871710283 701802433 852972229 960080772 211403823 81970348 993750556 172396545 811220636 82908473 749634918 868982171 552552206 925368536 487781392 64104742 690736302 685253580 933190567 71836728 982253825 477234867 4332379 988928592 282703439 377908467 938879829 580004661 482956755 464853650 330872563 354666038 19173433 183843792 167264161 230577255 118332489 161013717 402973800 782071475 96440539 5126068 503570996 648992744 930494603 991352387 565615835 473748255 529123318 351323752 545584982 363894493 681076968 402435710 205340435 963780406 632862527 144219264 396302417 115818282 609072914 727174979 323002670 628246346 911018770 490266830 858823601 881869609 651280546 114314751 663940084 600239435 119440818 20028430 101749529 49934422 11379818 667365364 523682676 393021485 871207465 921786008 609434327 552283434 176739068 814774761 368581190 809601594 958994025 764883607 925419876 420584289 492057586 100939896 901348984 255593707 591206725 612689935 137462316 95004621 727004685 653920749 695244055 846445503 673949178 796993584 896379924 537847345 316876298 272579950 783387179 188082763 46883308 392820506