1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958 2436 3010 3718 4565 5604 6842 8349 10143 12310 14883 17977 21637 26015 31185 37338 44583 53174 63261 75175 89134 105558 124754 147273 173525 204226 239943 281589 329931 386155 451276 526823 614154 715220 831820 966467 1121505 1300156 1505499 1741630 2012558 2323520 2679689 3087735 3554345 4087968 4697205 5392783 6185689 7089500 8118264 9289091 10619863 12132164 13848650 15796476 18004327 20506255 23338469 26543660 30167357 34262962 38887673 44108109 49995925 56634173 64112359 72533807 82010177 92669720 104651419 118114304 133230930 150198136 169229875 190569292 214481126 241265379 271248950 304801365 342325709 384276336 431149389 483502844 541946240 607163746 679903203 761002156 851376628 952050665 65900098 190663895 329465723 483829790 655424312 846105207 59659345 294832206 555849535 845451794 168394293 524489633 919131236 358101188 842294458 380093635 973317739 631364771 358919041 163085871 51636899 33138150 116957133 313409595 633773306 92212840 698779560 471894966 426095697 579278679 950993537 564455068 441341388 607355848 92314139 923461193 139628697 772315124 865141262 462012100 609054799 360405990 771416529 906275738 833026314 626013695 366234773 142138747 50053451 195111874 691771539 666639862 255594678 605020267 877836865 251420055 913251795 76618770 962404109 822066609 921404275 553300909 34034576 705835739 945788142 161764778 791147031 318294510 261388533 186925784 707583568 492066304 261781722 799651371 957983888 659334583 901645133 770593893 440370753 183625235 378560468 520156484 226737408 249156795 484054969 984748801 974388392 857051217 234580494 918185048 954527725 634670238 515722183 445077675 579794696 414291632 801431761 987720613 638394517 870178779 291543752 33715345 794517524 887745844 280887521 647955762 430130843 886074754 162524015 352062132 574911451 54296007 193312239 674712845 552038125 352793690 189230129 879235639 77164040 400735924 589624482 658601669 65624947 892508782 48557230 464688729 331001112 329403841 889995699 475500379 861252717 469588872 691170891 264705550 649346389 458195434 887138222 209782361 269037098 43971933 218622830 821886406 889325156 187382610 967812066 811884457 484002394 887640010 63450972 262987839 98299076 771593907 383990750 340730457 843511181 507823585 52277122 146853832 351251488 216499848 493180960 534144102 811891188 655571237 123636580 117094772 660996042 450788085 581470848 590750961 710078662 460134446 492119591 815657844 313127518 674106755 677754166 938227344 44335259 224125257 465248142 226282178 648144777 460756077 440770104 653776934 337732887 649838717 162400242 318354477 743319506 646334976 175253689 12190819 56222424 493429286 105789849 135583136 564698016 148043463 31482428 362307250 697725463 639765511 516058350 567257844 451998122 563903916 977922801 561057532 47272858 677426091 204766717 877102285 249312206 455457467 804721330 406668585 647561386 348874540 386019979 687807486 411064623 261801278 795426797 744925279 201914823 814710748 855846812 386342668 412806344 397320431 1856002 566839979 256373010 467433290 501008738 238424247 841286193 422276938 710990148 879060957 598595750 674806840 438786365 422967183 604520316 981597818 853854428 839863082 122733852 232346565 998034201 297756422 357229054 630580603 153383543 764261987 343100308 827643896 416787078 179799071 727027885 707610976 35681188 211760660 980641197 291472680 174788100 234477796 765049764 944960237 625625204 986747847 149364895 901162343 292379156 236803268 589729867 983473344 632172390 663347932 71937595 204211351 878003336 560659972 802120713 57680992 315037078 519256288 619426225 243341899 432731653 671201605 407132464 772643850 708202897 895227873 939147131 226158980 352569460 914435167 299520730 934369952 772742943 485995804 604670993 588546875 873455643 858719939 162418614 568367797 798470924 541010750 200290248 488926113 234313052 874979491 640523709 997432022 702040684 20374921 595836497 474555404 781133116 538144151 186008554 358877508 689373802 503521687 610029653 777949585 875515482 510024362 446858044 575465827 661307142 436737769 88462778 524987762 342495404 941692332 849747892 265936873 474948616 504773762 980535445 926283826 850237717 542565546 670680741 945566215 400298023 932584250 223091750 988775482 764090093 907541246 46975882 837301480 742593756 821767311 788530091 14726414 928267519 407069515 140702566 414504959 979766137 967617451 160137671 723532467 182763772 440402269 931186076 93827269 410332422 437279964 361933481 768590964 971594332 290703335 345466613 509333323 783462874 700353811 998053423 695951817 968864185 90095664 788791868 788761100 436614829 944874145 971493851 738271130 183243673 34774568 56758830 214436801 191896749 587528771 500141973 23540487 785603665 157077956 238433306 937355474 719458860 644981523 601727492 974161715 582979776 262643364 900743161 668102774 291458116 96158293 528478740 523557563 516686878 714732850 950939990 249233922 536896158 75194299 771341153 950483521 270778323 604775300 216263990 471103356 625882994 905760934 47380774 672036655 238972924 467847383 487383322 592822269 64651127 190732804 723176670 273170105 93887238 442259364 871192639 108961565 323860103 964113996 435156570 509930788 912665398 137156811 631881170 899471585 379261415 892227493 870186981 752674172 420308409 288714420 259450487 60137990 784029219 103308331 18767654 813937043 807262118 565177768 435408279 440012083 204043508 774136467 391511503 624960526 415127819 18663124 916889038 368890232 290699953 686979750 354240350 667670640 65917821 724286121 182485354 50300926 876125785 625540587 941717530 729342041 748502400 500913016 210793097 846191623 118956886 333998542 512187512 301206680 136457637 828534063 160202680 702054616 370854192 586614093 754004000 492174262 54017789 87356589 77174753 986421568 885740997 915664840 55707369 256270130 818238524 243590297 211465908 222654292 69227307 684256149 397761107 179317834 284867895 559521640 469525298 413738695 493672410 247355194 488052822 116648940 82360933 338862728 579625137 345128610 76204974 863709100 669987573 355155322 444072928 243817512 356463449 463459593 298559809 975898201 985312380 922853455 265621322 852865881 841637188 724055455 623176675 426498198 713980612 668762485 782024479 929630262 105744172 214446631 685346825 819180452 163782850 897152280 987005893 106366649 394919291 563523726 105759072 578252092 314832095 78389495 914348923 755165455 809899394 119303216 127490327 714292700 120828384 956776274 299771298 993554713 187306355 204199590 910814072 531107155 567294434 651831275 212531355 625475178 804603285 858322687 83951792 388068814 826110444 736537262 721853880 816834141 403794204 827338988 797144838 401862965 960744572 450199759 745709343 619306678 487425723 180456559 771505384 926679712 695253620 13555904 77586782 873712396 548049524 466368066 744907768 818357987 537941008 785826835 883606217 591211890 78188951 469929316 381731314 184205912 662910437 55472297 915686014 289905960 231613465 765944711 315513824 745453129 436276845 987804192 35759274 503726461 736624761 715784498 484524517 264459758 360075815 696481968 731902013 735430558 45706580 900537480 380544360 3006536 540279196 129058964 315151519 595822747 762122041 610380031 577868986 913488707 713329029 686413200 881512809 980629241 265532172 655412847 401015385 708510839 261380697 821253712 410793417 947999133 789464437 981803405 619413293 211806896 491884113 616965309 991008959 200018177 767763083 207177876 198832980 303393975 407426187 472739479 590881950 527179629 384933555 912415242 228674427 615633542 403492563 183370622 178855437 219843327 801012532 506520143 784152044 452823881 364081481 554118269 785359874 233868341 331555165 197645500 444126703 29122145 471267272 420415731 971993054 112939867 323234900 967384697 46362306 218639399 439763972 491141903 378157063 503310307 172240346 167076640 103123259 221460673 332968449 203243498 218028019 159293145 303294013 193889672 377556164 562948699 960053773 965956377 995720833 434046990 235693016 187101362 461407065 544027140 552358863 662429610 159502303 287775078 832232334 310487049 577056990 901531574 832483138 585465157 876287633 400598563 193324737 538046772 10629153 832384477 706971434 990848907 181970574 819840435 468346181 560672362 719302476 882705335 970731110 805164463 209415733 692608781 687889213 26644634 584798183 514404889 720643756 411805032 386866238 410945248 83088389 233727403 808363787 989403188 674235138 909568920 127868104 431752887 449794972 4537640 146047107 91463170 721594215 412498730 267916527 849719397 601967950 110475850 545934663 134006225 751102193 975509535 985542976 99377406 693208521 338074175 141142805 562494825 975275507 718144722 883095620 113810422 745330911 286116140 196581551 813371701 994512491 482643939 20935422 835089413 603887826 751133120 456535300 781768306 669594459 312769781 681327493 811911747 770957190 873513813 574165984 964782943 158893099 783375126 945489723 769508102 661753388 469024085 190294698 113524554 582033654 707574255 7804223 299717098 42027048 979230240 500126858 217557292 825983573 472154800 293441142 156076708 950045408 987677675 825062835 558779385 45118111 879768565 459134695 775265644 303676317 746614293 921136002 520876490 550864078 107387303 961431801 21822685 548070138 911355084 722302533 850552632 790837477 980908098 524414757 53257632 471087673 466358153 971065097 390687549 925200477 683696000 38543258 908902409 960421753 927747168 134625524 37374371 78278640 293093312 761650898 627356119