1000000000 534756891 543527658 1000
702340808 598102723 853329752 572034620 975329351 617733109 230679944 829852779 503128018 355746866 443120420 51627950 127579068 106567561 79644532 703345646 306545813 302226744 726078059 118130342 68034745 998675817 12288173 368910305 490224052 374647055 271008784 31825804 172868128 923003131 565515419 928775737 948940346 553099179 554952220 560491022 235597591 802625499 308241465 883762497 325659410 495637893 97017744 637152141 188844828 92697339 9848694 170767642 68072545 560238594 288007489 113744091 436508413 592775945 608685988 647064638 358190861 717146689 332441638 667919002 817652148 531802686 180813191 237949035 594888934 688203532 289856388 49676703 618958864 430857986 115329824 244377357 187772614 167121038 968425616 550784305 303570548 762805190 232498306 252541628 628637371 962509787 981427484 29847787 214341341 31108747 867203603 119451835 803531126 496737329 321619193 237454058 865753486 443405760 552361633 55268148 105102915 159401150 69295224 708701497 128020396 933939908 770066236 693038209 519903978 988957233 954537477 134807832 119993242 239282164 452209743 344540674 5470589 676142728 521128202 89645127 205887925 762208561 699338775 608799797 412360450 612371087 305497768 941337025 539368532 638460143 697597972 342153010 678191034 587260388 250516310 285949033 950745871 833795200 191396304 940936752 254422759 443377739 81412686 355938866 448830546 458693341 866439683 165158680 199337819 196243016 795238346 706420924 453135631 873554761 562932218 462589470 850436956 716523690 599115680 860171607 44295648 373880653 275000655 551217047 60472577 602853414 329499358 609142923 810570015 687735763 479985308 90768407 831235482 119888818 631720046 159679160 446842000 323188844 848766248 554213341 356723098 744524292 906314801 331369042 894409029 3167151 616965908 221243023 63561183 973446928 118371033 892102912 916568856 872579667 280654712 15930755 386493636 734266707 305775466 239906597 209645343 562365300 598083459 691502436 973694514 709169977 485570992 553812347 729998334 507932630 576223988 519068572 906932296 736546356 353662403 843022551 656670381 740639937 46469726 406396004 225908347 90516939 899788503 165544553 242254389 134868579 67234651 436389438 740638364 20032315 601944256 81657978 183594216 807737799 331330089 239717555 253633516 63472520 557021307 975906282 650544418 860794852 855497951 951062598 788316771 339626837 96724136 696039980 486033841 816731129 84621882 605804863 542370417 625267230 155124822 137744299 81070230 653321764 295017243 888820808 515079927 441760435 816671769 160700185 427339999 44314204 685759749 19376397 315340261 163136894 578910465 573539328 495144539 395151654 220687237 386142293 197945620 419874540 200138141 762352988 979239717 841003237 4056511 532062303 249228816 121865441 566826279 411821464 143559570 107823988 795326878 46886197 963573160 599926496 528904010 854889540 389166929 567145571 409452990 65072925 611482555 404317569 727139881 784303520 534643757 686053254 657347638 312138277 879230548 392853632 252528725 822611409 130248483 800434294 468655299 793343323 165586653 949829089 457817251 100647162 433496528 437882051 57189694 188271832 894879372 335891842 673439161 179425816 542665930 223253507 567777646 295327684 737685174 851633690 428928978 980480493 219897403 160664725 905097199 268218471 379683850 98826696 975428944 144109013 752377901 831685377 165089722 114102536 18442587 726931347 500698052 317506001 900246238 342503934 133711357 603312029 521248899 670636706 323204865 44297775 409629142 878175942 921701589 165335495 815237224 746364311 693001253 394508069 141372377 928635060 732057250 752403893 194791098 15172637 529714696 521445436 52696251 902644799 926671191 927007118 214781644 988830327 969120386 416615233 181806794 831307303 253250945 76061067 605599910 318959220 628436031 799805474 156721524 129977629 543150007 842934478 250169293 896085255 202072777 421542815 321548655 125655312 912420589 945874726 568831367 825347355 198173040 855388100 178538665 664696199 339093302 793277802 192608594 914791732 224852285 594885501 630513505 282430816 875881448 285941567 825273213 843765144 252529050 828065281 525411786 143147644 700784874 217332153 905562150 566465567 791794224 803120939 45166957 542186551 756256839 526736706 936241614 800141735 439559437 331728785 498158689 588105000 487258085 991505390 831747640 137793736 911966292 826697811 90930193 329155717 202269350 74360652 547034103 624693120 169734463 868853231 769489063 656176413 277614967 466544068 743364082 734018154 423320893 140934543 12409963 268342785 321537198 851348825 22164823 768313110 219287165 477460709 609505954 469581091 247002115 278665557 943932618 140085320 771904531 450749393 496491761 489333515 439768821 629620203 301089631 941972691 485588759 852430719 939701902 975143682 718428100 394279845 600578903 756490224 154271107 821750226 688731331 570639593 77688855 46545415 604759203 147840376 114636659 405513260 422023872 890480889 498782286 331481544 637738093 373255277 501716055 247204842 464681179 572301540 92744673 760350019 601336262 600529458 999218336 540462015 763009521 202438193 764621306 448154697 910850853 333117134 209820215 280221937 258474094 888438607 533878661 711986664 580989167 76795263 60321797 216169198 687130288 505455480 818695054 880063055 426163479 671637211 505418732 201071418 341820578 459707124 725221388 752446374 908760861 640110169 512297543 922872781 522198212 893442425 881185554 606963640 690591036 688188647 39675790 37338539 483616855 996636720 100914843 637435397 654561126 723871327 610549440 827589520 45497827 177816863 344538447 675234152 283068495 855934166 766335339 264878093 72525626 241243316 127294879 551327344 840484029 941404067 592393199 618324907 513360922 541481038 709859906 270056040 125184748 519844206 219149339 308494371 839377942 605002454 399682298 131551476 151259352 669041242 351795408 602958871 782067355 532390828 402039373 18463532 5203735 486103248 909504351 251036314 435713269 113692619 645160333 564791431 571869480 347296614 153655758 143255995 374348081 614861883 292375023 504444031 999149291 453764523 705924370 697495545 768146068 633037742 831350959 986968934 823192713 236539996 535498981 27425896 311808597 706999502 513619666 595215748 812265716 196361639 641459864 648034711 556080419 194787195 902908208 305799036 636047587 951958573 814574664 348136626 313085333 690273387 718171021 368528790 520543985 816933282 260990286 228396207 28048843 44252187 717181853 923451390 583203264 781901543 966805611 166897454 431883202 166265960 555781779 544253833 67585237 959987626 467398674 74341595 697454837 83975116 473026936 179260561 986442212 560519050 706672591 387935606 273394556 401056742 683245087 705133506 290346179 765392872 530962577 19744933 66882276 956473754 465552262 180216396 945033705 392435126 734891148 63337118 428811944 87231879 448609678 891798019 87199499 978149245 767059736 628666817 383666885 469702884 146493419 24900250 812949215 946502694 385671308 872043716 936602667 425900162 541035686 741021607 18746475 465667846 81607508 409095153 493349003 282349160 577230880 262033240 577463313 947309201 113771494 897062231 515981056 554658412 991177487 689382633 779645669 633295115 862060079 645340074 364472947 897517696 654796950 392406405 252177301 284928955 986172505 322512392 217055719 554503206 530113892 788281667 823375732 91323262 493015459 45175866 135327454 263345608 85845592 771604186 771568499 171768686 698300840 344103831 179643052 972525912 744974070 949540883 982648127 144091638 460364680 670456023 507699558 953958581 68979171 765516247 457042555 725356193 870630362 804673702 372659338 149445693 251653891 77911673 570222071 576580962 76288053 125577915 685342630 525058532 648450204 23078506 259660461 426614129 729527400 109137656 325566660 10538870 603155482 37638713 159932156 403970074 255500534 303931164 381235765 412049933 762220986 908165750 301747600 189297616 28017484 590951701 13388138 602411061 411056848 177568743 469352901 706780079 47002775 775415959 411519496 437100915 887272244 258176946 189239465 124415451 475163005 646700472 680103840 523536125 831167922 58158125 358564296 551026196 74065291 348580803 262183811 960626463 466913898 516645951 992122039 458340744 309059425 672572512 646041602 343902388 15216022 185136164 953454071 179614189 487425471 583528018 871341307 942366259 657826791 849069984 290395176 515143627 438632915 865792480 25036094 948595676 128939607 276983429 589694733 362363432 93766299 750940621 297640534 955057881 291303272 745127570 308198316 158548851 777083056 513139768 45762827 336696166 233060520 37995915 794708649 393729629 336354418 931752825 518984254 563533090 897777166 720741946 628392325 65238732 176975333 159587442 574760293 614817051 612625423 285147222 359618680 18438681 661283205 958970016 544304983 927271691 366492761 660742934 468561504 290672582 882538975 163019802 758437272 666052138 579790185 326599435 188519119 902470514 144946843 875151409 554249566 562153706 263040168 321033033 49530946 316713016 457449225 357685121 807117500 643383031 758447775 842576059 668672101 590093562 623031494 160073692 635290383 36782600 803618090 884599453 433735196 154216237 973283556 593803299 695555490 373904792 680696425 819435809 445022055 873886110 763205743 279115876 996259690 206630977 365790046 661380391 444883068 685415248 671807434 672285942 124626906 807870123 407815910 467948372 723189696 965537282 324928421 21074232 933574099 249061291 527498237 850382846 880830340 437012188 469787782 499640685 799941428 294216755 319920874 684827456 456463702 973860833 632413023 794335105 558034966 832595516 429401963 340004800 6705739 445523733 715662072 76545660 160211470 803433178 998008940 615238089 172818324 85955707 474823344 306727162 128933917 181351599 697037703 589388339 581500188 75599025 356252781 356090834 855473075 532971666 500515631 472781724 352958174