0 1 1 0 2 0 3 0 4 0 5 0 6 1 7 1 8 2 9 3 10 5 11 7 12 11 13 14 14 20 15 26 16 35 17 44 18 59 19 73 20 94 21 117 22 148 23 181 24 228 25 277 26 344 27 418 28 514 29 621 30 762 31 917 32 1116 33 1342 34 1624 35 1945 36 2348 37 2803 38 3366 39 4012 40 4798 41 5700 42 6798 43 8052 44 9565 45 11305 46 13383 47 15771 48 18618 49 21880 50 25745 51 30187 52 35414 53 41414 54 48461 55 56531 56 65967 57 76783 58 89370 59 103779 60 120515 61 139636 62 161772 63 187060 64 216235 65 249521 66 287854 67 331515 68 381668 69 438759 70 504168 71 578532 72 663590 73 760151 74 870373 75 995400 76 1137820 77 1299176 78 1482706 79 1690366 80 1926163 81 2192719 82 2494877 83 2836065 84 3222307 85 3657922 86 4150345 87 4705194 88 5331495 89 6036444 90 6831213 91 7724813 92 8730992 93 9861240 94 11132284 95 12558636 96 14160905 97 15957144 98 17972642 99 20230106 100 22760310 101 25591624 102 28761811 103 32305956 104 36270250 105 40698363 106 45646459 107 51168636 108 57333542 109 64207713 110 71874851 111 80417094 112 89936043 113 100532733 114 112330894 115 125454167 116 140052920 117 156278757 118 174313803 119 194343436 120 216588658 121 241275264 122 268670972 123 299051069 124 332738998 125 370069628 126 411434114 127 457238587 128 507955372 129 564077162 130 626173077 131 694839706 132 770763050 133 854663775 134 947367670 135 1049745167 136 1162788546 137 1287547439 138 1425214158 139 1577051956 140 1744491763 141 1929053315 142 2132451306 143 2356511468 144 2603287928 145 2874970410 146 3174016942 147 3503052339 148 3865014029 149 4263044423 150 4700652249 151 5181594245 152 5710057215 153 6290529371 154 6928000733 155 7627827338 156 8395953140 157 9238761808 158 10163326760 159 11177251088 160 12288943268 161 13507449327 162 14842758500 163 16305621556 164 17907894847 165 19662345798 166 21583033053 167 23685104381 168 25985218694 169 28501329611 170 31253160251 171 34261974142 172 37551100942 173 41145701635 174 45073353135 175 49363800435 176 54049614213 177 59165932877 178 64751192402 179 70846867486 180 77498284585 181 84754354766 182 92668488517 183 101298325135 184 110706750422 185 120961635247 186 132136971504 187 144312612934 188 157575553964 189 172019680850 190 187747197825 191 204868406023 192 223503298584 193 243781362316 194 265843374876 195 289841242119 196 315940007135 197 344317748036 198 375167829663 199 408698860512 200 445137232070 201 484727155668 202 527733507885 203 574441982654 204 625162286756 205 680228413038 206 740002247840 207 804873998027 208 875266242198 209 951634562755 210 1034472104312 211 1124310428689 212 1221724666306 213 1327334645352 214 1441810688804 215 1565875092332 216 1700308658527 217 1845952561495 218 2003715738581 219 2174577220842 220 2359594466389 221 2559906266236 222 2776742152168 223 3011425947619 224 3265386419871 225 3540161597720 226 3837410799774 227 4158919879874 228 4506614824596 229 4882568045983 230 5289013789736 231 5728355660603 232 6203184044163 233 6716285102354 234 7270660490089 235 7869538016812 236 8516394002896 237 9214965887981 238 9969277536079 239 10783654140669 240 11662750888123 241 12611570471843 242 13635495608925 243 14740309585413 244 15932233091724 245 17217948315030 246 18604640690312 247 20100027026678 248 21712402885829 249 23450675373842 250 25324416843318 251 27343903109756 252 29520174346376 253 31865079472645 254 34391345267540 255 37112627869527 256 40043591142411 257 43199966402082 258 46598641299264 259 50257728906048 260 54196668594774 261 58436305875301 262 62999006797661 263 67908750174164 264 73191257342439 265 78874098473185 266 84986839827616 267 91561166200375 268 98631047916283 269 106232881797346 270 114405680562863 271 123191234851505 272 132634328101815 273 142782922637216 274 153688403311534 275 165405791138848 276 177994019560736 277 191516179361693 278 206039831991560 279 221637290161932 280 238385973009652 281 256368727435805 282 275674230682752 283 296397357909502 284 318639638561842 285 342509676583654 286 368123667527700 287 395605878738534 288 425089235237676 289 456715867904170 290 490637777300798 291 527017459134602 292 566028656073847 293 607857071090320 294 652701218823675 295 700773238473217 296 752299857857609 297 807523319274252 298 866702470743969 299 930113820114583 300 998052770075865 301 1070834817396321 302 1148796950531730 303 1232299013325794 304 1321725286037134 305 1417486035454950 306 1520019303091173 307 1629792666058580 308 1747305259321292 309 1873089775096499 310 2007714749004311 311 2151786829444394 312 2305953361563816 313 2470904961579792 314 2647378436907818 315 2836159705174769 316 3038087093143973 317 3254054645358362 318 3485015850195268 319 3731987388194486 320 3996053339788525 321 4278369430048854 322 4580167778842153 323 4902761706030804 324 5247551092762022 325 5616027818535776 326 6009781811052441 327 6430507195899013 328 6880009121281420 329 7360210711334878 330 7873160763178854 331 8421041605420478 332 9006177777188030 333 9631044906447883 334 10298279493365992 335 11010688937432846 336 11771262563009132 337 12583182939295923 338 13449838303019309 339 14374835333503544 340 15362013145458168 341 16415457701530408 342 17539517569779888 343 18738820177397554 344 20018289551342042 345 21383164642323705 346 22839019292514598 347 24391782887000170 348 26047762822585048 349 27813667773980034 350 29696632971048138 351 31704246402380574 352 33844577244114213 353 36126205362742983 354 38558253280516096 355 41150419381575685 356 43913013845341261 357 46856996009272706 358 49994014751815390 359 53336450519635202 360 56897460699855689 361 60691026878767835 362 64732005807576011 363 69036182527898416 364 73620327605338252 365 78502256832870915 366 83700895487196411 367 89236345403674996 368 95129957099876052 369 101404405110407249 370 108083768919733343 371 115193617550311746 372 122761100358381197 373 130815041983722848 374 139386044185995671 375 148506592395440038 376 158211169903005616 377 168536377396716446 378 179521060973099026 379 191206446203394293 380 203636281605004679 381 216856988962667087 382 230917824086623867 383 245871045314695553 384 261772093596689361 385 278679781324054850 386 296656494016236335 387 315768401874029786 388 336085685603418040 389 357682773365599425 390 380638593566909071 391 405036840183304120 392 430966255670199717 393 458520927982468228 394 487800607116320158 395 518911037526803274 396 551964312216727914 397 587079244673588120 398 624381764867523493 399 664005335301135525 400 706091393771456584 401 750789818649292178 402 798259423813008530 403 848668478851274555 404 902195262189695430 405 959028642557444427 406 1019368697004597168 407 1083427360690290491 408 1151429117245908198 409 1223611724734204441 410 1300226986653218927 411 1381541562800883800 412 1467837830141860274 413 1559414788293430500 414 1656589020512995857 415 1759695704604921547 416 1869089685434269812 417 1985146603263625934 418 2108264090466611926 419 2238863030643987322 420 2377388893624052121 421 2524313140188053810 422 2680134711010794321 423 2845381593474917116 424 3020612481935445824 425 3206418524929856206 426 3403425176076516229 427 3612294142006475092 428 3833725445339093877 429 4068459595907543905 430 4317279889611994307 431 4581014827997830923 432 4860540679407135880 433 5156784174716515981 434 5470725360108377682 435 5803400599828299664 436 6155905753102409129 437 6529399518153270903 438 6925106969348284441 439 7344323280446084365 440 7788417661998456145 441 8258837505942229023 442 8757112767626854547 443 9284860578449949555 444 9843790121707418196 445 10435707765033189772 446 11062522484604780793 447 11726251574760428388 448 12429026680986152820 449 13173100150289529679 450 13960851739924893631 451 14794795678956244543 452 15677588126896389846 453 16612035024482694367 454 17601100384376781222 455 18647915017566534582 456 19755785747098170313 457 20928205105779881318 458 22168861573669093620 459 23481650353003765285 460 24870684740930624895 461 26340308098913489033 462 27895106484095258594 463 29539921942929182233 464 31279866537717087452 465 33120337108029179688 466 35067030843470483892 467 37125961671713216541 468 39303477544583011288 469 41606278628361348117 470 44041436487988203040 471 46616414273894117827 472 49339088008644730691 473 52217768985090918886 474 55261227381353665454 475 58478717107720055644 476 61880001999668443573 477 65475383375938962059 478 69275729085542155939 479 73292504067009701754 480 77537802554300591266 481 82024381957638016248 482 86765698565175474718 483 91775945099375324801 484 97070090286508908231 485 102663920479521128025 486 108574083506285818763 487 114818134790659820642 488 121414585933233860308 489 128382955807233457401 490 135743824372679232728 491 143518889273330616755 492 151731025437182309811 493 160404347755212363215 494 169564277078445216970 495 179237609619411568281 496 189452590019113556640 497 200238988178352613284 498 211628180137470986945 499 223653233117644587516 500 236348995032851401280 501 249752188601581309649 502 263901510394775472077 503 278837734966872222036 504 294603824436297342591 505 311245043682127524539 506 328809081555895439484 507 347346178297352921820 508 366909259588788920058 509 387554077461343089438 510 409339358526797085391 511 432326959775664172854 512 456582032457576467629 513 482173194315189816171 514 509172710734046686490 515 537656685113422421727 516 567705259071304335779 517 599402822826040207723 518 632838236423260193200 519 668105062192181698681 520 705301809160492394782 521 744532189858053099363 522 785905390304798914481 523 829536353664179530312 524 875546078429902516280 525 924061931683863770421 526 975217978372138378387 527 1029155327199545210801 528 1086022494176093223908 529 1145975784485088592107 530 1209179693800752467927 531 1275807329801667700216 532 1346040855111246691475 533 1420071952496180979362 534 1498102313666999803445 535 1580344152605182998182 536 1667020744884487323675 537 1758366994014105695702 538 1854630026406365517895 539 1956069816110522871044 540 2062959841062962865362 541 2175587772121051412129 542 2294256196792401501523 543 2419283379065361579436 544 2551004057429003757239 545 2689770282641246853127 546 2835952297526336112227 547 2989939460528721678985 548 3152141215515595388916 549 3322988109740598711298 550 3502932862691691007519 551 3692451487940029006769 552 3892044470965060769520 553 4102238005297633231369 554 4323585290232161472829 555 4556667892697173760190 556 4802097176836857100719 557 5060515804165338342555 558 5332599308175979976833 559 5619057746567055739554 560 5920637435326587904308 561 6238122768167124381783 562 6572338125947344462907 563 6924149879933501729592 564 7294468493968370396521 565 7684250729798786242775 566 8094501961100474505289 567 8526278600888569285790 568 8980690648367400010359 569 9458904360388429838180 570 9962145054132663738351 571 10491700046714047336320 572 11048921738935398647664 573 11635230849472612026052 574 12252119807391099243211 575 12901156309906112185286 576 13583987054025749927727 577 14302341649686117730724 578 15058036723820667818760 579 15852980223738718464390 580 16689175930132951963089 581 17568728188930741548209 582 18493846873268213580909 583 19466852585722918468441 584 20490182113132177672492 585 21566394145142729709149 586 22698175269963977594057 587 23888346259577513527863 588 25139868659126363626871 589 26455851693949925608003 590 27839559510355062852423 591 29294418764918717734628 592 30824026579905841924458 593 32432158881054599532896 594 34122779136943758852070 595 35900047517789681330411 596 37768330494669610541910 597 39732210898765799787962 598 41796498463573193603226 599 43966240871578391008165 600 46246735330477724803377 601 48643540702536605924525 602 51162490214478830899976 603 53809704773800311805303 604 56591606921430127408183 605 59514935449142159567228 606 62586760714407035876925 607 65814500683832660023028 608 69205937740903969824847 609 72769236292173052547293 610 76512961210908073910520 611 80446097155636880146049 612 84578068806193408558197 613 88918762058294965898663 614 93478546223187754918848 615 98268297277316398000892 616 103299422212843165790206 617 108583884538266906380840 618 114134230984647077512127 619 119963619471376840929821 620 126085848392117400391525 621 132515387279967494192872 622 139267408918052254082420 623 146357822960211380351495 624 153803311134049833311356 625 161621364097156031875019 626 169830320025382726551763 627 178449405010686476744974 628 187498775354655143017996 629 196999561842527875969710 630 206973916091727355752763 631 217445059067690397258222 632 228437331869622375152445 633 239976248887676861955534 634 252088553443570595353815 635 264802276025650729256106 636 278146795240657501070682 637 292152901603586723161291 638 306852864299052846809696 639 322280501046894476628877 640 338471251217587278342858 641 355462252342579441047484 642 373292420178374786275144 643 392002532482980118149265 644 411635316677996043910315 645 432235541569698109582895 646 453850113318141156746826 647 476528175843703180823760 648 500321215877269816879340 649 525283172861003284275864 650 551470553924605629868177 651 578942554163135343314927 652 607761182461672158936262 653 637991393113733904573345 654 669701223500949285532687 655 702961938103617809970030 656 737848179133855609801490 657 774438124085734881101372 658 812813650520470815866692 659 853060508408071600614939 660 895268500372210591261752 661 939531670189172082744952 662 985948499918892556239153 663 1034622116051026673779705 664 1085660505078104174355692 665 1139176738913660522640743 666 1195289210604476853444006 667 1254121880792893861179393 668 1315804535418695540334797 669 1380473055158012075483081 670 1448269697132676360649367 671 1519343389432670560046838 672 1593850039032926277650612 673 1671952853696328163370706 674 1753822678496244611444137 675 1839638347604027173013395 676 1929587052031461472418342 677 2023864724031965169140573 678 2122676438912173920222729 679 2226236835021241873238683 680 2334770552736590555936128 681 2448512693282591671680489 682 2567709298273916476744157 683 2692617850895315299666386 684 2823507799688976415196506 685 2960661105943156119653561 686 3104372815739620605012945 687 3254951657742746977507920 688 3412720667881792850423145 689 3578017842106192462809709 690 3751196818467589396031072 691 3932627589814008845603114 692 4122697248461023750266706 693 4321810764240134727515053 694 4530391797410075963838119 695 4748883547956158122065777 696 4977749642894767734699727 697 5217475063243967305661282 698 5468567112420181008926616 699 5731556427869627458445446 700 6006998037849791066732432 701 6295472465330218665988240 702 6597586881096747516085095 703 6913976308203092447852545 704 7245304880037379818748062 705 7592267154337415081499432 706 7955589485621674204538780 707 8336031458576188531181730 708 8734387385080997192059401 709 9151487867640656206674257 710 9588201432137920663329361 711 10045436232918878021442564 712 10524141833384447918483160 713 11025311065361448670615597 714 11549981970706034702538312 715 12099239828700561034986427 716 12674219272998538779052037 717 13276106501991479754873204 718 13906141586680160106175661 719 14565620880263847520701974 720 15255899533886100377755989 721 15978394123119726804475206 722 16734585390016196379521199 723 17526021105702917410194787 724 18354319058773552609184611 725 19221170174890087610870904 726 20128341773297707262990428 727 21077680966143888252495756 728 22071118206797690183137191 729 23110670993573900057912875 730 24198447735595276848642154 731 25336651787754775419598664 732 26527585662094165080606453 733 27773655423165830508855822 734 29077375275327108832647452 735 30441372350190557901040863 736 31868391702866400091160555 737 33361301525933193626526966 738 34923098590518347595266913 739 36556913924197945913221095 740 38266018735906256902423327 741 40053830598403660112117568 742 41923919899370824282388605 743 43880016572588509078435848 744 45926017121222725478448219 745 48065991945662615275009246 746 50304192988963353832818634 747 52645061713413236569217682 748 55093237422397222692881917 749 57653565942238710423935599 750 60331108679406473152589380 751 63131152069029530183814261 752 66059217431424113048690658 753 69121071253943080906565974 754 72322735916280283870168896 755 75670500878023259498397825 756 79170934348135436333681896 757 82830895456769305730151375 758 86657546950770739122165390 759 90658368435019410856010357 760 94841170182785637051494745 761 99214107539138744158586789 762 103785695942560226174780250 763 108564826590845754913301655 764 113560782778587709328323807 765 118783256934543170243153182 766 124242368388496578991295502 767 129948681898329028740896188 768 135913226969414825527822721 769 142147517999665809178364560 770 148663575285065403327161147 771 155473946921839513273067750 772 162591731643054745435195637 773 170030602628853765101295810 774 177804832331312624841904078 775 185929318356448058918648590 776 194419610447819990059679055 777 203291938617851888376311995 778 212563242475062526591879050 779 222251201797225570912275957 780 232374268402710327939288570 781 242951699374237556430170734 782 254003591691700425487834269 783 265550918332852162859840281 784 277615565903271776448639577 785 290220373859355831872152883 786 303389175390903288363148480 787 317146840032397556045502787 788 331519318075134894851893660 789 346533686855102667036828836 790 362218198994799939341005529 791 378602332680182586128823592 792 395716844057467575487888046 793 413593821837775531309096347 794 432266744201427821999199063 795 451770538097234655163593048 796 472141641036255193899171933 797 493418065483329531213717643 798 515639465954158822221673237 799 538847208929851897144831103 800 563084445705691572843150411 801 588396188295365691551562013 802 614829388517129843268338462 803 642433020393239062741668992 804 671258165999625608718640612 805 701358104908079834177817203 806 732788407369282169443042789 807 765607031390757232777023774 808 799874423870399229161076463 809 835653625952420106818943348 810 873010382779675983629587710 811 912013257823048101946992320 812 952733751976226343379655549 813 995246427611524757356614311 814 1039629037800643188945326374 815 1085962660912176813371545498 816 1134331840806621546005134520 817 1184824732858166576667004283 818 1237533256042225482549640028 819 1292553251336909381675418513 820 1349984646697076478026956076 821 1409931628869610496910232722 822 1472502822329843158813193325 823 1537811475629882096106488711 824 1605975655461765912197660492 825 1677118448750109319664184091 826 1751368173102030282449964371 827 1828858595954859490803497524 828 1909729162776306780469996823 829 1994125234685512571927270070 830 2082198335878714595866012410 831 2174106411258142732509656267 832 2270014094679273960713527056 833 2370092988247681757971857393 834 2474521953114546454781620309 835 2583487412237313007836496046 836 2697183665591231342453381052 837 2815813218336357512241549967 838 2939587122465370734197476894 839 3068725332477941429694054517 840 3203457075649810618550373029 841 3344021237486780836291626366 842 3490666762978022034716214715 843 3643653074286927892355958566 844 3803250505543879073616302602 845 3969740755431036873659170384 846 4143417358277480213970415816 847 4324586174410854743880474897 848 4513565900542123054835683843 849 4710688600990115676701001733 850 4916300260585408395251715758 851 5130761360125595928616960427 852 5354447475289451921123247006 853 5587749899952636466336134102 854 5831076294885829389731065045 855 6084851362854173460430764718 856 6349517551178144569032541172 857 6625535782857030670317846970 858 6913386217400685646304819095 859 7213569042559589385048455371 860 7526605298191235078870579510 861 7853037733548790555619289499 862 8193431699329748959998942470 863 8548376075874051088705070456 864 8918484238957003482229136193 865 9304395064678226773243752907 866 9706773975008101094399310300 867 10126314025613554757370815075 868 10563737037650006830422158264 869 11019794775271473463421076721 870 11495270170680912182944187279 871 11990978598613275297825275769 872 12507769202219304013594772097 873 13046526272394096476094058731 874 13608170682675966021243671675 875 14193661381923150633815758243 876 14803996947063799458895689969 877 15440217198303222176033764776 878 16103404879267128056928245850 879 16794687404655165145710686215 880 17515238678081219389676819303 881 18266280982880088311522946078 882 19049086948770274447429647277 883 19864981597373959174139195774 884 20715344469713946080747782103 885 21601611838927473716941026596 886 22525279011564787682502694483 887 23487902720969951242165969290 888 24491103616379339652738803280 889 25536568851513066665607155826 890 26626054776583302249323752408 891 27761389737794249585952508907 892 28944476988568831749932419646 893 30177297716899805355448439834 894 31461914193395762636228049630 895 32800473044767925260739443964 896 34195208657689796879086567193 897 35648446718150945106117191119 898 37162607891626797210056201676 899 38740211649590361389756797149 900 40383880248107957395861454059 901 42096342864481034516710076679 902 43880439898129077565872006676 903 45739127442145791900454759477 904 47675481932211714520794946736 905 49692704979802107596783926542 906 51794128396899359790090489684 907 53983219419694771933025671344 908 56263586139055869501923751623 909 58638983145832508080422747067 910 61113317399388796554466087199 911 63690654328068105570843024432 912 66375224170636396097062041890 913 69171428568094235576370798873 914 72083847415611890642865675342 915 75117245984713812314126805913 916 78276582326230889484738585406 917 81567014964939615855422273504 918 84993910897229547187266244560 919 88562853903572239743445794608 920 92279653188019558109252370974 921 96150352357424467177107336867 922 100181238753567051835284188136 923 104378853151869693130707656001 924 108749999840912540539415764426 925 113301757097500301032724574512 926 118041488072599007911887613111 927 122976852104042951739723271960 928 128115816472523091945134410074 929 133466668617994588400817438142 930 139038028834299013966920452208 931 144838863460471330965379141940 932 150878498587909959121605705763 933 157166634303314639863139896046 934 163713359488059170753531818023 935 170529167195448243836646487134 936 177624970628128199715502669016 937 185012119738763672264551462356 938 192702418477975275315771456194 939 200708142714440183955663808432 940 209042058853007953815818082795 941 217717443177660034391337259636 942 226748101947164304012769497947 943 236148392272326713969049887502 944 245933243804842824757237623407 945 256118181268883049706250136287 946 266719347867729787637127062253 947 277753529599001974083166967849 948 289238180513276898551311268231 949 301191448952229290486611417240 950 313632204803778692143518472589 951 326580067813146072123790162026 952 340055436990195591873205781538 953 354079521154954643101044343529 954 368674370664791956809979744417 955 383862910368366104482754621523 956 399668973833163475150878233140 957 416117338895201284931902682673 958 433233764581306992406955442272 959 451045029456275196180568398198 960 469578971449177596283061052210 961 488864529215134495947946941707 962 508931785090979859198321283985 963 529812009705438722717218873248 964 551537708306719439660244723992 965 574142668872775388624360250513 966 597662012071946524081043545167 967 622132243144221002220587497335 968 647591305775997723216352696435 969 674078638043951426732923644728 970 701635230506441188455913720983 971 730303686523829107985898231337 972 760128284892128541120856085855 973 791155044877547570260313824314 974 823431793742775150005350446783 975 857008236859240473535955203724 976 891936030503104017438770986247 977 928268857436376167988089620231 978 966062505378351643685701352314 979 1005374948476458565950782839730 980 1046266431889697305167024094758 981 1088799559602048291761436137802 982 1133039385587609213473022273660 983 1179053508453741219835925924740 984 1226912169693212466982286461190 985 1276688355681184969952941699852 986 1328457903557951089146658949309 987 1382299611143547041509615157893 988 1438295351035808760988609980182 989 1496530189049046743645763273627 990 1557092507156359835181848093858 991 1620074131104638245517970219384 992 1685570462877584622437719862369 993 1753680618188562220585299715531 994 1824507569191824978660050052791 995 1898158292607647503347396916302 996 1974743923464120291412315103429 997 2054379914665857195769663307714 998 2137186202607647847390137715377 999 2223287379059125990596707421693 1000 2312812869554888253021688233758