0 1 1 1 2 1 3 2 4 3 5 4 6 6 7 8 8 11 9 15 10 20 11 26 12 34 13 44 14 56 15 72 16 91 17 114 18 143 19 178 20 220 21 272 22 334 23 408 24 498 25 605 26 732 27 884 28 1064 29 1276 30 1528 31 1824 32 2171 33 2580 34 3058 35 3616 36 4269 37 5028 38 5910 39 6936 40 8124 41 9498 42 11088 43 12922 44 15034 45 17468 46 20264 47 23472 48 27154 49 31369 50 36189 51 41700 52 47988 53 55156 54 63324 55 72616 56 83176 57 95172 58 108780 59 124202 60 141672 61 161436 62 183776 63 209016 64 237499 65 269616 66 305812 67 346562 68 392406 69 443952 70 501856 71 566856 72 639781 73 721530 74 813108 75 915642 76 1030354 77 1158608 78 1301928 79 1461968 80 1640572 81 1839789 82 2061850 83 2309234 84 2584688 85 2891208 86 3232110 87 3611064 88 4032074 89 4499562 90 5018412 91 5593952 92 6232056 93 6939200 94 7722448 95 8589576 96 9549138 97 10610466 98 11783817 99 13080454 100 14512663 101 16093924 102 17839020 103 19764072 104 21886740 105 24226368 106 26804036 107 29642810 108 32767924 109 36206860 110 39989656 111 44149128 112 48721000 113 53744274 114 59261508 115 65319008 116 71967268 117 79261332 118 87261054 119 96031632 120 105644072 121 116175527 122 127709964 123 140338740 124 154161056 125 169284776 126 185827144 127 203915392 128 223687739 129 245294292 130 268897840 131 294675074 132 322817724 133 353533584 134 387048006 135 423605328 136 463470182 137 506929338 138 554293488 139 605898906 140 662109728 141 723320160 142 789956600 143 862480440 144 941390805 145 1027227248 146 1120573178 147 1222059282 148 1332366908 149 1452232276 150 1582450734 151 1723880984 152 1877450274 153 2044159662 154 2225089296 155 2421404800 156 2634363768 157 2865322364 158 3115743152 159 3387203112 160 3681401852 161 4000171200 162 4345485101 163 4719469794 164 5124415566 165 5562788944 166 6037245270 167 6550643112 168 7106059248 169 7706804181 170 8356439784 171 9058797678 172 9817998362 173 10638472780 174 11524984840 175 12482654952 176 13516986346 177 14633892660 178 15839726826 179 17141313170 180 18545981156 181 20061600756 182 21696621600 183 23460114168 184 25361813048 185 27412164624 186 29622377280 187 32004474260 188 34571351664 189 37336839584 190 40315766584 191 43524030144 192 46978671058 193 50697951938 194 54701442722 195 59010111072 196 63646417819 197 68634420676 198 73999883922 199 79770394312 200 85975486719 201 92646777060 202 99818102900 203 107525675488 204 115808240676 205 124707249256 206 134267040728 207 144535037928 208 155561953108 209 167402009844 210 180113178176 211 193757423602 212 208400974828 213 224114607504 214 240973944750 215 259059779880 216 278458418388 217 299262040320 218 321569088828 219 345484681972 220 371121049160 221 398597998488 222 428043412152 223 459593771488 224 493394718568 225 529601651571 226 568380355730 227 609907677602 228 654372239820 229 701975198564 230 752931052320 231 807468499104 232 865831344964 233 928279473114 234 995089871076 235 1066557719232 236 1142997551050 237 1224744482720 238 1312155516144 239 1405610926704 240 1505515733928 241 1612301259666 242 1726426786599 243 1848381315542 244 1978685427076 245 2117893261860 246 2266594618524 247 2425417175896 248 2595028855456 249 2776140323652 250 2969507642184 251 3175935083882 252 3396278114904 253 3631446552688 254 3882407919488 255 4150190993424 256 4435889568059 257 4740666443010 258 5065757648724 259 5412476918560 260 5782220433552 261 6176471844548 262 6596807587462 263 7044902520072 264 7522535887196 265 8031597632848 266 8574095091408 267 9152160067284 268 9768056324834 269 10424187524908 270 11123105620528 271 11867519737232 272 12660305579526 273 13504515379392 274 14403388416954 275 15360362160498 276 16379084045904 277 17463423931092 278 18617487279054 279 19845629094624 280 21152468656928 281 22542905108394 282 24022133931744 283 25595664363978 284 27269337816936 285 29049347343120 286 30942258204040 287 32955029620944 288 35095037754805 289 37370099982803 290 39788500562800 291 42359017742404 292 45090952391662 293 47994158263972 294 51079073953590 295 54356756642280 296 57838917754908 297 61537960606344 298 65467020147620 299 69640004949024 300 74071641518682 301 78777521082576 302 83774148984488 303 89078996823048 304 94710557473090 305 100688403173616 306 107033246821422 307 113767006642450 308 120912874450352 309 128495387657168 310 136540505236864 311 145075687882680 312 154129982553528 313 163734111643146 314 173920567049580 315 184723709375456 316 196179872530960 317 208327474059676 318 221207131458328 319 234861784807000 320 249336826078972 321 264680235448404 322 280942724964544 323 298177890017604 324 316442368969863 325 335796011380732 326 356302055315622 327 378027314176728 328 401042373553438 329 425421798657408 330 451244352854928 331 478593227874266 332 507556286339986 333 538226317232796 334 570701304945560 335 605084712687432 336 641485780934384 337 680019841704370 338 720808649523925 339 763980729900324 340 809671746201592 341 858024885943616 342 909191267432778 343 963330367809168 344 1020610473642666 345 1081209155185344 346 1145313765490044 347 1213121965724042 348 1284842277959832 349 1360694666843452 350 1440911151672408 351 1525736450371440 352 1615428656986666 353 1710259954463394 354 1810517364434356 355 1916503535892256 356 2028537574780350 357 2146955916503328 358 2272113243523510 359 2404383450385512 360 2544160658488836 361 2691860283108671 362 2847920155364292 363 3012801701819214 364 3186991184599904 365 3371001005141480 366 3565371074664648 367 3770670254715632 368 3987497871346872 369 4216485306526854 370 4458297670621968 371 4713635560067488 372 4983236904373184 373 5267878906893236 374 5568380084097468 375 5885602408129488 376 6220453557755632 377 6573889283153616 378 6946915890061344 379 7340592849164522 380 7756035536988456 381 8194418114658560 382 8656976551297856 383 9145011799262592 384 9659893128550098 385 10203061628167488 386 10776033882735170 387 11380405832772390 388 12017856827622630 389 12690153880523140 390 13399156135542048 391 14146819556681136 392 14935201850058723 393 15766467630358116 394 16642893843376340 395 17566875457201984 396 18540931434883046 397 19567711002180012 398 20650000224780152 399 21790728909753888 400 22992977846863375 401 24259986406213362 402 25595160509223780 403 27002080990839168 404 28484512371884284 405 30046412061060788 406 31691940007137184 407 33425468823008232 408 35251594403995332 409 37175147063956394 410 39201203214043656 411 41335097609770356 412 43582436193403144 413 45949109560131152 414 48441307077433176 415 51065531688599560 416 53828615432986068 417 56737735716718356 418 59800432369302388 419 63024625523430626 420 66418634356609728 421 69991196735201572 422 73751489803547094 423 77709151562399568 424 81874303483122508 425 86257574206459242 426 90870124376492496 427 95723672662939360 428 100830523027587802 429 106203593292785520 430 111856445072755736 431 117803315131526448 432 124059148233700372 433 130639631557536466 434 137561230743226624 435 144841227652073696 436 152497759915952532 437 160549862360303280 438 169017510387162588 439 177921665408906296 440 187284322427758088 441 197128559859871239 442 207478591707516920 443 218359822187873450 444 229798902931231656 445 241823792866788776 446 254463820919822624 447 267749751649006056 448 281713853958692200 449 296389973027368386 450 311813605599180531 451 328021978792308900 452 345054132585191862 453 362951006148132656 454 381755528195622118 455 401512711542884736 456 422269752057643500 457 444076132206938490 458 466983729408091380 459 491046929401478568 460 516322744872792160 461 542870939562951916 462 570754158113632352 463 600038061907715152 464 630791471175852676 465 663086513651523840 466 696998780069815386 467 732607486818612722 468 769995646063659468 469 809250243683503888 470 850462425365580864 471 893727691229246136 472 939146099358070234 473 986822478640939716 474 1036866651338117664 475 1089393665807087786 476 1144524039842520528 477 1202384015103611852 478 1263105823123181840 479 1326827963415007968 480 1393695494217391784 481 1463860336434880688 482 1537481591365063442 483 1614725872821836160 484 1695767654293610613 485 1780789631803218056 486 1869983103164084610 487 1963548364357891304 488 2061695123790920100 489 2164642935217897764 490 2272621650156806836 491 2385871890654308282 492 2504645543297315700 493 2629206275405454392 494 2759830074380045160 495 2896805811225988824 496 3040435829307242656 497 3191036559442827840 498 3348939162496509892 499 3514490200663393874 500 3688052338708947992 501 3870005076468349008 502 4060745513970670654 503 4260689150611499640 504 4470270719856924056 505 4689945061025826064 506 4920188029764135984 507 5161497448891945898 508 5414394101376663168 509 5679422767260753244 510 5957153306448751728 511 6248181789339861968 512 6553131677377567547 513 6872655055673844840 514 7207433919957744386 515 7558181520194200480 516 7925643763316392188 517 8310600677619047904 518 8713867941468540768 519 9136298479095839064 520 9578784126355830288 521 10042257369458921274 522 10527693159805408212 523 11036110808185635866 524 11568575961747038626 525 12126202667269939920 526 12710155524443481912 527 13321651932988795968 528 13961964437635541916 529 14632423175126547097 530 15334418427600893008 531 16069403286885348214 532 16838896434414153456 533 17644485041695144056 534 18487827796442866044 535 19370658059713638440 536 20294787159600651954 537 21262107827275885956 538 22274597781407123420 539 23334323467229782506 540 24443443956811243920 541 25604215017317441788 542 26818993354374746864 543 28090241037911045928 544 29420530118166406214 545 30812547439882740912 546 32269099663009778880 547 33793118498609786466 548 35387666169002706222 549 37055941101562875684 550 38801283865967069014 551 40627183365097978104 552 42537283290223511760 553 44535388851509659264 554 46625473795379767332 555 48811687720701875232 556 51098363706277915706 557 53490026262620661196 558 55991399621532090400 559 58607416377550544056 560 61343226495910065440 561 64204206702249368808 562 67195970269930645546 563 70324377221476222994 564 73595544961299520416 565 77015859357607025224 566 80591986292076366942 567 84330883696667477352 568 88239814097711064616 569 92326357688237358858 570 96598425950353659216 571 101064275850363999786 572 105732524630244350232 573 110612165220037395840 574 115712582296725132720 575 121043569016171275320 576 126615344445793921653 577 132438571726745775042 578 138524376995540402131 579 144884369096263559044 580 151530660115762958416 581 158475886775513848976 582 165733232715206407116 583 173316451704509349896 584 181239891820928221630 585 189518520633191364048 586 198167951431177610548 587 207204470545043085530 588 216645065797904940594 589 226507456138214254656 590 236810122499794479448 591 247572339939430479816 592 258814211103884158684 593 270556701080281670322 594 282821673685959065992 595 295631929256086596160 596 309011243989712644108 597 322984410917271156368 598 337577282555101182560 599 352816815315129657816 600 368731115740563632874 601 385349488641246593642 602 402702487205251338768 603 420821965166303903838 604 439741131109781249656 605 459494605003296001692 606 480118477041269328952 607 501650368896421370720 608 524129497474773725826 609 547596741274555459008 610 572094709453357463024 611 597667813711986318912 612 624362343107723258250 613 652226541914122468068 614 681310690649082556470 615 711667190397690957648 616 743350650561300955952 617 776417980169451950682 618 810928482896581261584 619 846943955931029428282 620 884528792849608049792 621 923750090656975785696 622 964677761155285229064 623 1007384646816018854736 624 1051946641332622640184 625 1098442815039504169497 626 1146955545390186493706 627 1197570652694896754664 628 1250377541325654525860 629 1305469346605008075528 630 1362943087602944920992 631 1422899826075213266680 632 1485444831785333056912 633 1550687754461947707972 634 1618742802652909678604 635 1689728929747605586432 636 1763770027449508684488 637 1840995126991840341900 638 1921538608400529370216 639 2005540418120378707512 640 2093146295332528039164 641 2184508007303941177602 642 2279783594122749689044 643 2379137623186897234562 644 2482741453827656510016 645 2590773512464235030352 646 2703419578700898455756 647 2820873082793826337416 648 2943335414931279012847 649 3071016246787650618788 650 3204133865829619123692 651 3342915522870885544448 652 3487597793390979665154 653 3638426953153307822764 654 3795659368678037262312 655 3959561903146613883464 656 4130412338336707292478 657 4308499813209178752294 658 4494125279792341050752 659 4687601977033338392882 660 4889255923311931446064 661 5099426428338399689812 662 5318466625184686983822 663 5546744023226331824304 664 5784641082802218549986 665 6032555812429779660864 666 6290902389444990663948 667 6560111804969410742176 668 6840632534140658445384 669 7132931232578093408192 670 7437493460092192396024 671 7754824432684188158616 672 8085449803922008599792 673 8429916476819508097250 674 8788793447388454366130 675 9162672681076753559844 676 9552170023352067318399 677 9957926145737335229476 678 10380607528653800246124 679 10820907482478055262480 680 11279547208272428937144 681 11757276899702749316772 682 12254876887714286125632 683 12773158829595525693434 684 13312966944120424247118 685 13875179294523046763240 686 14460709121124085804528 687 15070506225496722865416 688 15705558408129785498186 689 16366892961619230904944 690 17055578221494713943744 691 17772725176866528145554 692 18519489143159615285332 693 19297071499285694480176 694 20106721491692032169630 695 20949738107816042440104 696 21827472021568855282136 697 22741327613568399132052 698 23692765068943507199532 699 24683302555635168257460 700 25714518486229497821832 701 26788053866469411020572 702 27905614733708440211472 703 29068974688690871511112 704 30279977524167494638762 705 31540539953985890138496 706 32852654446428548661922 707 34218392165711363667232 708 35639906025699297471516 709 37119433860045543094724 710 38659301713115442783072 711 40261927256216931761712 712 41929823333825627091726 713 43665601644665047333632 714 45471976562681001755040 715 47351769103134227063520 716 49307911039227066918322 717 51343449174878579069664 718 53461549779468242834136 719 55665503190581640938832 720 57958728591012322758980 721 60344778966502876242752 722 62827346250945284491711 723 65410266666006164797732 724 68097526262396871197036 725 70893266670271956119436 726 73801791066512406787818 727 76827570366932821794392 728 79975249651744574403168 729 83249654832910328774235 730 86655799572339496948616 731 90198892460199685100628 732 93884344462956220872408 733 97717776651100986250428 734 101705028216893378748560 735 105852164792810671568520 736 110165487081792895215032 737 114651539810769038598036 738 119317121019367295580294 739 124169291696142869955490 740 129215385775102965947184 741 134463020505770510721456 742 139920107210506544474848 743 145594862443306593652200 744 151495819564799247018432 745 157631840748706310323408 746 164012129435573903499396 747 170646243250153278884014 748 177544107399399777146836 749 184716028568668845244112 750 192172709334320079334064 751 199925263111594699111536 752 207985229657309426725872 753 216364591147611169331124 754 225075788851763147795920 755 234131740423684973453920 756 243545857833747468532064 757 253332065964128805356852 758 263504821891872691374270 759 274079134884652761325536 760 285070587135141208015336 761 296495355260804973684810 762 308370232596910545960192 763 320712652311509821452896 764 333540711372205709370816 765 346873195395558269421240 766 360729604411091602331264 767 375130179572999650211064 768 390095930853826763462866 769 405648665755617876739202 770 421811019075294753442112 771 438606483762320388452868 772 456059442908064977856454 773 474195202907685363160324 774 493040027836777068601458 775 512621175086555814123168 776 532966932302875355515894 777 554106655675992376128576 778 576070809629648953400724 779 598891007959760678422548 780 622600056474775700448864 781 647231997191609022441552 782 672822154142959315086288 783 699407180853784430587824 784 727025109546749125481139 785 755715402138566487339120 786 785519003091335512622308 787 816478394185233885540530 788 848637651281259743553820 789 882042503145131640044304 790 916740392405954978382272 791 952780538725848641000592 792 990214004259400200640854 793 1029093761484585221057104 794 1069474763489648769402972 795 1111414016803408501112480 796 1154970656859502104978920 797 1200206026188270870798844 798 1247183755433249124409056 799 1295969847292620184532064 800 1346632763489507046025647 801 1399243514878594010218038 802 1453875754800328274471538 803 1510605875797832163608164 804 1569513109815671463453996 805 1630679632003777940026112 806 1694190668254119130602624 807 1760134606602150547067160 808 1828603112629679747922140 809 1899691249010523321147930 810 1973497599345251836598148 811 2050124396436400003476602 812 2129677655160775135865312 813 2212267310100932286872864 814 2298007358103505360537432 815 2387016005937896255528904 816 2479415823234834929038596 817 2575333900890539121918388 818 2674902015128630095899818 819 2778256797418607047441056 820 2885539910456555499845208 821 2996898230420871372128884 822 3112484035723130246368860 823 3232455202481828983603640 824 3356975406954582476341960 825 3486214335172480432312644 826 3620347900028706872907152 827 3759558466082207550848810 828 3904035082346167076060040 829 4053973723340338318176668 830 4209577538695861609088056 831 4371057111611130690325224 832 4538630726467517378901716 833 4712524645924368565506306 834 4892973397823648758313364 835 5080220072245931193986208 836 5274516629071152685397340 837 5476124216409654373065344 838 5685313500281545863045030 839 5902365005935367238106440 840 6127569471210395909813440 841 6361228212360768044928965 842 6603653502773872083688884 843 6855168965030239864257876 844 7116109976767425357697298 845 7386824090826138233182036 846 7667671470173206154751792 847 7959025338112793756681528 848 8261272444314725534798092 849 8574813547206762866994804 850 8900063913296291712737514 851 9237453834006106930726752 852 9587429160628851906703344 853 9950451858025209926389780 854 10327000577712168145954464 855 10717571251009608469393272 856 11122677702936145909588842 857 11542852287568557960982506 858 11978646545603352770025264 859 12430631884884035580496778 860 12899400284683478333377992 861 13385565024557503519951776 862 13889761438613389133759568 863 14412647696065515763949664 864 14954905608979839350730900 865 15517241468139315433882032 866 16100386907993854693296722 867 16705099801690888032914342 868 17332165187216197064030976 869 17982396225709357616370464 870 18656635193053985961688224 871 19355754505880007865161752 872 20080657783153427902971444 873 20832280944568600429390590 874 21611593346998835990033264 875 22419598960303360224817472 876 23257337583832220081168180 877 24125886105015750434575372 878 25026359801471719578332552 879 25959913688111312549713800 880 26927743910774737399870344 881 27931089187978502514464658 882 28971232302409365786091143 883 30049501643854654286132178 884 31167272805315152397663144 885 32325970234105115235483856 886 33527068939804243499600638 887 34772096260988717585196024 888 36062633692732696648530024 889 37400318776938109285434368 890 38786847057619164547238472 891 40223974103338865362283410 892 41713517599067984485643616 893 43257359509812540620723808 894 44857448318433866443667800 895 46515801340165971540073608 896 48234507116418153867151720 897 50015727890536787991156288 898 51861702168289005528664386 899 53774747365922673168608128 900 55757262548751759423057369 901 57811731263313960002887080 902 59940724466248422544137708 903 62146903553145676527769248 904 64433023490729540272928326 905 66801936055841952680824656 906 69256593184816475205408240 907 71800050436944746353200026 908 74435470575862566380694466 909 77166127272808667011563356 910 79995408935839708352993920 911 82926822669219773966259216 912 85963998367341740554081068 913 89110692947681521866438260 914 92370794727434471241331322 915 95748327948636322225941984 916 99247457456729106548547196 917 102872493537695671437800720 918 106627896919054886947176696 919 110518283940183558113159448 920 114548431897610609971351392 921 118723284571114474594309764 922 123047957936645964400061596 923 127527746072296455412096608 924 132168127263735124256620320 925 136974770315749487458058900 926 141953541076740789942132272 927 147110509183250096975254296 928 152451955031822483769069316 929 157984376985755718831848418 930 163714498824526537144570112 931 169649277443942242679120706 932 175795910815328218034179086 933 182161846212333211215689328 934 188754788714214284779207894 935 195582709994752326373204176 936 202653857406247316413935660 937 209976763368350423021968666 938 217560255071807748780534096 939 225413464507518500022118420 940 233545838831648810399306432 941 241967151077891757931976524 942 250687511228324610283989768 943 259717377654686370931687792 944 269067568942282642553557114 945 278749276109121048036061824 946 288774075233289342151808324 947 299153940502010306583441554 948 309901257696242958198214496 949 321028838125148940706429176 950 332549933025206649679034622 951 344478248439234110437264632 952 356827960591075353638470480 953 369613731772214492954664330 954 382850726757107396301750012 955 396554629764563267238193920 956 410741661983068140719834160 957 425428599678519787815303088 958 440632792903439376589195296 959 456372184827340025592817104 960 472665331708566704367959208 961 489531423528576394709551137 962 506990305310302656447345072 963 525062499142945390815848806 964 543769226936245334040668726 965 563132433928044332884190984 966 583174812969697463011026048 967 603919829614692284890902984 968 625391748036644745496414125 969 647615657803681205346594120 970 670617501537082603987336360 971 694424103482960699515718234 972 719063199026658481276599094 973 744563465180518140159381968 974 770954552076641293234522712 975 798267115497278431696938936 976 826532850476528757406834404 977 855784526008108684811430066 978 886056020895058333025811876 979 917382360778401372716523716 980 949799756382955709091339708 981 983345643019711793762329524 982 1018058721385453019571495726 983 1053978999701589851168612184 984 1091147837235517303902689940 985 1129607989249185368447947920 986 1169403653420995288197077784 987 1210580517788602570027776768 988 1253185810261721629687173304 989 1297268349755588462976870768 990 1342878598997348158615098344 991 1390068719059294941347891424 992 1438892625674605310758806688 993 1489406047392971325703890324 994 1541666585635362831827562048 995 1595733776709026142739437856 996 1651669155845764118315167308 997 1709536323328540547049342052 998 1769401012773512095892750070 999 1831331161636715759409671376 1000 1895396984016830700952954072