1000000000 957733823 809081300 1000
533363221 638929575 443006622 286508611 691905309 228596664 175904171 410178708 451046889 127797916 415935615 570618723 800660185 563213999 903523847 668436995 933625911 861427774 755608174 362042286 314119712 895203661 417507948 153273866 167248092 956338547 340620264 687124372 406025268 437399336 534133277 696358885 991662675 254002761 900664117 923345346 948405403 152246766 84647568 928114841 578679509 986820726 479752907 479772094 802239599 264879510 96332742 935475182 803620993 933390174 120629889 201998461 890246750 858567004 993020438 525347208 131527022 813994394 259215147 458414496 474859062 907039588 701704093 634251953 837508993 332089492 118110297 804888657 764182552 590217387 556666219 376642980 530532134 301482197 23628285 909869930 334892328 337164884 594611181 314984559 398301661 549497131 144865196 576652104 198221420 760277846 462066475 650386176 348705205 205516175 956657252 328377678 10669759 11763391 138833819 139030274 219615585 628498128 769736333 517067606 562684859 600202455 871979629 933225878 580524084 850088273 224917626 619338268 365050073 35814238 634493712 605785212 212096060 949376626 369472778 280031352 276529066 469416960 709686272 573006469 129317914 192746640 13713787 706876283 590161580 692459793 957874664 388334919 542188803 794106203 127038816 542652200 538075358 378921195 165785993 5160771 837749123 72995512 622416150 555396916 518303929 940479277 81841602 48537313 796592361 914764332 608707454 410570966 601276154 664027722 915168825 964570364 180064948 547130816 102656461 917779889 825308248 358864969 235728190 850110841 604218002 715551581 367007070 714799709 615196248 543330057 647817761 131035643 71588709 600598246 7846201 874614546 121127713 176948425 781078106 12210237 132781777 427825209 683045910 578782734 574248058 595609591 989125673 564283087 618066460 464601084 299886699 51638987 313069524 424563121 617965892 921846758 457707231 399016266 748703307 276067959 235775972 579449495 95589768 259479626 608545755 437643850 348712781 332854410 89185241 35330421 19165754 44654407 127050517 739310907 258049213 189914581 733671828 94150829 771293794 923510869 509124993 215182686 212950457 276841476 351382713 109236544 913827049 961927829 864135790 98326272 80995540 861167212 671301530 759492002 139288249 260434116 544523429 303717915 18385292 837716106 591812213 517361213 128636994 559684259 634975556 114194328 487448908 977433677 551668419 130480613 406875910 775504128 819642459 696971538 551095007 156829944 878450745 171614896 261035957 995997108 88374194 320145060 157762668 448607257 992761759 472704953 136401397 59503013 413510215 609118619 402101090 257899922 902006214 931391331 885813940 444523559 11856603 631697676 857448394 446153167 557141075 841355008 547554187 775810320 597102286 307046774 131935280 159393835 281523476 658595194 878717323 357015645 292644200 733526173 744522410 874692431 356390681 526300890 53933043 214571473 677720204 190221746 527493269 766885670 924356622 765060362 311184528 955690054 178808244 900551561 105358477 159672794 339840234 462070448 717160387 562663924 248347910 348863828 724017692 923022348 888495538 416976154 879096923 294510307 958682044 356693751 251289263 392059818 869548936 882766323 762832168 442883389 362806824 988225538 468099671 44838115 901197338 221505878 186397874 684185975 412502366 850069652 985696303 908919966 92954030 293628246 92518119 173874008 648959115 459528098 937556877 357180279 912172594 109762576 91170462 72381102 412279696 328880433 944280279 614514629 898527986 454871804 254239787 589401209 797806278 915981108 657967039 242034696 543125060 423658653 448957745 449043287 812997454 683513743 925467604 109982013 558031054 766846532 266564256 494579756 566520185 636008723 298771325 632900992 680477356 358768596 763470826 439390160 707907313 738822017 631209571 170060423 978553834 50785891 864486123 617663885 140982403 816801386 191697861 640487730 415505925 865020061 191503214 590289475 694507411 694742468 668079340 291227443 544419794 709416521 334268706 236929593 640996416 375056939 717486634 677196539 21056514 635787673 878542865 646133913 821623138 700246962 840321580 358607371 201237494 985576263 530850200 278516745 590332981 351979333 472960876 142731964 156902055 861903740 165234148 393978268 900674978 32135946 16715604 692557301 449199570 218420364 941521831 424177504 579351914 476779906 978409991 854450464 525817765 523985756 871923375 523112815 159039290 429956741 490638 729976908 147825848 944197983 305107581 825915057 893827421 909362385 12497399 664137813 617984615 162773992 922075896 13853899 914263423 779872882 157105116 134549028 65250111 368230590 877405702 861188195 882776049 926288646 662511806 133222150 312981455 18137665 970808007 863182373 180374105 374431801 948202100 26788195 331377721 197141230 859135515 884316807 808261571 544431505 906234894 62113917 271558980 689035388 312208071 978516482 496761054 720373672 881253744 36978855 880858808 915482268 863897747 392513268 974490322 474816411 190204231 233118664 6912425 213026843 486927558 805047219 207900212 222986221 370469138 919726519 256330533 295089055 497131553 504891020 995500649 334330772 206339435 834544366 971477611 306056742 672345035 44069537 868608774 113840715 986717754 896586150 30688857 391561125 4208450 938209025 580421884 206146293 809640646 100224913 852941946 941951100 122700419 641649416 612609704 20966393 194857446 56541650 34006155 310813789 93397202 989978283 935464055 616601101 532374311 124446558 997978354 101187591 926543739 381171701 409076512 180058120 432372620 875713118 331216318 475052005 928598715 121215239 376291096 209048123 188565172 602733058 454159713 905431759 522467677 53631562 516289424 368681867 945833880 956082872 338457833 850368554 640633099 711247465 932658463 707656591 819896254 667528405 695347713 103022223 622699285 555701948 276267636 370521841 731755613 916770504 852174412 926909044 713935573 50306201 461521919 87968072 394852853 567447947 122785708 166323597 450736611 281673091 934923498 121394190 162695083 669585753 913448794 22702332 379754984 220634010 565306331 635859192 541057991 42168322 53392747 797484609 878399342 381426499 396490801 179144169 103983692 675973012 889936860 607764466 191429913 432052988 872367212 173665897 372471412 212207285 671259958 60782994 451322816 470335711 44998573 376781070 703918713 274414874 369672192 410348576 84792894 258786480 769992588 528978097 904799577 634803038 435918176 336339098 674269585 177718279 835112402 854782252 733461160 725599146 658974139 805194997 544121411 33965618 703250254 850776116 290364733 3488126 642892019 22210259 699418661 877710379 613177013 965785764 206206505 747873503 288195836 58066650 968619215 583368824 343251396 885145133 99380390 617687590 539392338 458335085 213948612 946713612 709353067 341547555 165976857 469232677 833667361 190298282 740083594 359689337 132229057 801936580 540748294 205799960 357531033 364835728 728276714 563694524 389772934 14844967 391274123 549274953 705695248 67859158 195060352 245557321 692083143 874368412 279320869 146609747 906291526 804173845 561488923 901200749 278842958 704294158 142068048 809625902 926155925 941166422 893260978 885320039 733464040 773994903 150151421 301664328 937228759 211210171 18883909 628029033 401849432 47350615 179111898 635346818 985294048 590679525 807635224 754827307 122920903 52356710 564679926 845296995 228545043 382043444 28075584 493696578 755324664 965807237 567103216 771334329 531040790 260537404 133009601 749220238 374184284 9417755 444168633 489074665 384252569 649609057 172568054 174626707 414677730 904181998 992562617 346942426 643260580 847897465 984962989 395280030 230810618 878607050 651149384 291048582 759528438 751668101 713228432 37873963 892545032 831086932 844434439 763943476 867034349 496025327 166170041 17412970 602019201 267516769 397338395 466012821 404638744 756418989 30766286 619160101 591822775 694876747 777431249 996510401 125363460 302231319 802970084 730980846 914892865 621477938 892995184 880607235 982253747 874573456 504269907 220122466 557720911 922982248 214534838 61987356 291931900 573060131 507473753 380079417 304661920 851891798 471991243 555557207 702899189 319144182 515875298 924658950 477569537 291094503 457572458 281370102 228322023 928713598 978311996 281190323 428001840 430466060 726126854 938219503 756525630 749339749 235330418 607207778 498851108 414431074 951967989 972829376 476584400 913766120 796140726 840327651 460642668 342782044 512938833 963623979 380308009 925382194 821971387 110808561 491171181 186908402 674687079 752097399 412255557 996918083 534823893 492381939 135023461 522852778 83564725 18036340 341580556 720624664 804708994 965811982 646844027 945357481 465437644 401306913 592910194 717516881 111807641 102847968 915220971 767246362 544064529 107178380 682003053 231362715 494016514 763788302 406508578 595094913 928867115 337238341 755469560 179848839 136212323 102961765 680323503 994186696 799292591 126639935 281101771 13450200 571736868 265970377 176931815 501913836 350093042 982322744 44088675 116510913 767578953 765212348 718129583 745813744 29556272 683549450 451844926 655512296 604066568 317883990 810656420 133993061 384780750 936820939 873180599 716834021 446148083 471694287 330007111 553013006 180376029 406760065 975980860 830235040 485337704 927908225 327301464 176352060 421656366 82525068 798140544 91530425 753578529 609545527 60942678 987648157 427733615 217375779 565042509 496770132 872939214 954852024 52681740 658750019 259635627 9229091 494526659 747860729 73503218 565504707 748747557 195739234 918117264 53118932 490451602 977846031 275055855 405213220 747960709 680125255 883458030 577191658 676579313 342619532 97634388 263661211 21476095 171492775 356031957 939677563 566078109 722238559 12163252 416838302 709693603 696218586 781132625 928511070 795649371 98316931 997743177 443526642 436550163