1000000000 1 801809934 1000
326406661 169791972 761656767 15280008 186815446 186117411 265403224 308467755 392051233 725260841 341791121 418439521 777844152 419969954 730027819 343615863 568299464 475588222 277121423 761476244 202455418 960116443 484950749 866814884 28710946 434807477 996165424 769785962 277448789 894807489 201496085 872256986 226055859 422267476 689774427 922076486 23770029 70935867 365709390 379536822 848952570 464510128 918681257 942223099 399220318 956979801 380749603 831068191 529454452 442491822 224199599 362618538 251651927 44911129 295152951 843478268 799713235 753952702 455811793 754652908 413022380 967149518 578241689 70839331 890704082 863585350 510766007 952150993 827352133 350701812 476501899 600905233 872409416 640471626 144845997 253974511 425866367 196030191 439522445 783746065 829173983 905763704 732758175 721681906 320172692 622173692 775372604 756593835 821919361 310149402 738204951 997599544 176978862 218890942 260583286 904139972 286231635 331728568 494503167 353022282 821927139 440882652 22416593 946057132 413311942 497969779 634311697 767876174 391888174 132211875 513167110 505299821 350017888 792951289 922559571 626786860 999475888 574171185 377346903 550205936 246599176 645329902 193520547 135858450 597869195 311592858 302308003 254190249 830549463 401127544 799472478 6925695 436055733 500775950 552987460 824766230 912844855 560312220 451697848 331047594 860533207 753006134 652970770 838303623 802534020 918245963 68679378 21862590 224854896 638768578 512755899 36535888 952105204 57776410 385531232 665270031 319819718 58440388 807582840 948151243 175546940 848648232 718202076 890470175 318703685 628626580 781137046 856984469 165166860 336819079 151375664 476413379 186899820 530449405 187038043 706079719 87220717 261018348 700034241 486345204 681091549 953980576 438649136 64685407 540926873 114154174 886314050 259929337 650645767 416692251 402506496 353207028 705736094 754366283 964425123 960224931 160824918 376243883 265351392 511069155 678450311 649970037 870849796 197742050 219699020 957056753 600348447 104450106 998800346 805817542 269816991 402463903 711079897 373350130 933514068 55432700 723244732 816777107 857374128 271706329 229626818 309833273 793733966 118359801 703326688 960671820 155495577 709516329 937999938 287522145 546502071 272765884 572384673 416210777 900307566 299501806 25201680 510374107 807947037 626767684 677193259 997533543 141433475 881767322 78749713 696516645 421909524 42384280 461781786 160585447 646413676 154899165 640102797 388396339 500732919 903515670 531006156 752177186 679493843 495829832 101702643 993096519 730298752 188348838 188041394 389539204 381512151 762310545 265900216 71469308 741309286 558800134 807880613 584121340 105877522 293327521 406942161 815242862 841122177 929330864 615283423 934746862 373906812 714646565 188788687 64382369 816476325 97098348 918113342 865324500 749630822 832427035 818967266 86421022 779179785 319375492 108526770 795823893 884032941 576044424 722361895 624257223 359806349 801219768 304440665 354484484 701094213 47675205 265778507 173389792 26933568 627178085 58610102 438740567 527624401 823337547 523281387 844753650 760222039 597868453 299113661 938694610 151705987 659451326 235350721 948448703 879989866 269817779 415707819 195095866 842441119 548219168 140985929 876054465 699517826 396884483 353315005 373021886 874089215 955566008 241450769 392740383 496636429 773284944 29030567 437960103 295259431 664307230 244142260 531464629 941548536 873008439 348208382 445346602 959838422 107210693 151345821 225100211 466818893 460485529 922980745 189265513 562212590 178970136 400244935 997848544 66946164 956505950 160088155 878361620 821174668 679004437 299480904 747635186 577769311 721516873 767680128 318176926 365331058 463361839 946740857 93517959 872057535 95116776 899837670 991894322 926076823 685440931 29719792 210604619 578798083 832218701 538723199 529758244 179614849 498509687 44877445 488466421 898905492 357164205 642016876 346067387 968865636 429999277 715393190 926163407 175423525 921887570 69892691 12919534 242776397 123991885 872490411 928012767 797440746 141185498 409268110 179011832 27279380 800766201 197532861 998826791 402224544 983148882 900817079 272943806 341485853 202693166 754993626 770760689 553549722 611027253 268249620 903196690 538618413 916111992 710259184 538262041 295276906 958001151 366718281 156090280 258069552 531752154 405263690 522468176 62009852 670022172 732150162 166492230 63734375 663059402 746733534 456081273 988827571 922791890 236413402 555317270 253443834 96721020 222307161 768659373 670220289 840677111 965299367 621258310 422941262 202935670 535791060 641430355 152085351 592971133 667985234 857071548 554961790 721334012 915560772 35830828 913321842 195550161 961592823 602407469 350686104 212497543 180908643 768468975 691426573 772415300 445317791 475620348 817071508 436671021 104494727 675012073 845554036 253665836 606674760 130343767 254380432 805729673 940494759 342039172 912399415 589994904 38628312 685986793 614079434 26656562 266513941 722668971 803646795 293294161 920010868 740416882 592560039 201170913 940291219 142376266 621136710 526693709 213591035 305626091 950578039 160526423 728139132 398837497 965366598 677476307 386012161 158309146 84205757 54451332 335520108 868156764 33101409 137133296 549369447 146372259 136047777 558662614 644057217 278331818 703498766 732558410 585457022 6106603 628211791 252237668 225775301 1888061 594136748 931123716 682967526 335124670 664472835 879990251 276288474 720754510 839555473 367540500 16489711 117190717 381884723 581668804 762044490 89289528 671786473 319986011 705851595 548107943 419111001 252240050 265809575 695549668 276046034 941032724 793690743 465652663 793914179 999724448 456760214 588637303 843740018 903978191 788412242 870457707 50344764 35908436 70195851 813162360 233871818 788587922 601894400 317470009 295337098 895906272 415130966 405689159 157132894 601422278 972450143 545274714 45663028 806866423 718499186 515280424 590288043 670448191 376058731 374727199 544247168 673107261 774841733 424179526 613335668 411083282 621844981 619444348 444583 64929054 340934708 603283966 49594058 303686173 558630918 111350948 83971998 420622710 963471272 407808616 345366518 949608473 584045519 979046026 806864071 678960718 638445898 458173853 725347859 730552420 156788024 173892902 966510573 576911309 259720964 369746227 580912997 944098123 774244208 45253262 362380202 260448928 793477116 96457548 885614381 311752513 838137537 158618669 876772359 954002225 802503879 411666176 754859624 666072722 925737069 343912974 193134924 97143630 605434496 760071592 216789371 372959664 902065885 860531601 726014092 116770393 833692019 604725288 651564391 823620290 980384098 747261881 746083117 261949392 241971800 559773812 336548189 967236551 967263497 346394692 27429830 377918931 500604121 886282927 810595303 39017759 788979984 748829493 249384010 582735756 440687351 96097591 204517796 283028751 187956758 40803775 741779838 951183237 668412797 526938528 33296674 197726681 733147283 818969121 117598007 784756812 636929636 744170587 330303984 173839996 77319431 280087188 141231298 705012357 401678583 397108539 897798727 9367446 672375497 556044371 662670283 649261442 772653690 156962824 964272855 548540302 169575949 352192080 827374234 722153319 727018219 887005529 70465235 610800636 754473398 617223281 251935336 513198898 110012697 852149931 515465280 475945768 917696331 494690766 284773204 515949095 17481482 679758561 89149493 465701875 547270036 295051757 395155782 290066533 360349844 495951971 7009169 765261428 469266916 335372007 526506904 295176467 343673105 456623935 445671393 870679142 550785742 327722207 805328720 644128629 404811479 438342260 275721189 850071927 227521540 359897699 412952124 892951190 141200077 180272607 816030158 114570747 371463696 455393649 169357641 978056818 287380971 321265897 742050724 135246718 581711092 399037083 24832803 753100906 98320127 217548883 253175966 963372661 451373677 251414714 353039532 38106066 498532859 434320845 333542568 917638512 596677060 676466156 588273480 97684378 30109721 321690381 360168951 676908790 511430354 306670963 258139147 627693495 131171384 205495645 611617945 532342056 656070193 316956632 256944447 949456838 643854039 84744643 521565343 994222973 335266710 904263872 221135288 400342685 493257550 892782236 522815669 533623989 726681654 599066692 36821887 390181279 435456845 98933342 620344619 98913751 291078682 191668911 153925080 374775151 276443012 96849206 872803408 819835825 725648429 413531696 970149786 537880261 321142983 823727176 629333453 850391499 858951499 928260239 874900048 624584130 485414777 75790489 352954355 754019874 511029774 16573844 457480628 885466939 420324397 244700379 248094251 380584309 200455580 728841143 386384719 947290702 744828286 646832842 757362783 860726515 780699816 96732745 142132839 824818012 709394702 187538552 528199894 831980390 828397516 740576314 50899789 774270620 489159746 740467112 363033825 508472454 134058020 402813243 139994740 323268294 36607154 2389219 427164666 318726347 727715802 800122952 123865153 889980931 685914365 470523862 304576066 482677040 233551544 774443518 173839365 66722618 420585395 336318067 320809971 595503610 281644829 550699821 35895962 934278753 22591613 666392802 936612512 591365077 518539226 600140259 900393280 666355181 304316365 412849627 244034338 865111626 393074571 744633431 593138731 263570946 651875887 690224445 969336247 823373993 62095889 50211077 301515283 579713091 104622401 673336940 608889520 846593088 537135220 684149182 867864239 485342852 663454297 941282858 702717183 481394811 157956807 490284363 314552208 647979572 703101070 490924275 332134957 882240552 516133559 970284283 650879289 46529211 332418575 280299161 482627635 476943532 507246703 859008957 904740148 709713255 880736103 545279666 128891292 538703451 197853608