1 1 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 1 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 1 21 1 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 1 30 2 31 1 32 0 33 0 34 0 35 0 36 0 37 0 38 1 39 3 40 3 41 1 42 0 43 0 44 0 45 0 46 0 47 1 48 4 49 6 50 4 51 1 52 0 53 0 54 0 55 0 56 1 57 5 58 10 59 10 60 5 61 1 62 0 63 0 64 0 65 1 66 6 67 15 68 20 69 15 70 6 71 1 72 0 73 0 74 1 75 7 76 21 77 35 78 35 79 21 80 7 81 1 82 0 83 1 84 8 85 28 86 56 87 70 88 56 89 28 90 8 91 1 92 1 93 9 94 36 95 84 96 126 97 126 98 84 99 36 100 9 101 2 102 10 103 45 104 120 105 210 106 252 107 210 108 120 109 45 110 11 111 12 112 55 113 165 114 330 115 462 116 462 117 330 118 165 119 56 120 23 121 67 122 220 123 495 124 792 125 924 126 792 127 495 128 221 129 79 130 90 131 287 132 715 133 1287 134 1716 135 1716 136 1287 137 716 138 300 139 169 140 377 141 1002 142 2002 143 3003 144 3432 145 3003 146 2003 147 1016 148 469 149 546 150 1379 151 3004 152 5005 153 6435 154 6435 155 5006 156 3019 157 1485 158 1015 159 1925 160 4383 161 8009 162 11440 163 12870 164 11441 165 8025 166 4504 167 2500 168 2940 169 6308 170 12392 171 19449 172 24310 173 24311 174 19466 175 12529 176 7004 177 5440 178 9248 179 18700 180 31841 181 43759 182 48621 183 43777 184 31995 185 19533 186 12444 187 14688 188 27948 189 50541 190 75600 191 92380 192 92398 193 75772 194 51528 195 31977 196 27132 197 42636 198 78489 199 126141 200 167980 201 184778 202 168170 203 127300 204 83505 205 59109 206 69768 207 121125 208 204630 209 294121 210 352758 211 352948 212 295470 213 210805 214 142614 215 128877 216 190893 217 325755 218 498751 219 646879 220 705706 221 648418 222 506275 223 353419 224 271491 225 319770 226 516648 227 824506 228 1145630 229 1352585 230 1354124 231 1154693 232 859694 233 624910 234 591261 235 836418 236 1341154 237 1970136 238 2498215 239 2706709 240 2508817 241 2014387 242 1484604 243 1216171 244 1427679 245 2177572 246 3311290 247 4468351 248 5204924 249 5215526 250 4523204 251 3498991 252 2700775 253 2643850 254 3605251 255 5488862 256 7779641 257 9673275 258 10420450 259 9738730 260 8022195 261 6199766 262 5344625 263 6249101 264 9094113 265 13268503 266 17452916 267 20093725 268 20159180 269 17760925 270 14221961 271 11544391 272 11593726 273 15343214 274 22362616 275 30721419 276 37546641 277 40252905 278 37920105 279 31982886 280 25766352 281 23138117 282 26936940 283 37705830 284 53084035 285 68268060 286 77799546 287 78173010 288 69902991 289 57749238 290 48904469 291 50075057 292 64642770 293 90789865 294 121352095 295 146067606 296 155972556 297 148076001 298 127652229 299 106653707 300 98979526 301 114717827 302 155432635 303 212141960 304 267419701 305 302040162 306 304048557 307 275728230 308 234305936 309 205633233 310 213697353 311 270150462 312 367574595 313 479561661 314 569459863 315 606088719 316 579776787 317 510034166 318 439939169 319 419330586 320 483847815 321 637725057 322 847136256 323 1049021524 324 1175548582 325 1185865506 326 1089810953 327 949973335 328 859269755 329 903178401 330 1121572872 331 1484861313 332 1896157780 333 2224570106 334 2361414088 335 2275676459 336 2039784288 337 1809243090 338 1762448156 339 2024751273 340 2606434185 341 3381019093 342 4120727886 343 4585984194 344 4637090547 345 4315460747 346 3849027378 347 3571691246 348 3787199429 349 4631185458 350 5987453278 351 7501746979 352 8706712080 353 9223074741 354 8952551294 355 8164488125 356 7420718624 357 7358890675 358 8418384887 359 10618638736 360 13489200257 361 16208459059 362 17929786821 363 18175626035 364 17117039419 365 15585206749 366 14779609299 367 15777275562 368 19037023623 369 24107838993 370 29697659316 371 34138245880 372 36105412856 373 35292665454 374 32702246168 375 30364816048 376 30556884861 377 34814299185 378 43144862616 379 53805498309 380 63835905196 381 70243658736 382 71398078310 383 67994911622 384 63067062216 385 60921700909 386 65371184046 387 77959161801 388 96950360925 389 117641403505 390 134079563932 391 141641737046 392 139392989932 393 131061973838 394 123988763125 395 126292884955 396 143330345847 397 174909522726 398 214591764430 399 251720967437 400 275721300978 401 281034726978 402 270454963770 403 255050736963 404 250281648080 405 269623230802 406 318239868573 407 389501287156 408 466312731867 409 527442268415 410 556756027956 411 551489690748 412 525505700733 413 505332385043 414 519904878882 415 587863099375 416 707741155729 417 855814019023 418 993755000282 419 1084198296371 420 1108245718704 421 1076995391481 422 1030838085776 423 1025237263925 424 1107767978257 425 1295604255104 426 1563555174752 427 1849569019305 428 2077953296653 429 2192444015075 430 2185241110185 431 2107833477257 432 2056075349701 433 2133005242182 434 2403372233361 435 2859159429856 436 3413124194057 437 3927522315958 438 4270397311728 439 4377685125260 440 4293074587442 441 4163908826958 442 4189080591883 443 4536377475543 444 5262531663217 445 6272283623913 446 7340646510015 447 8197919627686 448 8648082436988 449 8670759712702 450 8456983414400 451 8352989418841 452 8725458067426 453 9798909138760 454 11534815287130 455 13612930133928 456 15538566137701 457 16846002064674 458 17318842149690 459 17127743127102 460 16809972833241 461 17078447486267 462 18524367206186 463 21333724425890 464 25147745421058 465 29151496271629 466 32384568202375 467 34164844214364 468 34446585276792 469 33937715960343 470 33888420319508 471 35602814692453 472 39858091632076 473 46481469846948 474 54299241692687 475 61536064474004 476 66549412416739 477 68611429491156 478 68384301237135 479 67826136279851 480 69491235011961 481 75460906324529 482 86339561479024 483 100780711539635 484 115835306166691 485 128085476890743 486 135160841907895 487 136995730728291 488 136210437516986 489 137317371291812 490 144952141336490 491 161800467803553 492 187120273018659 493 216616017706326 494 243920783057434 495 263246318798638 496 272156572636186 497 273206168245277 498 273527808808798 499 282269512628302 500 306752609140043 501 348920740822212 502 403736290724985 503 460536800763760 504 507167101856072 505 535402891434824 506 545362740881463 507 546733977054075 508 555797321437100 509 589022121768345 510 655673349962255 511 752657031547197 512 864273091488745 513 967703902619832 514 1042569993290896 515 1080765632316287 516 1092096717935538 517 1102531298491175 518 1144819443205445 519 1244695471730600 520 1408330381509452 521 1616930123035942 522 1831976994108577 523 2010273895910728 524 2123335625607183 525 2172862350251825 526 2194628016426713 527 2247350741696620 528 2389514914936045 529 2653025853240052 530 3025260504545394 531 3448907117144519 532 3842250890019305 533 4133609521517911 534 4296197975859008 535 4367490366678538 536 4441978758123333 537 4636865656632665 538 5042540768176097 539 5678286357785446 540 6474167621689913 541 7291158007163824 542 7975860411537216 543 8429807497376919 544 8663688342537546 545 8809469124801871 546 9078844414755998 547 9679406424808762 548 10720827125961543 549 12152453979475359 550 13765325628853737 551 15267018418701040 552 16405667908914135 553 17093495839914465 554 17473157467339417 555 17888313539557869 556 18758250839564760 557 20400233550770305 558 22873281105436902 559 25917779608329096 560 29032344047554777 561 31672686327615175 562 33499163748828600 563 34566653307253882 564 35361471006897286 565 36646564379122629 566 39158484390335065 567 43273514656207207 568 48791060713765998 569 54950123655883873 570 60705030375169952 571 65171850076443775 572 68065817056082482 573 69928124314151168 574 72008035386019915 575 75805048769457694 576 82431999046542272 577 92064575369973205 578 103741184369649871 579 115655154031053825 580 125876880451613727 581 133237667132526257 582 137993941370233650 583 141936159700171083 584 147813084155477609 585 158237047815999966 586 174496574416515477 587 195805759739623076 588 219396338400703696 589 241532034482667552 590 259114547584139984 591 271231608502759907 592 279930101070404733 593 289749243855648692 594 306050131971477575 595 332733622232515443 596 370302334156138553 597 415202098140326772 598 460928372883371248 599 500646582066807536 600 530346156086899891 601 551161709573164640 602 569679344926053425 603 595799375827126267 604 638783754203993018 605 703035956388653996 606 785504432296465325 607 876130471023698020 608 961574954950178784 609 1030992738153707427 610 1081507865660064531 611 1120841054499218065 612 1165478720753179692 613 1234583130031119285 614 1341819710592647014 615 1488540388685119321 616 1661634903320163345 617 1837705425973876804 618 1992567693103886211 619 2112500603813771958 620 2202348920159282596 621 2286319775252397757 622 2400061850784298977 623 2576402840623766299 624 2830360099277766335 625 3150175292005282666 626 3499340329294040149 627 3830273119077763015 628 4105068296917658169 629 4314849523973054554 630 4488668695411680353 631 4686381626036696734 632 4976464691408065276 633 5406762939901532634 634 5980535391283049001 635 6649515621299322815 636 7329613448371803164 637 7935341415995421184 638 8419917820890712723 639 8803518219384734907 640 9175050321448377087 641 9662846317444762010 642 10383227631309597910 643 11387298331184581635 644 12630051012582371816 645 13979129069671125979 646 15264954864367224348 647 16355259236886133907 648 17223436040275447630 649 17978568540833111994 650 18837896638893139097 651 20046073948754359920 652 21770525962494179545 653 24017349343766953451 654 26609180082253497795 655 29244083934038350327 656 31620214101253358255 657 33578695277161581537 658 35202004581108559624 659 36816465179726251091 660 38883970587647499017 661 41816599911248539465 662 45787875306261132996 663 50626529426020451246 664 55853264016291848122 665 60864298035291708582 666 65198909378414939792 667 68780699858270141161 668 72018469760834810715 669 75700435767373750108 670 80700570498896038482 671 87604475217509672461 672 96414404732281584242 673 106479793442312299368 674 116717562051583556704 675 126063207413706648374 676 133979609236685080953 677 140799169619104951876 678 147718905528208560823 679 156401006266269788590 680 168305045716405710943 681 184018879949791256703 682 202894198174593883610 683 223197355493895856072 684 242780769465290205078 685 260042816650391729327 686 274778778855790032829 687 288518075147313512699 688 304119911794478349413 689 324706051982675499533 690 352323925666196967646 691 386913078124385140313 692 426091553668489739682 693 465978124959186061150 694 502823586115681934405 695 534821595506181762156 696 563296854003103545528 697 592637986941791862112 698 628825963777153848946 699 677029977648872467179 700 739237003790582107959 701 813004631792874879995 702 892069678627675800832 703 968801711074867995555 704 1037645181621863696561 705 1098118449509285307684 706 1155934840944895407640 707 1221463950718945711058 708 1305855941426026316125 709 1416266981439454575138 710 1552241635583456987954 711 1705074310420550680827 712 1860871389702543796387 713 2006446892696731692116 714 2135763631131149004245 715 2254053290454180715324 716 2377398791663841118698 717 2527319892144972027183 718 2722122922865480891263 719 2968508617022911563092 720 3257315946004007668781 721 3565945700123094477214 722 3867318282399275488503 723 4142210523827880696361 724 4389816921585329719569 725 4631452082118021834022 726 4904718683808813145881 727 5249442815010452918446 728 5690631539888392454355 729 6225824563026919231873 730 6823261646127102145995 731 7433263982522369965717 732 8009528806227156184864 733 8532027445413210415930 734 9021269003703351553591 735 9536170765926834979903 736 10154161498819266064327 737 10940074354898845372801 738 11916456102915311686228 739 13049086209154021377868 740 14256525628649472111712 741 15442792788749526150581 742 16541556251640366600794 743 17553296449116561969521 744 18557439769630186533494 745 19690332264746101044230 746 21094235853718111437128 747 22856530457814157059029 748 24965542312069333064096 749 27305611837803493489580 750 29699318417398998262293 751 31984349040389892751375 752 34094852700756928570315 753 36110736218746748503015 754 38247772034376287577724 755 40784568118464212481358 756 43950766311532268496157 757 47822072769883490123125 758 52271154149872826553676 759 57004930255202491751873 760 61683667457788891013668 761 66079201741146821321690 762 70205588919503677073330 763 74358508253123036080739 764 79032340152840500059082 765 84735334429996480977515 766 91772839081415758619282 767 100093226919756316676801 768 109276084405075318305549 769 118688597712991382765541 770 127762869198935712335358 771 136284790660650498395020 772 144564097172626713154069 773 153390848405963536139821 774 163767674582836981036597 775 176508173511412239596797 776 191866066001172075296083 777 209369311324831634982350 778 227964682118066701071090 779 246451466911927095100899 780 264047659859586210730378 781 280848887833277211549089 782 297954945578590249293890 783 317158522988800517176418 784 340275848094249220633394 785 368374239512584314892880 786 401235377326003710278433 787 437333993442898336053440 788 474416149029993796171989 789 510499126771513305831277 790 544896547692863422279467 791 578803833411867460842979 792 615113468567390766470308 793 657434371083049737809812 794 708650087606833535526274 795 769609616838588025171313 796 838569370768902046331873 797 911750142472892132225429 798 984915275801507102003266 799 1055395674464376728110744 800 1123700381104730883122446 801 1193917301979258227313287 802 1272547839650440504280120 803 1366084458689883273336086 804 1478259704445421560697587 805 1608178987607490071503186 806 1750319513241794178557302 807 1896665418274399234228695 808 2040310950265883830114010 809 2179096055569107611233190 810 2317617683083989110435733 811 2466465141629698731593407 812 2638632298340323777616206 813 2844344163135304834033673 814 3086438692052911632200773 815 3358498500849284250060488 816 3646984931516193412785997 817 3936976368540283064342705 818 4219407005834991441347200 819 4496713738653096721668923 820 4784082824713687842029140 821 5105097439970022509209613 822 5482976461475628611649879 823 5930782855188216466234446 824 6444937192902195882261261 825 7005483432365477662846485 826 7583961300056476477128702 827 8156383374375274505689905 828 8716120744488088163016123 829 9280796563366784563698063 830 9889180264683710351238753 831 10588073901445651120859492 832 11413759316663845077884325 833 12375720048090412348495707 834 13450420625267673545107746 835 14589444732421954139975187 836 15740344674431750982818607 837 16872504118863362668706028 838 17996917307854872726714186 839 19169976828050494914936816 840 20477254166129361472098245 841 22001833218109496198743817 842 23789479364754257426380032 843 25826140673358085893603453 844 28039865357689627685082933 845 30329789406853705122793794 846 32612848793295113651524635 847 34869421426718235395420214 848 37166894135905367641651002 849 39647230994179856387035061 850 42479087384238857670842062 851 45791312582863753625123849 852 49615620038112343319983485 853 53866006031047713578686386 854 58369654764543332807876727 855 62942638200148818774318429 856 67482270220013349046944849 857 72036315562623603037071216 858 76814125130085224028686063 859 82126318378418714057877123 860 88270399967102611295965911 861 95406932620976096945107334 862 103481626069160056898669871 863 112235660795591046386563113 864 121312292964692151582195156 865 130424908420162167821263278 866 139518585782636952084016065 867 148850440692708827065757279 868 158940443508503938086563186 869 170396718345521325353843034 870 183677332588078708241073245 871 198888558690136153843777205 872 215717286864751103285232984 873 233547953760283197968758269 874 251737201384854319403458434 875 269943494202799119905279343 876 288369026475345779149773344 877 307790884201212765152320465 878 329337161854025263440406220 879 354074050933600033594916279 880 382565891278214862084850450 881 414605845554887257129010189 882 449265240625034301253991253 883 485285155145137517372216703 884 521680695587653439308737777 885 558312520678144899055052687 886 596159910676558544302093809 887 637128046055238028592726685 888 683411212787625297035322499 889 736639942211814895679766729 890 797171736833102119213860639 891 863871086179921558383001442 892 934550395770171818626207956 893 1006965850732790956680954480 894 1079993216265798338363790464 895 1154472431354703443357146496 896 1233287956731796572894820494 897 1320539258842863325628049184 898 1420051154999440192715089228 899 1533811679044917014893627368 900 1661042823013023677596862081 901 1798421481950093377009209398 902 1941516246502962775307162436 903 2086959066998589295044744944 904 2234465647620501781720936960 905 2387760388086500016251966990 906 2553827215574659898522869678 907 2740590413842303518343138412 908 2953862834044357207608716596 909 3194854502057940692490489449 910 3459464304963117054606071479 911 3739937728453056152316371834 912 4028475313501552070351907380 913 4321424714619091076765681904 914 4622226035707001797972903950 915 4941587603661159914774836668 916 5294417629416963416866008090 917 5694453247886660725951855008 918 6148717336102297900099206045 919 6654318807021057747096560928 920 7199402033416173206922443313 921 7768413041954608222668279214 922 8349900028120643147117589284 923 8943650750326092874738585854 924 9563813639368161712747740618 925 10236005233078123331640844758 926 10988870877303624142817863098 927 11843170583988958626051061053 928 12803036143123355647195766973 929 13853720840437230954019004241 930 14967815075370781429590722527 931 16118313070075251369785868498 932 17293550778446736021856175138 933 18507464389694254587486326472 934 19799818872446285044388585376 935 21224876110381747474458707856 936 22832041461292582768868924151 937 24646206727112314273246828026 938 26656756983560586601214771214 939 28821535915808012383609726768 940 31086128145446032799376591025 941 33411863848521987391642043636 942 35801015168140990609342501610 943 38307283262140539631874911848 944 41024694982828032518847293232 945 44056917571674330243327632007 946 47478248188404897042115752177 947 51302963710672900874461599240 948 55478292899368598984824497982 949 59907664061254045182986317793 950 64497991993968020191018634661 951 69212879016662978000984545246 952 74108298430281530241217413458 953 79331978244968572150722205080 954 85081612554502362762174925239 955 91535165760079227285443384184 956 98781211899077797916577351417 957 106781256610041499859286097222 958 115385956960622644167810815775 959 124405656055222065374004952454 960 133710871010630998192003179907 961 143321177446944508242201958704 962 153440276675250102391939618538 963 164413590799470934912897130319 964 176616778314581590047618309423 965 190316377659157025202020735601 966 205562468509119297775863448639 967 222167213570664144027096912997 968 239791613015844709541815768229 969 258116527065853063566008132361 970 277032048457575506434205138611 971 296761454122194610634141577242 972 317853867474721037304836748857 973 341030369114052524960515439742 974 366933155973738615249639045024 975 395878846168276322977884184240 976 427729682079783441802960361636 977 461958826586508853568912681226 978 497908140081697773107823900590 979 535148575523428570000213270972 980 573793502579770117068346715853 981 614615321596915647938978326099 982 658884236588773562265352188599 983 707963525087791140210154484766 984 762812002142014938227523229264 985 823608528248059764780844545876 986 889688508666292295371873042862 987 959866966668206626676736581816 988 1033056715605126343108037171562 989 1108942078103198687068559986825 990 1188408824176685765007325041952 991 1273499558185689210204330514698 992 1366847761676564702475506673365 993 1470775527229806078437677714030 994 1586420530390074703008367775140 995 1713297036914352060152717588738 996 1849555475334498922048609624678 997 1992923682273332969784773753378 998 2141998793708325030176597158387 999 2297350902279884452075885028777 1000 2461908382362374975211655556650