0 0 1 0 2 0 3 0 4 1 5 1 6 3 7 4 8 7 9 9 10 15 11 18 12 27 13 34 14 47 15 58 16 79 17 96 18 127 19 155 20 199 21 242 22 308 23 371 24 465 25 561 26 694 27 833 28 1024 29 1223 30 1491 31 1778 32 2150 33 2556 34 3076 35 3642 36 4359 37 5151 38 6133 39 7225 40 8570 41 10066 42 11892 43 13937 44 16401 45 19173 46 22495 47 26228 48 30676 49 35692 50 41620 51 48316 52 56197 53 65094 54 75519 55 87303 56 101037 57 116571 58 134617 59 155008 60 178620 61 205312 62 236099 63 270896 64 310929 65 356136 66 408012 67 466576 68 533588 69 609202 70 695542 71 792870 72 903774 73 1028727 74 1170789 75 1330734 76 1512262 77 1716447 78 1947786 79 2207811 80 2501887 81 2832173 82 3205149 83 3623655 84 4095562 85 4624668 86 5220392 87 5887772 88 6638203 89 7478141 90 8421402 91 9476324 92 10659496 93 11981652 94 13462837 95 15116578 96 16967157 97 19031690 98 21339367 99 23911784 100 26784202 101 29983520 102 33552363 103 37524292 104 41950574 105 46873000 106 52353401 107 58443342 108 65217451 109 72739402 110 81098897 111 90374416 112 100673980 113 112093729 114 124763739 115 138801770 116 154364008 117 171594463 118 190680835 119 211798431 120 235172800 121 261017268 122 289602197 123 321186790 124 356095277 125 394641540 126 437214241 127 484193206 128 536043465 129 593224039 130 656291319 131 725798557 132 802411116 133 886795314 134 979745536 135 1082063268 136 1194696746 137 1318607995 138 1454928170 139 1604811003 140 1769604041 141 1950689366 142 2149671616 143 2368203492 144 2608194517 145 2871619306 146 3160747445 147 3477935629 148 3825880038 149 4207389194 150 4625663763 151 5084047827 152 5586336879 153 6136508740 154 6739061584 155 7398720932 156 8120813954 157 8910949674 158 9775430831 159 10720908881 160 11754836129 161 12885091212 162 14120479283 163 15470324878 164 16945022241 165 18555597440 166 20314312565 167 22234192280 168 24329691930 169 26616184833 170 29110697479 171 31831360196 172 34798214768 173 38032622993 174 41558159372 175 45399973817 176 49585774371 177 54145147376 178 59110637726 179 64517020755 180 70402496451 181 76807909113 182 83778062811 183 91360893815 184 99608917943 185 108578349802 186 118330703209 187 128931853960 188 140453804373 189 152973696464 190 166575755615 191 181350249010 192 197395636279 193 214817471031 194 233730774520 195 254258890841 196 276536105069 197 300706448328 198 326926597163 199 355364629159 200 386203227335 201 419638401789 202 455883029420 203 495165541663 204 537733848677 205 583853998347 206 633814519543 207 687925076134 208 746521272875 209 809963310307 210 878641319386 211 952974030913 212 1033414689510 213 1120449773285 214 1214605549086 215 1316446859325 216 1426584408648 217 1545673644365 218 1674422848112 219 1813592164372 220 1964002586151 221 2126535165393 222 2302141016023 223 2491840754295 224 2696735626249 225 2918007259938 226 3156930044678 227 3414871256779 228 3693304861550 229 3993812092677 230 4318096832119 231 4667986767266 232 5045450531829 233 5452599544527 234 5891707148475 235 6365211262241 236 6875735742827 237 7426094034649 238 8019313019028 239 8658637830185 240 9347558524100 241 10089816267508 242 10889433151435 243 11750720031379 244 12678309863485 245 13677167462349 246 14752626827522 247 15910403138829 248 17156634543931 249 18497896803753 250 19941250083894 251 21494256663407 252 23165033390426 253 24962272941888 254 26895302621974 255 28974109784447 256 31209407753870 257 33612666039190 258 36196184312041 259 38973128147633 260 41957612038428 261 45164741562316 262 48610706550423 263 52312830630070 264 56289675871662 265 60561100804514 266 65148377949412 267 70074261628131 268 75363119986357 269 81041014007354 270 87135845905591 271 93677450971746 272 100697764357098 273 108230927677588 274 116313476485858 275 124984463719960 276 134285670534176 277 144261748983352 278 154960459107301 279 166432833655055 280 178733444707846 281 191920593501696 282 206056610381878 283 221208073219300 284 237446144837633 285 254846824084137 286 273491325418225 287 293466367097529 288 314864598313646 289 337784929571053 290 362333013281442 291 388621622196787 292 416771190144763 293 446910244983426 294 479176017116595 295 513714934314605 296 550683306432307 297 590247890521836 298 632586661258427 299 677889455679749 300 726358840145187 301 778210845273114 302 833675941407209 303 892999875828087 304 956444770222148 305 1024290073577036 306 1096833796972315 307 1174393597317478 308 1257308166452914 309 1345938462976426 310 1440669274775790 311 1541910618134290 312 1650099495342996 313 1765701482735679 314 1889212707429519 315 2021161648846803 316 2162111361623531 317 2312661517974017 318 2473450907307087 319 2645159750251754 320 2828512508954544 321 3024280507623171 322 3233285091659685 323 3456400593590604 324 3694557884045485 325 3948747726792092 326 4220024769447842 327 4509511336959136 328 4818401915776324 329 5147967440816111 330 5499560333558338 331 5874619344324338 332 6274675211652970 333 6701356129532398 334 7156394103557279 335 7641631120821032 336 8159026287682214 337 8710662789504996 338 9298755904572142 339 9925660851702028 340 10593881786184843 341 11306080644661538 342 12065087241870055 343 12873909235390007 344 13735743455602967 345 14653987127930678 346 15632250584165082 347 16674369895761545 348 17784421132557852 349 18966734579055749 350 20225910725570832 351 21566836260248168 352 22994701999532400 353 24515020870919041 354 26133648014312961 355 27856800996015897 356 29691082339040164 357 31643502237601061 358 33721503804690921 359 35932988587346258 360 38286344853846361 361 40790476245322677 362 43454833461738899 363 46289446425135462 364 49304959765329452 365 52512668913116925 366 55924559833559738 367 59553349516249512 368 63412530455007132 369 67516416057054235 370 71880190425562882 371 76519959269162049 372 81452805608348228 373 86696846834010367 374 92271297029096839 375 98196530900175522 376 104494153485056545 377 111187071763659236 378 118299572610992672 379 125857402986167803 380 133887857087131135 381 142419866120127014 382 151484095721525652 383 161113046423345329 384 171341162529178898 385 182204944518509209 386 193743070697080438 387 205996522924627255 388 219008722509443953 389 232825670799824568 390 247496100959165409 391 263071635135689127 392 279606953937339204 393 297159972088567943 394 315792027628783310 395 335568078178429127 396 356556912112469910 397 378831367796419529 398 402468569236747401 399 427550170912900195 400 454162620685936747 401 482397433144586111 402 512351482864189277 403 544127309510462340 404 577833444882903924 405 613584753381925309 406 651502796651979549 407 691716213416390582 408 734361125958872397 409 779581563774245115 410 827529916593411436 411 878367406791101418 412 932264594178238595 413 989401902651047567 414 1049970182550640252 415 1114171297641788345 416 1182218751474268893 417 1254338341449702452 418 1330768856324388729 419 1411762804861338492 420 1497587192396350674 421 1588524332392706682 422 1684872710854376199 423 1786947890010252737 424 1895083470315180877 425 2009632096493343532 426 2130966527927951161 427 2259480758405732142 428 2395591206865098498 429 2539737963415757941 430 2692386113711151241 431 2854027125175882508 432 3025180319703089673 433 3206394415528045834 434 3398249164533331771 435 3601357066873460352 436 3816365190923217933 437 4043957079595837924 438 4284854772908750503 439 4539820926972515787 440 4809661061286097320 441 5095225913624145665 442 5397413936539825931 443 5717173913859375562 444 6055507733486270754 445 6413473293956984550 446 6792187583524102376 447 7192829908261211822 448 7616645310591505615 449 8064948153774480164 450 8539125916569909223 451 9040643172636401681 452 9571045801904325153 453 10131965407500226406 454 10725123988693663208 455 11352338842462757367 456 12015527747618380274 457 12716714403098276204 458 13458034178093846286 459 14241740144649007664 460 15070209454380794265 461 15945950029006991585 462 16871607630614650086 463 17849973280416653707 464 18883991096532141772 465 19976766518637443831 466 21131574994957721630 467 22351871098590876449 468 23641298153940938022 469 25003698339443686212 470 26443123353068015493 471 27963845606040513729 472 29570370037402632330 473 31267446514198337313 474 33060082916496253013 475 34953558871485175419 476 36953440242944778410 477 39065594339896430534 478 41296205958364887346 479 43651794219765106349 480 46139230328065417034 481 48765756209104438598 482 51539004163069609519 483 54467017493575712715 484 57558272253881935258 485 60821700073971137492 486 64266712219309318154 487 67903224845537116775 488 71741685610997313313 489 75793101612177583471 490 80069068815916135947 491 84581802954613852795 492 89344172071194632340 493 94369730681588542180 494 99672755755398910031 495 105268284484498172293 496 111172154055226837307 497 117401043396402559813 498 123972517135036533152 499 130905071734963332599 500 138218184067810961154 501 145932362395147023688 502 154069200030155348573 503 162651431662012470445 504 171702992631788937017 505 181249081148147774076 506 191316223753804809076 507 201932344037016883185 508 213126834922992580935 509 224930634546475979927 510 237376306066300848640 511 250498121431234894428 512 264332149485950477456 513 278916348435752473944 514 294290663089235141899 515 310497126908187724649 516 327579969316783146701 517 345585728311567979856 518 364563368859889597273 519 384564407142190991438 520 405643041164360954946 521 427856287811379791332 522 451264126910242611742 523 475929652391289178789 524 501919231161234106074 525 529302669797260084785 526 558153389724574913881 527 588548611009620090585 528 620569545484605304565 529 654301599361221386977 530 689834586107002808390 531 727262949771042722438 532 766685999595215897196 533 808208156129977836217 534 851939209758940424576 535 897994591887509226528 536 946495659773650714166 537 997569995296593048807 538 1051351718721696781841 539 1107981817802557304107 540 1167608493365647594624 541 1230387521769013972591 542 1296482635474909007793 543 1366065922184103821462 544 1439318243874466417260 545 1516429676254136988881 546 1597599970083488726761 547 1683039034945758958750 548 1772967447041816881985 549 1867616981666234185317 550 1967231172071892108526 551 2072065895466067349292 552 2182389987988476285201 553 2298485889509297136254 554 2420650320253380030929 555 2549194990194034716760 556 2684447343391880869752 557 2826751338338824088269 558 2976468266666730333772 559 3133977611409907268209 560 3299677947381168061677 561 3473987884993292791439 562 3657347060303360031114 563 3850217172769459239785 564 4053083073734075077679 565 4266453907297749480439 566 4490864306854937978648 567 4726875649147836206043 568 4975077369390317124523 569 5236088339529739679773 570 5510558313503681963305 571 5799169441793015702168 572 6102637859460155578347 573 6421715350231402324889 574 6757191091173187034884 575 7109893480804759148797 576 7480692055589977450768 577 7870499497962927250156 578 8280273741257570135890 579 8711020175039708510718 580 9163793956676727824348 581 9639702433021305606099 582 10139907678550966053606 583 10665629154255111579662 584 11218146494162623874209 585 11798802424258299910997 586 12409005821281130467643 587 13050234916654380851558 588 13724040653693530940637 589 14432050203892949768035 590 15175970651148243056515 591 15957592850320020578728 592 16778795469769782949831 593 17641549224937532996955 594 18547921313434150150945 595 19500080059446398447316 596 20500299778844581820684 597 21550965873589515291674 598 22654580167826960283322 599 23813766495142054369817 600 25031276550448498557832 601 26309996016945004796814 602 27652950982796672070131 603 29063314659025794114142 604 30544414414557381843185 605 32099739141056397749509 606 33732946964903714823009 607 35447873320209930498699 608 37248539401739951725936 609 39139161013029476900741 610 41124157830227225053722 611 43208163098456853493074 612 45396033783040457295313 613 47692861194033075075402 614 50103982108378193527482 615 52634990409945014021187 616 55291749273899614431564 617 58080403917652128003174 618 61007394947163759530454 619 64079472323022463479342 620 67303709977608988638007 621 70687521110131156582486 622 74238674193610159921387 623 77965309723186414064684 624 81875957742834920388045 625 85979556182687757140947 626 90285470047325316118233 627 94803511490326281892645 628 99543960818998263859669 629 104517588467957327832630 630 109735677989352773718396 631 115210050102095052654530 632 120953087852099225346236 633 126977762929931043136223 634 133297663202455459175728 635 139927021509273732907575 636 146880745785540388559141 637 154174450566748045385947 638 161824489942502132435959 639 169847992020114299022535 640 178262894970944742800202 641 187087984726041035160216 642 196342934400431213787854 643 206048345518857761619516 644 216225791129302318967027 645 226897860883893486782324 646 238088208181153104563275 647 249821599456595947292832 648 262123965723910831623070 649 275022456461831852416160 650 288545495957925302619635 651 302722842213225510799062 652 317585648528730355410394 653 333166527887309292399900 654 349499620262676082707934 655 366620662979463487469817 656 384567064267623853374444 657 403377980146618413887564 658 423094394795201515278417 659 443759204554711769967490 660 465417305735356845617744 661 488115686386966086796753 662 511903522218571136526287 663 536832276843061637869312 664 562955806547445223176213 665 590330469781048077872237 666 619015241579761887477994 667 649071833136193460225443 668 680564816752928062172923 669 713561756407838477862235 670 748133344189415820988449 671 784353542851820676716062 672 822299734770198282673992 673 862052877568560178373299 674 903697666725300981203862 675 947322705453253462701110 676 993020682186000220976902 677 1040888555994115459417416 678 1091027750292011808658182 679 1143544355188192749291859 680 1198549338871046409016550 681 1256158768414668820290132 682 1316494040431031010071213 683 1379682121987446507979559 684 1445855802252782375414731 685 1515153955328858686383920 686 1587721814770809786368418 687 1663711260293620355950931 688 1743281117212413525040143 689 1826597469158033155857803 690 1913833984663071104269739 691 2005172258208076311699033 692 2100802166374759891056308 693 2200922239748324652489472 694 2305740051271833029922546 695 2415472621751688713596019 696 2530346843278058822060193 697 2650599921321202209499579 698 2776479836333664119809309 699 2908245825686558229956501 700 3046168886841691278994833 701 3190532302660828251171275 702 3341632189831788848817153 703 3499778071392065753562177 704 3665293474414249600590867 705 3838516553920195800698671 706 4019800744180031800307231 707 4209515438556617130822308 708 4408046699151196571096734 709 4615797997512597010529381 710 4833190987773836435859171 711 5060666313588976823410737 712 5298684450351416293333158 713 5547726584186414214775980 714 5808295529326343127780021 715 6080916685491702347340406 716 6366139037024492976678608 717 6664536195538375712812894 718 6976707487982028774832728 719 7303279092033596041127809 720 7644905220885152486903994 721 8002269359501641737442089 722 8376085554589475020743946 723 8767099760540006103563144 724 9176091243774233213461571 725 9603874047950085988938814 726 10051298522665952664986545 727 10519252918334618749297380 728 11008665050086063109050007 729 11520504033604159155075643 730 12055782095999458055373986 731 12615556464873548193897641 732 13200931338941413729288419 733 13813059943638933110453390 734 14453146675368403628576778 735 15122449338103844989545154 736 15822281476319489561076188 737 16554014808282698624242054 738 17319081764011285463192930 739 18118978132282909431082314 740 18955265821361301267194051 741 19829575738202581830086010 742 20743610791201749885123046 743 21699149021649788150187644 744 22698046869389835829276086 745 23742242578284264911104503 746 24833759747445263280686633 747 25974711034319177730844863 748 27167302016080102655531559 749 28413835215941466168785192 750 29716714301385896950836148 751 31078448461484007582928511 752 32501656970892533680082066 753 33989073948311306609051766 754 35543553317628735385293200 755 37168073980194936140548044 756 38865745207144526449942906 757 40639812260922874328891898 758 42493662255687614995737765 759 44430830266513379396025460 760 46455005697883496329689586 761 48570038922235143714080485 762 50779948199920892655057225 763 53088926892261295640789250 764 55501350980003364891711775 765 58021786899843106066814019 766 60654999712357504188554449 767 63405961615069129183910396 768 66279860815104364187802176 769 69282110776321558151286911 770 72418359856577686917004486 771 75694501351258270334041332 772 79116683960046158352298651 773 82691322694405445335877343 774 86425110244170676579127232 775 90325028822180557460779248 776 94398362506877120862630468 777 98652710103393001118281123 778 103095998544704216315135571 779 107736496855084799736943314 780 112582830699232951692198801 781 117643997541159546580835120 782 122929382438147736292445305 783 128448774495881171807247830 784 134212384012147304748313818 785 140230860337384467248869902 786 146515310481748360155478917 787 153077318499315587736672597 788 159928965681554296199297105 789 167082851593220589980328792 790 174552115985465376078016850 791 182350461622058910312626441 792 190492178056388547179701583 793 198992166398109824913713939 794 207865965110210862235085159 795 217129776878585334266309101 796 226800496598230840155518181 797 236895740521644787585595829 798 247433876617164027386927529 799 258434056186579922358807158 800 269916246793698906264789549 801 281901266557245117824775650 802 294410819864016927549808445 803 307467534560088608252008818 804 321095000680554064506700488 805 335317810780354649735195544 806 350161601931643811573472720 807 365653099455365909049283594 808 381820162457858040398159992 809 398691831245702733881350351 810 416298376695428582011499141 811 434671351657285437685225193 812 453843644475946005675599884 813 473849534713843134167547502 814 494724751166752964670250207 815 516506532264338305600770620 816 539233688952564252399580585 817 562946670158269317917124920 818 587687630940692590597345242 819 613500503438417632529640857 820 640431070725055215488235364 821 668527043690959806783109928 822 697838141073506657619618275 823 728416172762767318597444859 824 760315126515052353440482545 825 793591258211466720488237728 826 828303185804683868788449140 827 864511987102216773146882137 828 902281301540987316525039363 829 941677436113495182196050895 830 982769475612908711813739393 831 1025629397370362150704631384 832 1070332190665301318403263086 833 1116955980996181284077710847 834 1165582159406954707058413379 835 1216295517071790918114200079 836 1269184385349222649735103678 837 1324340781524502080053409251 838 1381860560468374104210912430 839 1441843572448689722421485433 840 1504393827341429408875028541 841 1569619665496602061214080734 842 1637633935525408057987278278 843 1708554179284685945280626632 844 1782502824346420585051491352 845 1859607384250515605129786076 846 1940000666851690651885614710 847 2023820991082646295329226844 848 2111212412469265288023058250 849 2202324957745826832836082887 850 2297314868932878629010255410 851 2396344857253618597719203556 852 2499584367280428278425235873 853 2607209851717485472926832180 854 2719405057242381555143865127 855 2836361321845118332242908836 856 2958277884121157216845476136 857 3085362204991898864633407795 858 3217830302345668632836791527 859 3355907099110343688587341498 860 3499826785289960954100448813 861 3649833194517167442817524707 862 3806180195696198973584898076 863 3969132100332172565625163083 864 4138964086167046955802737374 865 4315962637765405848797637726 866 4500426004719665348455075585 867 4692664678168941483465099506 868 4893001886354281319413484869 869 5101774109959573606257836778 870 5319331618018097092996893787 871 5546039025193409799458328605 872 5782275871276264809800391247 873 6028437223770282582903361414 874 6284934304474610108255382634 875 6552195141005320261356889635 876 6830665244235514502448173902 877 7120808312670286698796323064 878 7423106964813830922966818560 879 7738063500625050086756066440 880 8066200693202283938135151000 881 8408062611879951931880597219 882 8764215477967542723352555182 883 9135248554406902615044868499 884 9521775070675041968845405428 885 9924433184308801707242168661 886 10343886980482894238145305869 887 10780827511125837389044509977 888 11235973875117673420529565797 889 11710074341170550320033090141 890 12203907515057135268254878962 891 12718283552913518650597981052 892 13254045422412020634642453399 893 13812070213665851052494950184 894 14393270501801555288394200656 895 14998595763206940934302571977 896 15629033847541785102506501915 897 16285612507676008992993324252 898 16969400989805658964859847080 899 17681511686080476303114889597 900 18423101852168994126793745797 901 19195375392277063158027795823 902 19999584714234858060811292349 903 20837032657364398713622321056 904 21709074495946291177910746694 905 22617120021208931747003904100 906 23562635704878174207648852838 907 24547146947438131910940917001 908 25572240414377237440390918597 909 26639566463815107146412592523 910 27750841669038556773551727772 911 28907851439605958572277550282 912 30112452744821978920353991357 913 31366576943525715891840666877 914 32672232724288908580976117318 915 34031509160272776821439644335 916 35446578883157316056606309644 917 36919701380720493092566708720 918 38453226422822538425183180598 919 40049597620726775430036163656 920 41711356124879595090138499457 921 43441144466462008965640474229 922 45241710548230803679207310781 923 47115911790371750656822039291 924 49066719437308415646304260412 925 51097223031630252830103428030 926 53210635061541417066559758446 927 55410295788468763332106233300 928 57699678261723152290851907998 929 60082393527363385137220159305 930 62562196038686976805442974205 931 65142989276046717402799430315 932 67828831583987527159390205938 933 70623942233993856725981503110 934 73532707721455648538664113827 935 76559688305779205274994362855 936 79709624802910936024562680272 937 82987445639884559517302285090 938 86398274181369602845196474822 939 89947436338567741097069766927 940 93640468471198321008432261243 941 97483125593711171130880540868 942 101481389897289181212160767066 943 105641479599630043487677578404 944 109969858134952705135966349625 945 114473243697133394504720188510 946 119158619149366371260959735866 947 124033242314238685810347338044 948 129104656658635178961845805781 949 134380702388421506069315267882 950 139869527968419285606189282207 951 145579602083759230339866895168 952 151519726059306715338283505368 953 157699046754469191551047222907 954 164127069951348852970035330018 955 170813674254865326720434560936 956 177769125524175908679494979494 957 185004091855432081025989543329 958 192529659136666150452635754823 959 200357347196366609704901212670 960 208499126568112133586985823661 961 216967435894456402466743809396 962 225775199994127598802671679686 963 234935848617490479597440575562 964 244463335916155362989096338617 965 254372160653568768128025261420 966 264677387184426427026563163021 967 275394667231771032439166704124 968 286540262491717716771816726034 969 298131068096848404496138591263 970 310184636970476940544917938756 971 322719205105167186809795718433 972 335753717800133042682997958925 973 349307856893417827214188039845 974 363402069026089528363063064846 975 378057594977051587450208213349 976 393296500108507015055741307004 977 409141705963578437851335537500 978 425617023059131108916589964653 979 442747184918419821774014920039 980 460557883389839174434897224118 981 479075805299747646032922462545 982 498328670489116856411572174146 983 518345271285574086950683193826 984 539155513464318379882694897051 985 560790458753342136040830682183 986 583282368940443274032805489295 987 606664751641609378817725466389 988 630972407792559576890425265632 989 656241480927481581743688589955 990 682509508311367829031052861049 991 709815473994773010216746268597 992 738199863862355746807958809378 993 767704722749164377436321075949 994 798373713701353858670601361087 995 830252179460809883789314200210 996 863387206256083492268834110327 997 897827689985034388054702726196 998 933624404877723008811705095241 999 970830074731307147321068621305 1000 1009499446812070961356406862984