2 2 3 5 6 6 9 11 10 12 16 18 18 23 27 27 31 37 40 40 48 56 57 65 79 89 95 112 130 137 153 176 193 205 229 259 278 308 347 379 406 450 502 533 578 643 699 749 827 920 989 1076 1192 1296 1391 1520 1669 1794 1940 2128 2306 2481 2709 2961 3180 3426 3736 4034 4323 4680 5076 5447 5861 6362 6864 7368 7964 8615 9242 9936 10743 11559 12388 13357 14410 15432 16565 17863 19184 20517 22037 23691 25330 27128 29143 31217 33355 35764 38367 40979 43835 47012 50280 53670 57445 61514 65631 70090 75020 80107 85404 91213 97464 103867 110738 118250 126044 134232 143147 152686 162510 173027 184489 196406 208892 222429 236900 251883 267856 285177 303272 322242 342705 364481 387138 411230 437163 464299 492793 523447 555943 589821 625830 664489 704971 747404 792901 841124 891484 944881 1001979 1061895 1124823 1192057 1263217 1337663 1416577 1500645 1588840 1681498 1780180 1884506 1993630 2109149 2231975 2360887 2496254 2640056 2792077 2951203 3119353 3297699 3484962 3681744 3890358 4110518 4341142 4584746 4842751 5113496 5397939 5699095 6016612 6349254 6700025 7071045 7460340 7869120 8301173 8756308 9233368 9735838 10266524 10823329 11408033 12025183 12674522 13355159 14071624 14827420 15620121 16452042 17329240 18251786 19218657 20235435 21306747 22430490 23609318 24850724 26155281 27522380 28959153 30471027 32056344 33718812 35467977 37304694 39228815 41249917 43374805 45601977 47936312 50390273 52965841 55663190 58494300 61468319 64584744 67850292 71279967 74877272 78643862 82595133 86742491 91086031 95635834 100410691 105416019 110654733 116146734 121907527 127938412 134252929 140874736 147812966 155072641 162678495 170651188 178994957 187728048 196879868 206463394 216487879 226985359 237982251 249485792 261520836 274126144 287319271 301114210 315551853 330667775 346474664 363004465 380306968 398407270 417327428 437118930 457828107 479475792 502105102 525779691 550533564 576399425 603444662 631729287 661283453 692165101 724456990 758206716 793459183 830301612 868813367 909040019 951057518 994970375 42601840 90503996 140545108 192827037 247415806 304413579 363954650 426130861 491029016 558797113 629568902 703436003 780533313 861035057 945066769 34502527 126021120 221554568 321231542 425230400 533773759 647031012 765167231 888427093 18795809 152937108 292845071 438807937 591050240 749795068 915359632 89803459 269851643 457572769 653339790 857454941 71975026 293796310 525071599 766123509 19119252 281026828 554003250 838454011 136663826 445636779 767562394 104736062 454269475 818448904 199566661 594797867 8327173 437226360 883951341 351063221 835754841 342251831 867928281 417167763 987240259 582573712 202451184 846040575 517799335 217120082 943379930 701121458 489785304 310714843 165124318 54255855 977836105 940851376 942907747 985561901 72295498 201193033 375643713 597557841 868842955 193045763 568685332 1493778 490042234 39977483 650257696 326867216 70393019 881709364 767191861 727803515 766327457 885939919 91595674 382851026 764863141 243069064 817488960 495266777 278732761 172009906 179095764 304389827 552629805 928386217 438131518 85364383 873651779 811696683 903411186 156640273 573794149 164496252 931973465 886587161 35074839 381230530 934610626 704614873 697393892 921598033 387778051 102886106 76322807 318086572 838035574 648109033 757639213 179675870 921947317 1778949 426695177 212907085 371764488 917451402 866188150 232457653 29971402 275074317 984067936 177305607 867660219 78907183 824378266 129139259 10558441 489537501 589423527 333357062 743252460 844723030 663070226 224908150 555237923 683471662 639096600 452314666 153660290 773691388 349812498 912686135 501168070 151060414 899108510 787825971 856637092 150423957 709285788 581812945 813997198 456599707 557638830 171267775 350511551 152673887 633431026 855193079 880223659 771914736 596862855 424607344 325775863 373394283 644418127 219645984 177929673 603763304 587056096 217515040 586120196 792104023 935665756 120920590 451455106 42357690 5614108 458833637 527133747 337356677 19231872 706591387 544041793 673856754 246680988 416676475 346008705 198890730 146711883 367641248 45600996 367096780 530694547 738946793 201194189 132088003 756367543 307574628 21673169 146854132 938581292 662375789 589348905 4461491 196063541 465659110 127554058 501828061 920562007 729114776 283890001 948539414 105883364 145548707 474197942 509459092 683557276 446289897 257277975 591412027 944443239 827003084 761957893 294077308 984207481 415112960 181601697 903633762 225237541 799545441 313233640 470115909 996661016 644923675 192138279 439121503 212976338 367828668 789424839 389616935 106430342 913218366 818185362 853081932 90718245 635632676 630324239 250727694 714365189 281111894 242043433 936181022 751737699 112549566 486771756 401016915 424757013 175110649 324378738 603092110 791066344 725384434 308478013 499050965 316851582 848199176 254429449 751930601 635229913 275506522 116325230 673402076 552302093 441053209 107318466 405280575 291172809 807772523 93280936 385171606 34099242 482898792 288944395 127220089 784711356 166203961 300109536 351085945 603782942 479907677 548117493 517795177 238619389 719193696 134843112 805477071 227182766 71706026 186622056 593830219 514491416 367070892 758647917 506528457 648688783 440157508 350614860 94162954 628092852 149335474 104764159 219817622 483985809 156746562 792294980 253105329 685243075 556379303 668269672 152410127 468617466 448066833 290671900 556298552 195653592 569914983 448102219 7749600 873792912 135064626 316609800 427331268 981853379 994370358 983703760 23062480 739374841 319339045 528889049 760980335 21353654 934599197 810836048 640963589 96684555 568171126 213727738 938119454 423406153 173275146 535943632 697147009 726844169 628265060 330061279 705882114 647033512 75368753 936890403 272257988 254519167 197852193 577406222 111938679 778464172 823466226 820029006 737633119 938219522 213908604 867409872 755740802 281140493 473978066 73651622 521648732 14990506 597065287 209608732 687361761 863194668 649719801 49153866 204865179 525701189 730445854 864183073 409051274 384397806 368024552 558752988 916779665 225211222 108908459 171448545 113678389 758056375 136905690 641574168 112865028 863760724 845432845 778745652 200646905 559106499 409714737 499477820 826709818 817947943 495845012 534413640 386086086 497732745 428941703 922278772 119139600 748371959 219443870 756321005 669614811 488559982 64376821 813385201 963097418 645036956 83850700 895552337 273826178 102323259 259183733 894553702 567490066 465360360 763412865 841158381 445627018 37163990 124842993 441674725 220288618 603365066 916410488 876079707 1083197 4639283 25730324 958230529 946779422 703091187 779793814 59157121 217541363 17791897 709160020 612059400 507119888 978202652 991429792 452979254 564619635 327335180 212787886 652582626 464660172 531804096 476432115 104413808 7538130 366714747 545648312 614415708 166167163 111530826 239407595 943677158 176447545 158253486 42834740 876815017 558932868 519740404 613391964 237334035 205630727 558219126 712843569 596107845 498175594 141317546 6645604 399545850 441576142 437313660 230183850 252559310 814648923 682301492 361186624 314024712 593454542 456891479 653566297 983364348 165126973 389451028 814708232 506952459 363173925 695177233 104872253 692890476 958928973 603212934 842712423 718550910 20007371 536854119 702696611 865934248 498040040 948893978 202664407 214996008 636804956 940433672 169710913 610494779 93309572 258771883 424975790 841710270 415053017 16227489 730776537 781831279 438126302 483556182 136304080 465552099 389265115 597415038 227262452 531675884 86039313 478931691 581866842 342637944 535000199 328411917 861775140 329183436 605297112 512858181 584815560 799185245 211072584 605314223 638316934 585920340 786875709 573787370 176845395 626495148 703802659 326865055 643100737 886672144 688677537 390326315 457334236 959797698 477050990 774830991 345023637 365271524 702605276 123453377 591057019 985023736 681838966 76292512 525195674 360935998 233339771 592411250 554040984 747642617 215710819 704525644 80757082 212681403 47209290 41862489 716882687 370446531 174854020 450106322 583728450 169595140 516094041 414163972 191350962 161034262 299175259 759084392 672746704 317463767 696643932 584050697 942597268 669622426 373946142 525728225 990839703 154089950 666927155 626019060 135016896 159112238 838198523 213381169 736117432 644546636 745595246 743519599 109094341 517610570 756712941 653217433 81295382 446260387 850859816 100355103 413532246 676329471 982892145 524971450 21832708 6651819 302034020 369715921 270421120 249418647 966956343 372032061 616196215 576539619 437661567 10127926 29424927 459875325 557112520 239109237 483733789 57816573 113101776 200401201 677147826 49380099 909709214 434152238 464597876 697359263 739272692 45220186 984656048 893292926 210906274 608071539 446363786 655714955 50700405 31645228 696488705 723097616 631144027 704537290 985612874 319364956 120691767 61515136 288403643 530475483 247084032 588073854 147439932 839714749 309154463 730784361 123226823 155135494 653025704 723109995