1 0 2 0 3 0 4 1 5 0 6 3 7 1 8 5 9 5 10 10 11 8 12 22 13 19 14 33 15 40 16 62 17 67 18 107 19 118 20 175 21 208 22 282 23 331 24 462 25 542 26 712 27 859 28 1112 29 1323 30 1709 31 2030 32 2568 33 3078 34 3830 35 4577 36 5687 37 6760 38 8291 39 9885 40 12045 41 14290 42 17334 43 20515 44 24710 45 29242 46 35004 47 41282 48 49283 49 57963 50 68836 51 80855 52 95636 53 112019 54 132102 55 154381 56 181406 57 211622 58 247848 59 288458 60 337032 61 391393 62 455934 63 528586 64 614180 65 710558 66 823786 67 951215 68 1100216 69 1268259 70 1463731 71 1684189 72 1940055 73 2228368 74 2561733 75 2937839 76 3371069 77 3859599 78 4421183 79 5053951 80 5779405 81 6596892 82 7531426 83 8583993 84 9785179 85 11136820 86 12675885 87 14407407 88 16374757 89 18586433 90 21095468 91 23913679 92 27105107 93 30688045 94 34738225 95 39281875 96 44411103 97 50160159 98 56640478 99 63899560 100 72069922 101 81214799 102 91495234 103 102992338 104 115900592 105 130326676 106 146502827 107 164567070 108 184800964 109 207378078 110 232638556 111 260804734 112 292283881 113 327357198 114 366517484 115 410115316 116 458744981 117 512847153 118 573134472 119 640157026 120 714775383 121 797668323 122 889872804 123 992231979 124 1105989220 125 1232185580 126 1372319474 127 1527667332 128 1700031549 129 1890981530 130 2102677857 131 2337043200 132 2596675582 133 2883917471 134 3201888072 135 3553447089 136 3942329040 137 4372013552 138 4846981561 139 5371450953 140 5950790661 141 6590116752 142 7295848442 143 8074177760 144 8932788344 145 9879150468 146 10922450742 147 12071704837 148 13337876604 149 14731824261 150 16266641415 151 17955374719 152 19813643954 153 21857122642 154 24104416408 155 26574324708 156 29289014209 157 32270988059 158 35546630216 159 39142868674 160 43091066055 161 47423398152 162 52177143842 163 57390688212 164 63108300847 165 69375749817 166 76245547042 167 83772197173 168 92017973378 169 101047691456 170 110935136709 171 121757343265 172 133601646529 173 146559499080 174 160734235869 175 176234295523 176 193181842249 177 211705371504 178 231949174473 179 254065361454 180 278224277845 181 304605790874 182 333410847842 183 364852000084 184 399166088819 185 436604054077 186 477444897552 187 521984593599 188 570551563015 189 623494659909 190 681200167634 191 744078918003 192 812584998474 193 887201795088 194 968462718195 195 1056936145417 196 1153248191276 197 1258066630933 198 1372125976103 199 1496210137712 200 1631180195447 201 1777955786324 202 1937545645490 203 2111027829112 204 2299583361126 205 2504475032407 206 2727084666038 207 2968890496548 208 3231508183912 209 3516666929948 210 3826254710506 211 4162292849296 212 4526986124618 213 4922695849479 214 5351995089315 215 5817640478109 216 6322633164752 217 6870189094832 218 7463806567155 219 8107235091540 220 8804549927586 221 9560119862699 222 10378689596295 223 11265346199305 224 12225610492482 225 13265402424541 226 14391142049892 227 15609714337420 228 16928580913110 229 18355744153426 230 19899871260280 231 21570258057334 232 23376966308325 233 25330787998360 234 27443397528250 235 29727316508284 236 32196082920781 237 34864217157030 238 37747409557712 239 40862488860674 240 44227630373625 241 47862327176002 242 51787621804556 243 56026081406346 244 60602055018152 245 65541654452814 246 70873040350819 247 76626409655531 248 82834314366388 249 89531657530408 250 96756047834449 251 104547806779256 252 112950363548852 253 122010275067059 254 131777666607227 255 142306267762208 256 153653903384790 257 165882549488176 258 179058880818355 259 193254349672441 260 208545797676420 261 225015562222755 262 242752159239738 263 261850423235966 264 282412269932672 265 304546874925912 266 328371526810842 267 354011851633067 268 381602766380812 269 411288758143149 270 443224950611355 271 477577445966599 272 514524519274081 273 554257033961178 274 596979778524178 275 642911968797418 276 692288744879393 277 745361772764915 278 802400922513924 279 863694985490328 280 929553554651532 281 1000307876864659 282 1076312960852422 283 1157948583858609 284 1245621656871844 285 1339767409822395 286 1440852044329319 287 1549374125988461 288 1665867560926760 289 1790903224332191 290 1925092302801545 291 2069088194775094 292 2223590262225729 293 2389346044767514 294 2567155472391452 295 2757873436796903 296 2962414524551287 297 3181755998002796 298 3416943111560229 299 3669092562947209 300 3939398466114492 301 4229136337308434 302 4539669808825289 303 4872455226272900 304 5229049192993382 305 5611113866658945 306 6020425438970373 307 6458880226226126 308 6928504203516186 309 7431460000193370 310 7970057617181668 311 8546762454621612 312 9164207360806611 313 9825201830055653 314 10532745552202157 315 11290038941033163 316 12100498367772470 317 12967768203311771 318 13895737946522283 319 14888555980366927 320 15950648834009718 321 17086736883653493 322 18301856009741789 323 19601375505293501 324 20991022426806669 325 22476901998738266 326 24065524996046666 327 25763830975818047 328 27579219062477624 329 29519574382265842 330 31593302673734740 331 33809360339388492 332 36177293358500760 333 38707271428927893 334 41410131708177969 335 44297417580816552 336 47381427824549396 337 50675260595570632 338 54192868692421221 339 57949109432795877 340 61959806758699908 341 66241807765517867 342 70813052490046312 343 75692637935342422 344 80900896488566496 345 86459468397759722 346 92391389868611543 347 98721175070983594 348 105474915098877025 349 112680370703769770 350 120367083448874471 351 128566480522357689 352 137311999562552729 353 146639207073871502 354 156585938586770557 355 167192432369489711 356 178501486790109524 357 190558611233558607 358 203412202740127919 359 217113716273284197 360 231717862967274178 361 247282802133248867 362 263870363731384419 363 281546264802297206 364 300380359070882636 365 320446880818328063 366 341824724882116347 367 364597721325382349 368 388854949488996276 369 414691047229566902 370 442206563089986494 371 471508304332804863 372 502709731788316531 373 535931351389985445 374 571301156801389354 375 608955069733303303 376 649037436024653789 377 691701520651918493 378 737110063619413380 379 785435836242945938 380 836862263953596939 381 891584051228803388 382 949807879214337044 383 1011753107548488856 384 1077652555643526665 385 1147753290584583329 386 1222317501945751059 387 1301623386035989340 388 1385966125236827353 389 1475658880072211287 390 1571033885344391300 391 1672443562804549581 392 1780261747787083591 393 1894884936759822005 394 2016733659697811366 395 2146253878451650145 396 2283918521873594937 397 2430229052742980751 398 2585717184616306868 399 2750946637113133846 400 2926515055589905951 401 3113055976872943054 402 3311240975288033175 403 3521781863413191556 404 3745433090684972448 405 3982994206577476702 406 4235312540939563907 407 4503285960141193143 408 4787865861628146129 409 5090060257001081775 410 5410937116961346498 411 5751627819170983811 412 6113330883794365186 413 6497315828283981457 414 6904927338283283883 415 7337589576187471203 416 7796810837217734165 417 8284188363918506947 418 8801413542742941710 419 9350277282526007120 420 9932675813150815579 421 10550616692485675361 422 11206225275594184150 423 11901751421879487609 424 12639576710867190095 425 13422221929328147727 426 14252355118161982846 427 15132799928089138864 428 16066544591563683946 429 17056751245518340189 430 18106765932569158045 431 19220129000241833785 432 20400586247303745595 433 21652100520937211514 434 22978864136836204072 435 24385311809258961050 436 25876134487609781627 437 27456293769199323141 438 29131037310768826031 439 30905914890181505391 440 32786795568747959218 441 34779885586374405334 442 36891747469706604699 443 39129319965498965179 444 41499939310956177220 445 44011361432375683987 446 46671785617683950378 447 49489879232237132781 448 52474804059560598886 449 55636243813644075069 450 58984433442847909113 451 62530189748271284875 452 66284943977787624799 453 70260775893703392754 454 74470450019141013768 455 78927453535378482204 456 83646036581979214213 457 88641254405164182792 458 93929012156376539977 459 99526111758531936467 460 105450301695404012723 461 111720329112854189420 462 118355995144363792192 463 125378212819725841280 464 132809068530513001683 465 140671886380144864686 466 148991296457506551581 467 157793306330137100761 468 167105376865628077854 469 176956501644429254140 470 187377291147495269959 471 198400060948023761723 472 210058925170687885255 473 222389894413034715137 474 235430979477834554734 475 249222300075592131393 476 263806199937688719501 477 279227367462940890405 478 295532963436159079244 479 312772754904684867697 480 330999256856357007784 481 350267880747463501955 482 370637091636801818079 483 392168572936316667372 484 414927400655124792454 485 438982226109349387373 486 464405469103706440345 487 491273520519050582932 488 519666956450657377738 489 549670762793074722102 490 581374572565175679964 491 614872914833564086926 492 650265477687416677804 493 687657384085772231886 494 727159483201901544772 495 768888656049256459756 496 812968138197749146304 497 859527858330026005118 498 908704795643934117157 499 960643354817613980589 500 1015495761756004453694 501 1073422478803781295521 502 1134592642871910330147 503 1199184525134531870393 504 1267386015988569227832 505 1339395133907639042832 506 1415420562146875890427 507 1495682211908659243153 508 1580411816210016252633 509 1669853553045255818427 510 1764264702390039660541 511 1863916335629409785731 512 1969094042285351116900 513 2080098692621402457890 514 2197247241354491675161 515 2320873571054536807030 516 2451329380843562026434 517 2588985118986448090893 518 2734230965396880029300 519 2887477862671701817955 520 3049158602121047887391 521 3219728963440593969770 522 3399668914971395098931 523 3589483873239714705667 524 3789706029238719957753 525 4000895740204868426379 526 4223642994907942312442 527 4458568951285530402934 528 4706327555041684060649 529 4967607238137492801997 530 5243132706442731065654 531 5533666815594285100061 532 5840012545031767977920 533 6163015069399084310419 534 6503563938039382630911 535 6862595361942425104345 536 7241094619690788079464 537 7640098581964304686172 538 8060698367034318938696 539 8504042127042845410168 540 8971337978454697779784 541 9463857076751772361179 542 9982936849793079691167 543 10529984390226229372274 544 11106480022494154307222 545 11713981045188383709669 546 12354125665504235982027 547 13028637126968340261021 548 13739328048506484267419 549 14488104976500323138635 550 15276973169322056667357 551 16108041616541304342699 552 16983528313831657383141 553 17905765796390578069443 554 18877206953567890269333 555 19900431128217237792184 556 20978150525272728003431 557 22113216933858121380633 558 23308628789388399579125 559 24567538580864839897041 560 25893260631946998842360 561 27289279262007455226759 562 28759257358055142118794 563 30307045364862989024143 564 31936690726681870220707 565 33652447789143221533130 566 35458788197441603880783 567 37360411800816630613759 568 39362258102364862061674 569 41469518265786898844606 570 43687647721288994419736 571 46022379384014700178923 572 48479737530688565197926 573 51066052349820390856813 574 53787975214910894083107 575 56652494698206676573453 576 59666953378525458090151 577 62839065463146396998379 578 66176935281719106011283 579 69689076674904869265104 580 73384433340517796472063 581 77272400162900542372339 582 81362845593530563672415 583 85666135111943291900242 584 90193155840650394446319 585 94955342346853981631076 586 99964703710808812125147 587 105233851897750250666191 588 110776031519947918905256 589 116605151030359584600691 590 122735815441737989299038 591 129183360617704184440433 592 135963889237566811075165 593 143094308486973535767140 594 150592369584789633697991 595 158476709204445766729314 596 166766892909519331434529 597 175483460668586167035104 598 184647974579294033777150 599 194283068874194774685318 600 204412502349362282551326 601 215061213296604064288216 602 226255377092341069562505 603 238022466533078277419892 604 250391315083642941582453 605 263392183138157536620851 606 277056827474173107837631 607 291418574010990343340454 608 306512394068095923115366 609 322374984246913099950246 610 339044850148656378113595 611 356562394064883465915174 612 374970006871875921084353 613 394312164280171018301000 614 414635527690333457961491 615 435989049822478762752854 616 458424085392348917133291 617 481994507019245171046419 618 506756826662238653364127 619 532770322789507596727714 620 560097173602924898009853 621 588802596544202167929977 622 618954994432679946467050 623 650626108484626789671393 624 683891178594563740846703 625 718829111154324387074922 626 755522654823478850328767 627 794058584555181850969378 628 834527894327102446375338 629 877025998912587757566348 630 921652945180920290959580 631 968513633295904999696582 632 1017718048344307789408401 633 1069381502800731674042607 634 1123624890406874421258808 635 1180574951912679499711121 636 1240364553307835342250346 637 1303132977035959773171968 638 1369026226874893195890726 639 1438197347024517645104476 640 1510806756145338014625888 641 1587022596942976795934147 642 1667021102106899039437474 643 1750986977257326826876271 644 1839113801779480249266422 645 1931604448263446257518374 646 2028671521505870627966138 647 2130537817862164179496870 648 2237436805989259556095131 649 2349613129844590327464687 650 2467323135072557732871444 651 2590835419728323094710073 652 2720431410569449098767236 653 2856405965957240875136114 654 2999068006706297099456907 655 3148741176024683254910365 656 3305764530000728675148263 657 3470493259888736503553928 658 3643299447777427872692590 659 3824572857013452103130328 660 4014721759102831552511708 661 4214173798593786442667056 662 4423376897815075998821805 663 4642800203116474518970523 664 4872935074650064965060550 665 5114296121495293687410761 666 5367422284345447709951769 667 5632877967729140933143795 668 5911254224179152818212295 669 6203169992508439082438485 670 6509273392817401196392814 671 6830243080595459427380177 672 7166789662771300158735658 673 7519657178296559701341079 674 7889624646367765657588818 675 8277507685113143593648346 676 8684160204121467505718297 677 9110476173903333099983478 678 9557391475958192371644027 679 10025885836825153105492996 680 10516984850112923048863418 681 11031762090200480559807676 682 11571341321954003592632585 683 12136898810493474046759109 684 12729665735735178562419366 685 13350930716116089008500952 686 14002042446640226395125406 687 14684412456058982061967729 688 15399517988775429259695625 689 16148905016726963101618092 690 16934191387325381222197142 691 17757070113190652126653137 692 18619312810289105023054912 693 19522773290737192484530410 694 20469391317459371733197362 695 21461196527532927965728610 696 22500312532036253606417797 697 23588961199855907723237338 698 24729467133951423289815011 699 25924262348210931681181545 700 27175891154138172480281806 701 28487015266241768779707308 702 29860419136173146574708896 703 31299015525287049477827575 704 32805851326546570094513495 705 34384113646320625677983802 706 36037136157947023789324860 707 37768405738560083756984340 708 39581569402089326034394426 709 41480441540962933121712024 710 43469011490545040672709536 711 45551451429966209651389721 712 47732124634595452706105908 713 50015594095037576885533097 714 52406631519228534202759135 715 54910226733844191073977903 716 57531597503033494518296145 717 60276199782139531789205763 718 63149738425981385224263013 719 66158178370934814128752412 720 69307756312080717674934710 721 72604992896371201844979790 722 76056705454923794166464043 723 79670021297254402872542633 724 83452391592559003665417473 725 87411605862877159803055630 726 91555807115418000266299331 727 95893507641079774926992871 728 100433605508799966056791396 729 105185401785155526706061963 730 110158618511407956992670853 731 115363417470007908411088897 732 120810419775530117464506236 733 126510726324872672879836045 734 132475939144704308680400503 735 138718183674056238626893224 736 145250132023311828758028614 737 152085027250816968682895207 738 159236708701912335907140315 739 166719638455222882728197529 740 174548928924855352168125641 741 182740371667261902981940457 742 191310467445597270594677500 743 200276457604586795118714109 744 209656356813263773372115372 745 219468987233217540592202472 746 229734014174625902052723970 747 240471983302732903252666037 748 251704359462376958447805307 749 263453567188678701879707498 750 275743032977275984234947193 751 288597229388128504277656275 752 302041721062550597830637691 753 316103212733911492311381161 754 330809599318462059310298770 755 346190018173690103497420677 756 362274903618037219585642363 757 379096043806933508381415369 758 396686640066978437662711382 759 415081368791419295502811851 760 434316446007423624747038612 761 454429694727186656727631083 762 475460615202766925362768469 763 497450458206332871714680951 764 520442301465899587250702626 765 544481129388695085717448707 766 569613916213275725523714283 767 595889712733869306878661007 768 623359736750031133724520230 769 652077467397386459654334044 770 682098743525512005945997840 771 713481866292059833859406484 772 746287706153228051968368825 773 780579814434132226583000905 774 816424539674407578818562662 775 853891148948259776284058335 776 893051954370790590259608335 777 933982445006793715152489823 778 976761424411718309594889311 779 1021471154039395027537120174 780 1068197502765581508856853869 781 1117030102781860669549053246 782 1168062512129918569203533716 783 1221392384152339510962244182 784 1277121644152657404381286223 785 1335356673564208110912657443 786 1396208501945119250477883745 787 1459793007124339962788768152 788 1526231123842684132464434813 789 1595649061241258004284944737 790 1668178529570089014728057641 791 1743956976499078832918436643 792 1823127833435327210117918967 793 1905840772261172112669428660 794 1992251972930803756795665358 795 2082524402374692776371802511 796 2176828105186292711035817443 797 2275340506578042301351299068 798 2378246728120749127395887041 799 2485739916794291439547035937 800 2598021587906605438666220730 801 2715301982453186881638030170 802 2837800439520489474561479997 803 2965745784353396729012786659 804 3099376732740380809924485877 805 3238942312388425595925075708 806 3384702301995683830197612934 807 3536927688750119649946675193 808 3695901145020921970221556172 809 3861917525031734161484589150 810 4035284382346121002563123136 811 4216322509020106629025469358 812 4405366497321049440182975376 813 4602765324938874014946973513 814 4808882964663400855134451063 815 5024099019530814645461373207 816 5248809384493570466903292209 817 5483426935700104374124681196 818 5728382248525780282464919917 819 5984124345531578623116930989 820 6251121475586193938020667960 821 6529861925425548025119155813 822 6820854864987294563087703293 823 7124631227899777168093338317 824 7441744628573215318846909033 825 7772772317386628686613685605 826 8118316175537427316449970705 827 8479003751170509847270856169 828 8855489338482622089545564954 829 9248455101552176991589953885 830 9658612244729559259085949342 831 10086702231482304648664996506 832 10533498053680729256232777374 833 10999805553374284470961948770 834 11486464799206946985194664548 835 11994351519690436385579191592 836 12524378595659457844070100481 837 13077497614309918675568358206 838 13654700487334406685119221181 839 14257021135752762399808227118 840 14885537244157456420753450030 841 15541372087184387274009067298 842 16225696431150786819195172408 843 16939730513900796817131551286 844 17684746106040246971763459110 845 18462068656849675613291602786 846 19273079528316252003656415695 847 20119218320842119288978763485 848 21001985294349760331003831649 849 21922943888631969694033530709 850 22883723346969440224875741445 851 23886021447176908478922619852 852 24931607344427513738454093351 853 26022324530354816099573897500 854 27160093913134930830267868397 855 28346917023413853325988745080 856 29584879351163455457958772562 857 30876153818726126628890634913 858 32223004395543010870032031293 859 33627789860252291316151490272 860 35092967716096790072976397556 861 36621098265787880368601535056 862 38214848852244727011134450786 863 39876998271853147232356276915 864 41610441367181073168409062710 865 43418193806331842685227664135 866 45303397056431484450749634258 867 47269323559010911922298761766 868 49319382115382830517449259095 869 51457123490400069286447090785 870 53686246243346718058608941533 871 56010602795024301188362892205 872 58434205740487638227679063246 873 60961234417221759495818164651 874 63596041738973532616914660229 875 66343161305816316730353797281 876 69207314801480398339746385728 877 72193419689376804007492213475 878 75306597219231125710709183927 879 78552180756671428387024896748 880 81935724448640593782321950018 881 85463012237966081239426897406 882 89140067240986455450974455024 883 92973161502634653126834440639 884 96968826143987471757480704835 885 101133861917832400934395044799 886 105475350188458858648877817079 887 110000664352466802485655908381 888 114717481718091596152692370623 889 119633795861177696465545052075 890 124757929476693411513313226731 891 130098547745364220493038512681 892 135664672235819701056661124682 893 141465695363389975330807549876 894 147511395427567414957874088655 895 153811952250950220869045554287 896 160377963443431334328506612301 897 167220461316261743127205789025 898 174350930471636195034660829001 899 181781326094384755995540807240 900 189524092973450186319024221877 901 197592185281841828431955466651 902 205999087144936717511495886196 903 214758834028090538441373155558 904 223886034975790891161555224794 905 233395895735764780156032606067 906 243304242802818719450288651970 907 253627548418463675566885358186 908 264382956563847513776039725014 909 275588309984893179574457522399 910 287262178290123139291854924984 911 299423887163135826835884645069 912 312093548733402458643452821221 913 325292093150655983710608741017 914 339041301409975985430689156309 915 353363839476404112672116493804 916 368283293759895898023796145923 917 383824207993282811067143818843 918 400012121568039435989661702088 919 416873609384666505755622065006 920 434436323276782648343122944526 921 452729035070192826164553530200 922 471781681340656823926163756693 923 491625409936427846022938355849 924 512292628334272989026679909271 925 533817053900218869819888179041 926 556233766129107783765995110179 927 579579260939780320625559859099 928 603891507105757959092848240858 929 629210004904244058086119779797 930 655575847069550993395483841368 931 683031782140236890375553795221 932 711622280292773922304710526665 933 741393601757994352314236154947 934 772393867920366956809925556041 935 804673135203848218588915517889 936 838283471852147228410847078736 937 873279037715222993886967283004 938 909716167158237146828505500576 939 947653455213474815373897753667 940 987151847100483723328205097147 941 1028274731244305027855464394881 942 1071088035926764697498201060918 943 1115660329710776787139252231063 944 1162062925783090100933509548547 945 1210369990366278731431871648039 946 1260658655356670782909974821285 947 1313009135350694410160473389600 948 1367504849228458789430144470253 949 1424232546469619867118482725413 950 1483282438383397160716979061380 951 1544748334441321457761346837051 952 1608727783908623372929622162968 953 1675322222977404106496292670334 954 1744637127612611933097361180746 955 1816782172329636331184649901332 956 1891871395130807146243567132386 957 1970023368836473662901938913104 958 2051361379055451511697205921596 959 2136013609048657153336413058123 960 2224113331749547839770043332559 961 2315799109214709697558366881501 962 2411214999788470887173611282888 963 2510510773275886665852564674044 964 2613842134429768448992902555530 965 2721370955068700036579097627083 966 2833265515155159239961944748928 967 2949700753174995634761349802255 968 3070858526172603209417024506628 969 3196927879809185263427401175683 970 3328105328825577745473983799545 971 3464595148305151356719379884846 972 3606609676147435170958787875284 973 3754369627178228792933404620959 974 3908104419338224235543064433776 975 4068052512408433184286554334879 976 4234461759748185082853259170488 977 4407589773538972165279122194320 978 4587704304046192949373220597201 979 4775083633429684916274586271472 980 4970016984654114724155882609041 981 5172804946070561134531303523411 982 5383759912262309363868637777901 983 5603206541769676407923371632483 984 5831482232331987585351077576255 985 6068937614308273577356747429129 986 6315937062963294485360411021048 987 6572859230330717216377645434884 988 6840097597392174389415313836400 989 7118061047338055043200917525175 990 7407174460704781377596081721769 991 7707879333212491314648424967023 992 8020634417158100130044222253257 993 8345916387250074911836081127962 994 8684220531804616757356634986662 995 9036061470256663630378751040832 996 9401973897974965322656659576262 997 9782513359406731893345139284908 998 10178257050615854861733369923613 999 10589804652317669402061412210151 1000 11017779194554578298028054136569