1000 1000000000
667138214 974723153 121065516 695344940 628005827 29120140 184469445 345299326 474747941 249600730 104473002 451062758 469423972 58345076 890780996 427898608 256026256 930724620 409202271 624351009 795715366 745843697 408361916 917845781 738412775 5285192 607257981 741554215 755857242 54859569 505988853 520217865 817777197 366952651 607665666 314993605 801330707 856775001 357374085 113427422 944863439 808075970 796831381 934612853 595651422 991160789 630242524 267746037 387129127 260637845 896733768 775364582 489051100 771286724 519979565 670763771 890320148 183964495 544984017 176369803 646891048 184285425 338110196 335370372 985052678 822881035 206196477 48041194 425398642 509438760 195916997 715244322 579777863 974553861 682231421 779081280 984106709 340497529 301369449 822775618 813471675 92796664 60918685 63078817 449990905 214255236 109067728 162126241 649121728 611341247 986643414 191927263 633404972 218982124 574726780 366965464 797808228 458798578 180080043 815833090 794556448 128512010 105861290 473988591 23548624 477441626 863721340 882706710 255013232 299481270 659128592 378278792 -1 564467420 231333774 726601430 578834902 641902007 629955405 419106797 477352224 70920728 857638807 739693444 802599166 540369591 259736746 802126494 191239726 337322840 102579681 376267454 866012581 906541314 700983407 845476777 927442085 639470071 24878717 811094294 972801372 632870174 660816456 310553628 189929891 761742094 173229789 904136921 646673827 905958062 782492960 824829132 0 391189524 222527495 434550580 58892140 76317179 586060637 684596594 898045621 838629110 490217930 64263445 120981203 704465537 741539528 36740802 84661575 846889454 646705122 384507725 560173742 496264972 236777602 864075634 899512446 972772590 542142902 197351886 625753137 93343587 191010952 998396155 353109379 955883508 313584965 514113654 47470638 509488956 425972274 118366843 648202963 714919442 200649022 556311675 432637686 608682625 329102781 757675142 611804369 940387941 153963941 327655839 192253193 318475019 546583641 167910154 591399204 831829788 407354076 113184228 409344855 628630549 432246781 624519481 204824623 930623718 484026312 1961077 189407254 740577272 662486276 513812216 952953504 735754417 839305316 442299844 451029260 150655557 87115692 608392187 578976652 575137445 395959446 363472523 843616334 109405644 954232356 52018178 849452263 920971216 505277350 230390679 346019979 259639116 701889913 867536026 86955590 185387420 360153075 664954194 464052481 988240848 507534096 844320351 245826134 65009926 537163308 370047169 899920776 451327544 936625506 435565958 947281749 849288782 601755114 143779001 626309733 28634726 73120175 291990188 734528715 393214825 790266892 929895679 292512721 124268044 370139692 978918631 802336146 621340702 344424158 931906096 389937099 269101956 608609179 526736031 421553497 456407582 559993788 558642200 215233885 63549568 782767593 20882132 561820200 569395908 507825987 398557461 729953073 21734076 819079430 821260946 742738168 651829397 575296204 418281985 256394867 80750549 252285751 763890903 94838 145693851 313129121 838804256 344799921 219116958 206436232 654062128 972079542 217349684 244685497 302586521 214075055 913003229 625384636 177748993 217966496 880437053 322189882 391188681 171878465 200885256 870872706 581968166 923420108 702874275 301395213 43303895 307987558 784788624 660746132 105126893 86230076 552541136 267108105 797003296 589653049 264330828 912904767 201998657 582616503 506962437 283531430 411922306 493357367 874485089 970080308 557502348 455464828 669942577 629325459 88121529 843150593 737837819 765585882 757492991 847121531 408632553 653283741 428782797 227559041 575423343 764071116 352382718 718772589 499307647 25937961 555690289 210242882 617106068 259158565 604047419 74940893 609535477 672558161 937614010 764205688 838422625 373196036 679012586 904880916 507902475 462309137 375668866 364495230 772756799 473510333 381867474 377067512 440434563 829377420 171986079 314535519 453303636 53938594 613917001 717805935 652875001 742819277 690938405 654646231 81130577 932337611 425559076 864098717 243971770 197731500 649261006 110899946 331636469 517244330 432783189 539826601 459176269 921559447 425986309 365679392 887099466 907326546 234574753 657697072 902791362 95411227 327139574 205029355 601720704 194174007 514536712 427603946 704759469 539125536 596153088 531516631 955181223 415330848 832046291 473040714 269504837 21595867 115410852 757459059 397657545 973829163 230193761 939067134 257186720 65199449 96133251 922882030 652894176 566013342 354978946 921043165 369271120 40131575 79076332 663381342 326684046 753505560 760678745 296739738 186190548 796552354 794394135 756522872 857359019 981138010 452414319 483273502 641662871 658582152 391528465 653451162 724313328 975942712 623632429 505157646 327359811 594909459 645108015 345994 626828686 150721098 222513700 789053643 112641285 23749598 266144111 953632760 379566491 241935695 109221816 152096815 318385500 462086214 571523462 610456868 395374390 149489384 834315230 899203621 467530019 492408188 573866141 353331741 104701098 571290596 773203411 717019311 537406371 5103672 476853034 410568013 505891781 506645683 111974585 689416325 839059560 592207630 976684704 628139293 777217274 307272657 340153260 146221912 111509617 662849948 246479112 487821687 406429892 844099154 903571797 302117680 712803164 144823383 485956040 284673610 405513060 120181949 359176853 374132817 947933438 745522370 118159463 680068557 180960398 775596098 726780619 334828566 815012187 832059739 214574510 318718704 107604843 801066087 572001635 487302519 766846629 142145246 805056996 902725922 293416930 504723559 82442790 639677395 394982271 439725741 29073880 626920328 198651848 433602674 161919784 756666763 582854205 895874454 397244408 129719937 160387636 532561097 14055558 459262230 727649587 939758983 452637761 642670984 464871404 264356286 810965304 667025561 464711995 564239265 297408702 748540616 661153313 714615175 900244151 249629324 71842156 270692261 56547674 297122438 475870055 920069138 871206388 779298398 416149326 810646008 868313130 229250227 41352355 920904477 213315405 551491039 612896097 314071952 352056101 108674789 348703911 591386359 559240278 366979250 372544164 424581236 809942333 595365676 468588291 836368950 187810897 310514696 887439628 103856876 533082786 503336993 227694440 255942796 965972158 583011986 118889320 91911017 61066121 522521162 513922061 693331258 779748936 261823202 158222061 856667778 791409529 709381573 575034847 4561306 410989244 858430724 161584245 564525946 411191662 393570782 549661874 709608138 828717141 420163934 248884724 220212851 369316914 352955155 77472535 562353385 239663914 948813268 882516146 637863192 479969829 11060341 107418948 741496476 8988609 746073061 47187341 762153669 4159344 884098354 563790847 726149761 903975373 494826766 343191564 789811220 98723849 279985415 706606164 398120251 583795730 696214460 119458365 605116144 892957604 665491143 930365684 279605119 338416264 299953224 349966622 292427660 40810062 965031123 719396178 909327806 732778232 636919341 68754344 150440515 749933532 612151340 399040064 368493051 647562806 93219935 911212023 195692011 95055295 650697741 68105700 599206852 202102169 956992951 192904189 808875262 736483042 706814773 116607915 944030070 37030784 571403912 699987250 536521838 590745878 432226353 535323001 975179773 589094371 738286271 852448716 181451503 279552195 434660291 300472063 906687002 540118012 873055519 2166101 617224183 42267513 979439990 757481051 107909887 619974828 183137708 966505185 401226963 22007970 211986642 873119683 756021957 761051194 805324927 396560132 348861692 223031730 830439664 193742214 982424424 688707743 104074203 718269525 442994887 76026290 456774528 125147330 496602679 109917381 78759840 534095137 598981587 184347822 837294307 884784790 783304659 283297218 979523823 139446054 923231461 444991584 686159744 303926940 263405773 848396960 790067793 983265725 765262243 913945751 956802783 487252133 613753734 650290692 179323189 31885967 539274038 180733164 143371093 964386595 746902432 631244792 167048144 636091757 74637358 480151357 793965062 331924820 321126972 307145551 390609547 935380682 839600164 231849160 332278520 654182117 904116065 839547995 711639376 362673388 280980079 753946183 194073829 637112620 880677778 236894948 764693057 967098289 964811883 762423840 504411938 752599050 911885447 245040801 506713002 649897716 883297062 868161041 5913449 85902628 324688939 731636957 484601330 586256897 879476069 573488899 739447422 894542394 131365784 967585071 74511025 911673328 524156407 649562874 661184517 629651097 579009826 761275248 967589484 488119321 213484579 530112838 385536707 620596493 474323540 591677643 885260017 428893808 164663403 604298910 303907834 632918136 327880593 755676698 859519258 706368836 857912146 187175029 641181225 301110483 418315297 255471466 489179757 174542091 528697690 689434517 769527143 429861525 236168207 968384458 592100294 777881635 926518043 209135403 816503111 474030706 940603888 489170877 234554957 482910654 873113028 631900545 791814911 776275930 131542633 513305080 3541813 901642843 872367809 973927069 646804511 598859069 389634574 717824474 132502831 464778458 537027601 164823333 351720677 144203255 82339800 946354530 671378252 601470130 861367036 434007641 798730965 849991093 198725084 9961841 832302844 129325886 902834448 871336500 219918769 747875743 927262739 920075229 438502022 307649691 768577347 851877307 518568398 719322514 418807752 226279144 692824560 86773288 994753401 927814870 876679553 616839055 176655103 348018466 215112825 767720779 406711702 882869367 927854829 75766101 101010030 695696614 829697895 271065507 59077744 765945020 309659628 83470475 804701081 255447405 841084175 363573464 294067611 511188792 261952057 415603858 244884571 883467735