0 1 1 0 2 0 3 0 4 0 5 1 6 0 7 3 8 2 9 5 10 5 11 13 12 7 13 23 14 21 15 33 16 35 17 65 18 55 19 104 20 97 21 151 22 166 23 252 24 235 25 377 26 399 27 549 28 591 29 846 30 858 31 1237 32 1311 33 1749 34 1934 35 2556 36 2705 37 3659 38 3991 39 5090 40 5608 41 7244 42 7841 43 10086 44 11075 45 13794 46 15420 47 19195 48 21003 49 26240 50 29089 51 35483 52 39606 53 48341 54 53458 55 65073 56 72405 57 86943 58 97346 59 116599 60 129352 61 155037 62 173045 63 204680 64 229093 65 270845 66 301768 67 356168 68 397667 69 465605 70 521164 71 609236 72 679036 73 792905 74 885832 75 1027046 76 1148800 77 1330718 78 1484240 79 1716485 80 1915920 81 2205390 82 2464588 83 2832213 84 3156789 85 3623460 86 4042429 87 4620990 88 5156321 89 5887815 90 6558008 91 7478097 92 8331307 93 9470763 94 10553983 95 11981308 96 13329773 97 15116625 98 16819819 99 19023323 100 21163787 101 23911833 102 26569642 103 29983570 104 33310417 105 37511253 106 41669036 107 46873052 108 52005816 109 58443395 110 64830480 111 72721477 112 80644359 113 90374471 114 100125181 115 112092778 116 124145920 117 138775711 118 153648845 119 171594279 120 189811325 121 211798448 122 234206392 123 260979988 124 288475145 125 321185271 126 354749532 127 394641602 128 435701768 129 484140093 130 534299828 131 593224103 132 654206313 133 725798226 134 800087661 135 886717605 136 977055521 137 1082063335 138 1191518933 139 1318608063 140 1451357933 141 1604705512 142 1765516142 143 1950689317 144 2144833011 145 2368199840 146 2602801805 147 2871471465 148 3154543848 149 3477935702 150 3818610767 151 4207389268 152 4617523533 153 5083843421 154 5577046917 155 6136503207 156 6728173736 157 7398721009 158 8108681867 159 8910668161 160 9761543513 161 10720907947 162 11738707037 163 12885091292 164 14102437695 165 15469930271 166 16924516067 167 18555597522 168 20290473232 169 22234192286 170 24303137944 171 26615657685 172 29080477029 173 31831360281 174 34763334010 175 38032609178 176 41519207496 177 45399258682 178 49541666349 179 54145147464 180 59059714399 181 64517020844 182 70345860220 183 76806942734 184 83713860388 185 91360875924 186 99535257109 187 108578349621 188 118248587563 189 128930550799 190 140361112689 191 152973696558 192 166469465681 193 181350249105 194 197277522070 195 214815703263 196 233597393288 197 254258890938 198 276383884961 199 300706448426 200 326757160558 201 355362305736 202 386012658142 203 419638398160 204 455665654037 205 495165504421 206 537492583399 207 583850909688 208 633543028523 209 687925075810 210 746212854892 211 809963310411 212 878298712189 213 952969943048 214 1033030413279 215 1120449720212 216 1214169353691 217 1316446853817 218 1426100905911 219 1545668251688 220 1673880451202 221 1813592164173 222 1963389218839 223 2126535165503 224 2301460651496 225 2491833587992 226 2695974624204 227 2918007260050 228 3156070000985 229 3414871256892 230 3692352720827 231 3993802794669 232 4317032069892 233 4667986767381 234 5044250975455 235 5452599439080 236 5890378723292 237 6365199130192 238 6874253658315 239 7426094034767 240 8017644507333 241 8658637830304 242 9345714173825 243 10089800468692 244 10887376037034 245 11750719871901 246 12676000501020 247 13677167462009 248 14750073362276 249 15910382632695 250 17153792428419 251 18497896803877 252 19938062254439 253 21494256662488 254 23161514167859 255 24962246193755 256 26891387245270 257 28974109784574 258 31205026454857 259 33612666021330 260 36191347056163 261 38973093881058 262 41952240723157 263 45164741562446 264 48604701037036 265 52312830348607 266 56283055018770 267 60561056696535 268 65141028996509 269 70074261628264 270 75354920537265 271 81041014007488 272 87126807379392 273 93677394310976 274 100687748775553 275 108230927289947 276 116302311550680 277 124984463720097 278 134273378192482 279 144261676444055 280 154946844104763 281 166432833655194 282 178718296714106 283 191920593501836 284 206039935604839 285 221207980022371 286 237427704541585 287 254846824046930 288 273470824938674 289 293466367097441 290 314842057041437 291 337784811456891 292 362308099030791 293 388621622196932 294 416743539668775 295 446910244268347 296 479145622241079 297 513714784105765 298 550649757012957 299 590247890520905 300 632549456571787 301 677889455626713 302 726317986910023 303 778210654703970 304 833630872642297 305 892999874861766 306 956394869237824 307 1024290073577188 308 1096779017279832 309 1174393356052250 310 1257247808652643 311 1345938462976580 312 1440602499455703 313 1541910618134445 314 1650026263099392 315 1765701176546027 316 1889132064332739 317 2021161648846960 318 2162022267237579 319 2312661517970415 320 2473353229185795 321 2645159365975575 322 2828405070704989 323 3024280507622715 324 3233166485297916 325 3456400591847478 326 3694427970141009 327 3948747243289408 328 4219881952410391 329 4509511336853730 330 4818244451942312 331 5147967440816275 332 5499387923251989 333 5874618737142756 334 6274485876830556 335 6701356127209039 336 7156185509269795 337 7641631120821199 338 8158798082947595 339 8710662028503006 340 9298505436412944 341 9925660851696551 342 10593606165642081 343 11306080644514424 344 12064785826847628 345 12873908280250634 346 13735412960103525 347 14653987127930850 348 15631887158280006 349 16674369895761718 350 17784024003741373 351 18966733390119123 352 20225475528914372 353 21566836260248343 354 22994223955249980 355 24515020866831244 356 26133125854373830 357 27856799513736834 358 29690510637434686 359 31643502237601239 360 33720876248616239 361 35932988587346052 362 38285659896455604 363 40790474400964904 364 43454083930448022 365 46289446419742855 366 49304137831306783 367 52512668913117107 368 55923663084539704 369 59553347224891421 370 63411549985923184 371 67516416056772819 372 71879115975789504 373 76519959269162234 374 81451634175644832 375 86696843984978836 376 92270016935939004 377 98196530900171914 378 104492751978505636 379 111187071763659424 380 118298045236582701 381 125857399466945298 382 133886189359727231 383 142419866120127204 384 151482271000270867 385 161113046413657906 386 171339175252322726 387 182204940167377603 388 193740901951860854 389 205996522924627448 390 219006351639036144 391 232825670799823529 392 247493519985120011 393 263071629764373920 394 279604139366351808 395 297159972076435970 396 315788952682067064 397 335568078178429324 398 356553566746486409 399 378831361175060990 400 402464922981029945 401 427550170912900394 402 454158640337954517 403 482397433144580630 404 512347154309961535 405 544127301345547595 406 577828730315400058 407 613584753381907492 408 651497653193478949 409 691716213416390785 410 734355535852513405 411 779581553758663637 412 827523831098286998 413 878367406790386392 414 932257960089707545 415 989401902630541513 416 1049962975437436004 417 1114171285349446719 418 1182210910818020107 419 1254338341449702660 420 1330760313799544733 421 1411762804861338701 422 1497577917293775528 423 1588524317326723175 424 1684862625445883326 425 1786947889983707477 426 1895072489933198644 427 2009632096492377266 428 2130954610862438756 429 2259480739965404550 430 2395578256738952250 431 2539737963415758155 432 2692372022338148980 433 2854027125175882723 434 3025165034550714186 435 3206394392953124783 436 3398232562451721226 437 3601357066873459182 438 3816347137826450678 439 4043957079595838142 440 4284835198471273685 441 4539820899454015316 442 4809639813007075763 443 5095225913624145885 444 5397390843666612844 445 5717173913815267669 446 6055482707612510864 447 6413473260407565273 448 6792160430433306847 449 7192829908261212045 450 7616615818956868125 451 8064948153774443008 452 8539093969418211131 453 9040643131783166591 454 9571011158778002859 455 10131965407441838426 456 10725086381639411207 457 11352338842462757594 458 12015487029554753139 459 12716714353411781094 460 13457990044142708571 461 14241740144649007893 462 15070161573359356087 463 15945950029006991815 464 16871555809498049087 465 17849973219987441105 466 18883934958383471056 467 19976766518637444063 468 21131514121129290062 469 22351871098588553151 470 23641232302272852210 471 25003698266211442685 472 26443052047554075494 473 27963845606040460748 474 29570292760866872111 475 31267446514105665864 476 33059999353907560047 477 34953558782733115241 478 36953349806105109830 479 39065594339896430772 480 41296107995995285370 481 43651794219765088534 482 46139124445818694540 483 48765756101663189995 484 51538889620340643063 485 54467017493457598647 486 57558148247263660642 487 60821700073971137734 488 64266578238992858972 489 67903224715623212379 490 71741540743167872106 491 75793101612177583715 492 80068912052395249670 493 84581802954613849091 494 89344002774472216974 495 94369730524518399110 496 99672572778955590707 497 105268284484494084561 498 111171956156299849363 499 117401043396402560061 500 123972303495105366772 501 130905071545628510267 502 138217953274256596722 503 145932362395147023938 504 154068950527620780832 505 162651431661821901399 506 171702723399087593719 507 181249080919943015483 508 191315933023327670521 509 201932344037016883438 510 213126520780321105278 511 224930634546470587387 512 237375967208121223384 513 250498121156465747885 514 264331783736383606929 515 278916348435511208816 516 294290268059792385551 517 310497126908187619306 518 327579543383692533824 519 345585727981072480499 520 364562909309030612700 521 384564407142190991697 522 405642545060064453302 523 427856287811379791592 524 451263592189808387990 525 475929651993852198770 526 501918654488559159167 527 529302669797260079212 528 558152767445995068251 529 588548611009620089846 530 620568875036139637325 531 654301598884504814707 532 689833863339420143982 533 727262949771042685288 534 766685220022426395981 535 808208156129593560142 536 851938370139861104978 537 897994591315807621138 538 946494755013542398073 539 997569995296583612658 540 1051350743252848638498 541 1107981817802557304376 542 1167607443168157663776 543 1230387521084056581923 544 1296481504227366536282 545 1366065922183620318884 546 1439317024750574834000 547 1516429676254136989153 548 1597598658021672329135 549 1683039034125881084209 550 1772966034291709200444 551 1867616981666234181488 552 1967229650183549503514 553 2072065895466055217392 554 2182388350694506948305 555 2298485888528227074235 556 2420648557962654632102 557 2549194990194034717037 558 2684445445755879842864 559 2826751338338824035296 560 2976466225826569004270 561 3133977610238474363265 562 3299675751594856379440 563 3473987884993292791719 564 3657344696789055657477 565 3850217172768698237905 566 4053080532781485032262 567 4266453905899390635420 568 4490861573965079654201 569 4726875649147836206326 570 4975074428932304995689 571 5236088339529739680057 572 5510555153347374215196 573 5799169440125288298358 574 6102634461876125550082 575 6421715350230450271928 576 6757187436901147878273 577 7109893480804759149084 578 7480688129667815951259 579 7870499495975650394079 580 8280269521845436131787 581 8711020175039688004741 582 9163789420254855703969 583 9639702433021305324758 584 10139902806487995331002 585 10665629151887898086799 586 11218141259791554120828 587 11798802424258299911289 588 12409000195679924486686 589 13050234916654380845862 590 13724034613928320420084 591 14432050201078378780736 592 15175964164443721101883 593 15957592850320020579023 594 16778788500850656323193 595 17641549224936024366891 596 18547913833835522221157 597 19500080056101032463913 598 20500291748596196785770 599 21550965873589515291972 600 22654571543645753998562 601 23813766495142054370116 602 25031267297365531613886 603 26309996012972003444182 604 27652941051783426431614 605 29063314659023949378681 606 30544403752897595066699 607 32099739141056397749811 608 33732935529316568229303 609 35447873315495329345599 610 37248527132519875382221 611 39139161013029476795410 612 41124144662825221029243 613 43208163098456853493379 614 45396019664377792015613 615 47692861188440695399821 616 50103966965370635638995 617 52634990409945014021494 618 55291733028027583477560 619 58080403917652128003482 620 61007377532920716244309 621 64079472316399472680414 622 67303691306120689037952 623 70687521110131112474676 624 74238654168909780193091 625 77965309723183572122915 626 81875936284738883035465 627 85979556174847100379521 628 90285447047245428387446 629 94803511490326281874750 630 99543936160360008810104 631 104517588467957327832944 632 109735651573464497055433 633 115210050092819950079488 634 120953059547078884350548 635 126977762929927523913842 636 133297632866099309061145 637 139927021509273676126358 638 146880713297247036474098 639 154174450555784334093014 640 161824455141445671009702 641 169847992020114299022854 642 178262857684621900539821 643 187087984726041035160536 644 196342894480758184423097 645 206048345505903314562026 646 216225748381224282980256 647 226897860883893486782646 648 238088162394605404225878 649 249821599456595946577893 650 262123916718262359194848 651 275022456446546628627952 652 288545443495751159886678 653 302722842213225510799387 654 317585592355526160925663 655 333166527887303921084821 656 349499560157183426003927 657 366620662961435299560666 658 384566999942249162144374 659 403377980146618413887892 660 423094325940578283774441 661 443759204554711769967819 662 465417232082068983767734 663 488115686365717807557165 664 511903443417143423553474 665 536832276843054924356323 666 562955722223567102409836 667 590330469781048077867849 668 619015151404137572106121 669 649071833111167586465663 670 680564720302810521017429 671 713561756407838476896060 672 748133241010588391381932 673 784353542851820676716397 674 822299624462337857381555 675 862052877539097472222340 676 903697548775581230115494 677 947322705453253462701447 678 993020556045535235482562 679 1040888555994115341303439 680 1091027615472571681330358 681 1143544355153549622969677 682 1198549194753109880015114 683 1256158768414668820290472 684 1316493886349596868236816 685 1379682121987436492398215 686 1445855637615303076275713 687 1515153955288140622756898 688 1587721638826948560923234 689 1663711260293620355669608 690 1743280929159621484984955 691 1826597469158033155858147 692 1913833783780184321087308 693 2005172258160249911157022 694 2100801951756460147770354 695 2200922239748312360147982 696 2305739821947362680980512 697 2415472621751688713558797 698 2530346598373521366678134 699 2650599921265064060828978 700 2776479574754345859665607 701 2908245825686558229956850 702 3046168607417555459965845 703 3190532302660828251153263 704 3341631891501290587897294 705 3499778071326199101608418 706 3665293155858275812262134 707 3838516553920195610129720 708 4019800403985439521932582 709 4209515438556617130822661 710 4408046336033667848209871 711 4615797997435401105734035 712 4833190600140781356890980 713 5060666313588976823404486 714 5298684036501672559250080 715 5547726584186395772355107 716 5808295087702789496816282 717 6080916685401265507671944 718 6366138565710428708280185 719 6664536195538375712813252 720 6976706984925951374098284 721 7303279092033595799862778 722 7644904684206082176191210 723 8002269359395759490719714 724 8376084981976731165315808 725 8767099760539983562903762 726 9176090632761286730653483 727 9603874047950085988939176 728 10051297870976322864788650 729 10519252918210730290421548 730 11008664354942324735853503 731 11520504033604159155022602 732 12055781354431497977924869 733 12615556464873548193898006 734 13200930548203294079877465 735 13813059943494037595942984 736 14453145832116718317021659 737 15122449338103844987221959 738 15822280576987520443097355 739 16554014808282698624242422 740 17319080805281576693098651 741 18118978132113612708137827 742 18955264799220072557241648 743 19829575738202581830086380 744 20743609701360057121094776 745 21699149021649754600768513 746 22698045707852000979313607 747 23742242578086538373916924 748 24833758509386297726115386 749 25974711034319177346568889 750 27167300696355826131672763 751 28413835215941466168785566 752 29716712895177170296194271 753 31078448461253214028564203 754 32501655472413790088881453 755 33989073948311265755816824 756 35543551720702767482311320 757 37168073980194936140548421 758 38865743505975098474129758 759 40639812260653641624542567 760 42493660443329542821199252 761 44430830266513379396025839 762 46455003766936693502085340 763 48570038922235143230578010 764 50779946143405749591019704 765 53088926891947353936371089 766 55501348789602032467947025 767 58021786899843106066099104 768 60654997379195626659158840 769 63405961615069129183910779 770 66279858330799014596858933 771 69282110775955808584416511 772 72418357211157358951384803 773 75694501351258270334041717 774 79116681142891927076401428 775 82691322694405384979197265 776 86425107245204060097455633 777 90325028821754623769187916 778 94398359314169602429098029 779 98652710103393001118243788 780 103095995145538191841864598 781 107736496855084799732855693 782 112582827081520187824494257 783 117643997540663804611805524 784 122929378587606719971067538 785 128448774495881098575004457 786 134212379913578048687495400 787 140230860337384467248870294 788 146515306120639374822207601 789 153077318498738915061725820 790 159928961040841090856577015 791 167082851593220589219327019 792 174552111046967366883013384 793 182350461622058910311660292 794 190492172802723422762726815 795 198992166397439288038593632 796 207865959520974314273697366 797 217129776878585334266309498 798 226800490651717957021151916 799 236895740521644787585490438 800 247433870292538800964180551 801 258434056185800871685137257 802 269916240066608854523748022 803 281901266557245117819383225 804 294410812708533112817517222 805 307467534560088499861785760 806 321094993071751221165692476 807 335317810779449889626879584 808 350161593840439206534779584 809 365653099455365909049283997 810 381820153853331320305246582 811 398691831245702733881350755 812 416298367547744797520730412 813 434671351656235240195294479 814 453843634750433491927374060 815 473849534713843004253643266 816 494724740826519315583739034 817 516506532264338305600717468 818 539233677961964188623653998 819 562946670157050942320411664 820 587687619258370580499672252 821 613500503438417632529641266 822 640431058307065750520647487 823 668527043690959806783110338 824 697838127877241605199058326 825 728416172761354412105310762 826 760315112491263468593210204 827 793591258211466720488238140 828 828303170900999963832990853 829 864511987102216773146882550 830 902281285706566259626545461 831 941677436111857888226714136 832 982769458789078717559794310 833 1025629397370362149222410141 834 1070332172789746057987988388 835 1116955980996181094742888679 836 1165582140418982599062318717 837 1216295517069894353938067041 838 1269184365179039630929170436 839 1324340781524502080053409669 840 1381860539041803166033284751 841 1441843572448689722421482134 842 1504393804586139192295003701 843 1569619665494406274902398636 844 1637633911358345761443339379 845 1708554179284685717074152590 846 1782502798679418136920445018 847 1859607384250515603276147794 848 1940000639598516020246700134 849 2023820991080105342739181567 850 2111212383531227780472606239 851 2202324957745826832836064332 852 2297314838205149628349674697 853 2396344857253618597719203981 854 2499584334660359658957889479 855 2607209851714546268271013654 856 2719405022612668924174776987 857 2836361321845118332242909263 858 2958277847357329818693837274 859 3085362204991898864633408223 860 3217830263325507381088583288 861 3355907099106946102283996264 862 3499826743874221746998090864 863 3649833194517167442817525137 864 3806180151737055280753050183 865 3969132100332172235129663896 866 4138964039519183671573469814 867 4315962637761479926635944277 868 4500425955217759651345208346 869 4692664678168941483452967733 870 4893001833822990816874257684 871 5101774109959573606255513615 872 5319331562284615346278996789 873 5546039025188875546213313826 874 5782275812144550500630660879 875 6028437223770282182936332699 876 6284934241736648641059064240 877 6552195141005320261356890072 878 6830665177686077935481876972 879 7120808312665052327726569828 880 7423106894220417266795659796 881 7738063500625050086756066879 882 8066200618318412495157410641 883 8408062611879951931880597659 884 8764215398549452128627211971 885 9135248554400862374446200773 886 9521774986447311561115906088 887 9924433184308801707242169103 888 10343886891153428149791366979 889 10780827511125837385525287717 890 11235973780397302640476155081 891 11710074341163584469722889291 892 12203907414619566070628271688 893 12718283552913518650597875554 894 13254045315911489130775405173 895 13812070213665850480793344970 896 14393270388895002932193437702 897 14998595763198910685914514553 898 15629033727843072319786296408 899 16285612507676008992993315378 900 16969400862905465659951496543 901 17681511686080476303114608226 902 18423101717660806125202779907 903 19195375392267810070739940257 904 19999584571661689958312190239 905 20837032657364398028664930566 906 21709074344824098092747794644 907 22617120021208931747003904552 908 23562635544725234319968815183 909 24547146947427474579517799299 910 25572240244653285639561249794 911 26639566463815107146412592977 912 27750841489171167170461261367 913 28907851439605958572257044440 914 30112452554240938477702060778 915 31366576943513445853943562936 916 32672232522355488577797801780 917 34031509160272776816068329381 918 35446578669195246756076866423 919 36919701380720493092566709178 920 38453226196156871958715848821 921 40049597620712656767370884108 922 41711355884755939476213307835 923 43441144466462008965636386644 924 45241710293850217080884871362 925 47115911790371749676359139765 926 49066719167872810433349266402 927 51097223031614013043326333426 928 53210634776159810003481164550 929 55410295788468763332106233763 930 57699677959452574105888011284 931 60082393527363385130599181211 932 62562195718583784514301013175 933 65142989276028045914499830414 934 67828831245000399909864773854 935 70623942233993855554521881110 936 73532707362471676469634281510 937 76559688305779205274994363322 938 79709624422815467254093129118 939 82987445639863101421264932665 940 86398273778922195851805871324 941 89947436338567741097069767396 942 93640468045086682912892117190 943 97483125593711171130880502998 944 101481389446196773551550727263 945 105641479599605391974729769875 946 109969857657417245427772013138 947 114473243697133394504720188982 948 119158618643840572862585779941 949 124033242314238685810341945657 950 129104656123565502082872077627 951 134380702388393201048974272351 952 139869527402082080168758702437 953 145579602083759230339866895643 954 151519725459879184284897423525 955 157699046754469189883319819285 956 164127069316997998879408633091 957 170813674254832838427048819686 958 177769124852871704782763172739 959 185004091855432081015973962116 960 192529658426261451478065868101 961 200357347196366609704901207545 962 208499125816446129391986492848 963 216967435894419128060582785439 964 225775199198809694505666725250 965 234935848617490477610163719675 966 244463335074658414562206661968 967 254372160653568768128025261902 968 264677386294203527531867220825 969 275394667231728284361130018244 970 286540261549955925488073808654 971 298131068096848404496138591747 972 310184635974202237570751511012 973 322719205105167186797503377076 974 335753716746345963820542612897 975 349307856893368819204521201672 976 363402067911480615446320121484 977 378057594977051587450208213836 978 393296498929579061725862771558 979 409141705963578437851291429837 980 425617021812352245453036437655 981 442747184918363665171418543371 982 460557882071318772822626991384 983 479075805299747646032922463035 984 498328669094743091073763803362 985 518345271285574084136112206721 986 539155511989935807842330316164 987 560790458753277810651155583792 988 583282367381478729741096909793 989 606664751641609378817725412706 990 630972406144182191711812771255 991 656241480927481581743688590449 992 682509506568689368306848553944 993 709815473994699356928884418751 994 738199862020004713288124141119 995 767704722749164374090955092742 996 798373711753655541528713642711 997 830252179460809883789314200707 998 863387204197292020225949209261 999 897827689984950087238459317392 1000 933624402701530276086414004161