0 0 1 1 2 1 3 2 4 3 5 4 6 6 7 8 8 12 9 16 10 21 11 30 12 40 13 52 14 72 15 91 16 121 17 159 18 202 19 260 20 335 21 421 22 535 23 674 24 840 25 1052 26 1304 27 1614 28 1996 29 2451 30 3002 31 3674 32 4468 33 5442 34 6592 35 7971 36 9624 37 11584 38 13898 39 16691 40 19947 41 23823 42 28410 43 33782 44 40113 45 47610 46 56302 47 66572 48 78569 49 92547 50 108898 51 127999 52 150093 53 175933 54 205871 55 240544 56 280816 57 327401 58 381138 59 443389 60 515064 61 597654 62 692867 63 802279 64 927957 65 1072448 66 1237918 67 1427695 68 1645029 69 1893498 70 2177615 71 2502168 72 2872277 73 3294603 74 3775684 75 4323222 76 4946456 77 5654800 78 6459303 79 7373060 80 8409174 81 9583769 82 10914952 83 12421381 84 14125879 85 16053730 86 18231118 87 20690468 88 23466426 89 26596372 90 30125165 91 34101189 92 38576240 93 43613312 94 49278413 95 55644760 96 62798449 97 70831050 98 79843544 99 89955065 100 101290255 101 113990307 102 128216333 103 144140851 104 161956184 105 181884015 106 204157427 107 229043060 108 256838086 109 287863968 110 322480142 111 361093006 112 404134375 113 452098117 114 505525646 115 565008808 116 631208241 117 704859531 118 786754096 119 877790703 120 978945837 121 1091296057 122 1216035701 123 1354483971 124 1508072285 125 1678413023 126 1867250527 127 2076517495 128 2308345223 129 2565075720 130 2849266729 131 3163773462 132 3511682961 133 3896422468 134 4321749199 135 4791783696 136 5311039885 137 5884517746 138 6517630104 139 7216382252 140 7987328746 141 8837651549 142 9775225290 143 10808719168 144 11947535205 145 13202081365 146 14583681289 147 16104737971 148 17778843376 149 19620889719 150 21647057993 151 23875204021 152 26324713889 153 29016815298 154 31974735134 155 35223837862 156 38791719914 157 42708723240 158 47007759146 159 51724839581 160 56899291680 161 62573965564 162 68795508510 163 75615040054 164 83087973918 165 91274886849 166 100241798440 167 110060532862 168 120809278354 169 132573456824 170 145445642080 171 159526910533 172 174927201547 173 191765999154 174 210173303147 175 230290766762 176 252271886039 177 276283994828 178 302508806477 179 331143635120 180 362402972917 181 396520025706 182 433747446604 183 474360236050 184 518656582831 185 566960040552 186 619621932874 187 677023549957 188 739577854963 189 807733605809 190 881976810545 191 962834422889 192 1050877909182 193 1146726568311 194 1251050848976 195 1364578164697 196 1488095492003 197 1622455420951 198 1768581397401 199 1927472938090 200 2100211476142 201 2287968590818 202 2492010639236 203 2713708393044 204 2954544709539 205 3216122925332 206 3500176552918 207 3808581038019 208 4143361885089 209 4506709614789 210 4900991108556 211 5328763179649 212 5792788033452 213 6296050293604 214 6841770937974 215 7433430059617 216 8074783880675 217 8769886566974 218 9523114241655 219 10339190030491 220 11223207337445 221 12180664019367 222 13217488253710 223 14340073277526 224 15555313909442 225 16870644051439 226 18294074562896 227 19834244157961 228 21500459149905 229 23302748010528 230 25251916379497 231 27359603791098 232 29638344059341 233 32101640606177 234 34764028051568 235 37641156717219 236 40749874950938 237 44108315562005 238 47735990342983 239 51653901318435 240 55884636387387 241 60452498634295 242 65383629119413 243 70706139071599 244 76450255477834 245 82648485389059 246 89335764289162 247 96549651725794 248 104330514457773 249 112721728383570 250 121769900098254 251 131525109706144 252 142041140073206 253 153375770068020 254 165591047898446 255 178753598496896 256 192934957402006 257 208211929995457 258 224666943657283 259 242388484068663 260 261471503322525 261 282017885727087 262 304136946828323 263 327945965672236 264 353570721866185 265 381146140962587 266 410816904012988 267 442738149268305 268 477076213660086 269 514009421646840 270 553728898481175 271 596439520434970 272 642360824966647 273 691728061161612 274 744793286483599 275 801826535596217 276 863117042931234 277 928974637155280 278 999731098131244 279 1075741720173966 280 1157386928442970 281 1245074008839872 282 1339238933422676 283 1440348401319852 284 1548901857677368 285 1665433806645164 286 1790516187016898 287 1924760927594269 288 2068822655776189 289 2223401678394838 290 2389246976971376 291 2567159612067467 292 2757996206696676 293 2962672711375459 294 3182168400557322 295 3417530218622391 296 3669877208407927 297 3940405498528306 298 4230393399688827 299 4541206936080375 300 4874305711858857 301 5231249237392546 302 5613703452241843 303 6023448000656032 304 6462383672759700 305 6932540503352917 306 7436086345579818 307 7975336064181064 308 8552761105709144 309 9171000072856300 310 9832869565678848 311 10541375998825998 312 11299728081896425 313 12111350155272028 314 12979896175226649 315 13909265031654423 316 14903616307758766 317 15967387462318622 318 17105311931889662 319 18322438439681339 320 19624151350611449 321 21016192794921992 322 22504685522895578 323 24096157800415565 324 25797569582161418 325 27616340409845754 326 29560378925079678 327 31638114736279460 328 33858531479321050 329 36231202766224788 330 38766329916945494 331 41474782177308554 332 44368139352593404 333 47458737593167442 334 50759717092630626 335 54285073827227925 336 58049713802661303 337 62069510893816214 338 66361368216123916 339 70943283754155232 340 75834418989928915 341 81055173137435741 342 86627260930940250 343 92573795600643526 344 98919376926008872 345 105690185091424216 346 112914079154731337 347 120620703241304601 348 128841597813341641 349 137610318400129311 350 146962561540176407 351 156936298704126348 352 167571917183533640 353 178912371575480713 354 191003342558711757 355 203893406343504208 356 217634214277377975 357 232280683518190420 358 247891198052252338 359 264527824210363600 360 282256536693206491 361 301147459777308272 362 321275122740177821 363 342718730731148181 364 365562450791226506 365 389895717682990680 366 415813554891823348 367 443416917083354395 368 472813052400395255 369 504115886411820969 370 537446427973086092 371 572933202160089021 372 610712705088024636 373 650929888880042817 374 693738674262517327 375 739302493591784736 376 787794865242911556 377 839400005034979394 378 894313469153697528 379 952742839214715505 380 1014908445763498168 381 1081044134584829467 382 1151398077503864667 383 1226233633933432116 384 1305830257597562939 385 1390484461873742852 386 1480510838608352017 387 1576243137115380452 388 1678035405835501765 389 1786263203649306321 390 1901324875709353320 391 2023642910487485970 392 2153665371219920414 393 2291867411825800319 394 2438752880540919042 395 2594856019329444186 396 2760743255002732128 397 2937015102485578568 398 3124308171606985671 399 3323297292176530581 400 3534697761249058963 401 3759267722285260003 402 3997810674031018777 403 4251178133834018736 404 4520272445013469560 405 4806049749381725918 406 5109523129313213329 407 5431765931642130682 408 5773915274158756005 409 6137175764316269807 410 6522823418322020547 411 6932209810091132886 412 7366766454728514451 413 7828009442832764770 414 8317544330621778144 415 8837071321169521009 416 9388390724178348283 417 9973408734662815401 418 10594143535234284500 419 11252731744418536581 420 11951435221792556068 421 12692648271933184056 422 13478905235125421762 423 14312888519112695711 424 15197437076471069304 425 16135555359174500843 426 17130422768812457450 427 18185403652584789431 428 19304057835553494010 429 20490151761000865766 430 21747670243425952144 431 23080828879077013507 432 24494087142378468476 433 25992162228608832035 434 27580043638827999217 435 29263008600876241873 436 31046638331430629327 437 32936835203025651023 438 34939840856989964725 439 37062255335930615247 440 39311057241572989554 441 41693625039069180399 442 44217759514489612822 443 46891707475964587537 444 49724186755317691649 445 52724412601569930993 446 55902125487857545673 447 59267620486662381228 448 62831778224289874227 449 66606097541521179757 450 70602729937306412613 451 74834515911120538863 452 79315023249240699290 453 84058587451743429031 454 89080354319606148815 455 94396324878211016682 456 100023402739402649983 457 105979444051320334768 458 112283310115613010725 459 118954922920868794602 460 126015323627035694427 461 133486734243012977854 462 141392622631886410196 463 149757771039813436168 464 158608348276486094996 465 167971985861061320733 466 177877858194340759101 467 188356767086383345836 468 199441230815833742928 469 211165577982239351235 470 223566046345773338101 471 236680887050274120250 472 250550474332098544514 473 265217421157897300352 474 280726701022453975870 475 297125776258660731969 476 314464733144066417605 477 332796424304320932656 478 352176618580465932356 479 372664158951135874673 480 394321128814067975192 481 417213027104500637787 482 441408952655423532545 483 466981798434298668777 484 494008455919639666395 485 522570030399864486965 486 552752067597743118077 487 584644792270514219535 488 618343359350533764021 489 653948118435652067306 490 691564892033502616648 491 731305268588575956291 492 773286910830541484757 493 817633880329222594266 494 864476979032046744519 495 913954108822164183901 496 966210649702841084564 497 1021399857953804782955 498 1079683284984095836445 499 1141231218085366093356 500 1206223144139026312505 501 1274848237618026739448 502 1347305873772249383742 503 1423806168750207903862 504 1504570547638730603279 505 1589832342053103532465 506 1679837418695469374460 507 1774844840624616342428 508 1875127562519128572224 509 1980973162209867039058 510 2092684609819350437364 511 2210581076713159618812 512 2334998786159615150045 513 2466291907978009213211 514 2604833498995971857114 515 2751016492265785236233 516 2905254736869380209114 517 3067984091278014896059 518 3239663572791859495303 519 3420776566058162715808 520 3611832093219888366892 521 3813366149514313695649 522 4025943106830210409904 523 4250157189195677830648 524 4486634023549719570117 525 4736032269758335725949 526 4999045333411458018069 527 5276403166346119626457 528 5568874158337343585492 529 5877267125253478233748 530 6202433398121133772875 531 6545269018347949613036 532 6906717043956324141923 533 7287769973235400450178 534 7689472290529081403886 535 8112923141194865773773 536 8559279141621987355898 537 9029757331277834695038 538 9525638273387702009642 539 10048269312558891566666 540 10599067995804917702598 541 11179525666278742830294 542 11791211237514496125054 543 12435775157442178333322 544 13114953571100714907737 545 13830572692847137840585 546 14584553396872093232859 547 15378916038300108544080 548 16215785515207881006536 549 17097396583879858163740 550 18026099439289793064545 551 19004365574861535074060 552 20034793933493991839144 553 21120117366000021968341 554 22263209410655476854108 555 23467091410232375280948 556 24734939982538253708140 557 26070094862785659359259 558 27476067134037313601329 559 28956547866918314738918 560 30515417186757611287820 561 32156753789899926248442 562 33884844930510686987046 563 35704196901808297668534 564 37619546033661831970758 565 39635870234307687182933 566 41758401100277709584111 567 43992636623365968447420 568 46344354522912219660804 569 48819626234713426443644 570 51424831586076674820932 571 54166674193305087264827 572 57052197613580965942869 573 60088802289404274771291 574 63284263322982338692427 575 66646749121586090680933 576 70184840953429227921072 577 73907553461470353071271 578 77824356177542066942755 579 81945196087222480143584 580 86280521294788716905508 581 90841305842032019225363 582 95639075733760834903861 583 100685936231846178537378 584 105994600474041720428544 585 111578419484060875538393 586 117451413637886473299169 587 123628305656875219596328 588 130124555197965105808646 589 136956395121650077953839 590 144140869512246205018659 591 151695873537948254338597 592 159640195236113946688398 593 167993559316387086882531 594 176776673074936699398341 595 186011274524959983069040 596 195720182842128072039763 597 205927351239916436812873 598 216657922387023142054595 599 227938286488424452287404 600 239796142153453601335077 601 252260560187922877441770 602 265362050440808026354622 603 279132631856214508994999 604 293605905877826392025638 605 308817133365323128709224 606 324803315185536440805352 607 341603276656861158432890 608 359257756019331683886291 609 377809497127661192733352 610 397303346560186489757073 611 417786355352866306952527 612 439307885572537558664213 613 461919721961960370210394 614 485676188884077182609675 615 510634272823347623098813 616 536853750696855239658205 617 564397324249257079714672 618 593330760812837917412173 619 623723040735507958022731 620 655646511776276824035142 621 689177050804732393790964 622 724394233135229809656955 623 761381509854610705937940 624 800226393512024021146867 625 841020652565173119488196 626 883860514976857802659806 627 928846881400423296187905 628 976085548386593937753689 629 1025687442080976973000914 630 1077768862894351167155864 631 1132451741659055110559618 632 1189863907788538227161002 633 1250139370011044700114808 634 1313418610242577572898052 635 1379848891212204912135490 636 1449584578469322366495731 637 1522787477440866329976271 638 1599627186216141430398268 639 1680281464801713693561293 640 1764936621584311082111703 641 1853787917801660863215906 642 1947039990842302383024668 643 2044907297243309029328917 644 2147614576272601620375491 645 2255397335060315347534232 646 2368502356242002613015335 647 2487188229156141852912291 648 2611725905665198062131281 649 2742399281730002701744030 650 2879505805895744563426939 651 3023357115941269175286396 652 3174279704946734946052234 653 3332615618136484268085829 654 3498723181887935320570640 655 3672977766374558526125144 656 3855772583353649374058836 657 4047519520721976999116487 658 4248650015473859148116875 659 4459615966825533605071738 660 4680890691312883174331447 661 4912969921768939959919236 662 5156372852148520792723621 663 5411643230302942146632965 664 5679350500831595458574776 665 5960091000300553093735088 666 6254489207173660713638499 667 6563199048930017458961447 668 6886905268926107283302185 669 7226324855725169702950528 670 7582208537658310684681033 671 7955342345587309809314183 672 8346549246910418568493151 673 8756690854018931723735144 674 9186669210526520573313096 675 9637428658793509897521870 676 10109957792335855191248769 677 10605291496965879374180724 678 11124513084604666478355878 679 11668756523921999358350956 680 12239208772111772345457488 681 12837112212356159282465542 682 13463767201635002365289007 683 14120534733858032064269364 684 14808839223419335353242207 685 15530171414553540967846641 686 16286091422073085044944842 687 17078231909368525050803113 688 17908301409705586160941195 689 18778087797252383967305739 690 19689461914431214947486328 691 20644381362551829783027399 692 21644894462943447803231917 693 22693144396178389707082042 694 23791373527197099595214051 695 24941927924640985154948515 696 26147262082913338490472259 697 27409943855956780812510107 698 28732659612072393857218195 699 30118219619574832257770506 700 31569563673381087795498467 701 33089766973246870348251421 702 34682046264649730610843103 703 36349766253920983935569682 704 38096446309661832508899515 705 39925767463068308483142724 706 41841579720206673753788898 707 43847909700045239571662405 708 45948968612429620028058653 709 48149160590962542154181273 710 50453091396305118598363198 711 52865577506160200582431525 712 55391655608763524285116740 713 58036592517656369131226385 714 60805895526022866880897560 715 63705323219865897888426128 716 66740896770006809325398971 717 69918911723836733889562599 718 73245950318504053099508549 719 76728894338399142258727024 720 80374938540477989736958645 721 84191604672230573400916394 722 88186756108009162668506019 723 92368613130630077170278925 724 96745768886165918760433814 725 101327206041307233039190049 726 106122314173579775777581796 727 111140907926312179624603570 728 116393245961410747535151085 729 121890050744525276837063360 730 127642529198509444595775978 731 133662394262898532677973017 732 139961887398333596588291226 733 146553802076902491404264227 734 153451508300853152004480165 735 160668978194083733612981195 736 168220812712537470289216387 737 176122269521898061909745796 738 184389292092580312046037263 739 193038540064594951696779397 740 202087420936765385175892004 741 211554123137263991056167276 742 221457650534672728734157315 743 231817858451605695477852405 744 242655491245043018235208016 745 253992221520790139331164289 746 265850691051906162713200010 747 278254553474126154222191097 748 291228518834192172989284918 749 304798400070553618222199186 750 318991161508676057494324643 751 333834969457314713997383956 752 349359244995219854402325930 753 365594719041804656829178195 754 382573489809023874708838959 755 400329082736158725350834871 756 418896513012845467165250026 757 438312350800869401519086670 758 458614789269232376815988828 759 479843715562188383038549954 760 502040784824708220611849987 761 525249497415422457684092176 762 549515279441847594878479350 763 574885566759220939743157449 764 601409892579380313075993870 765 629139978842738376025964101 766 658129831512495068266411612 767 688435839957266081545206467 768 720116880594492230642928535 769 753234424975188701898009197 770 787852652497147337375229989 771 824038567942128713599389056 772 861862124040353525384730098 773 901396349274471261201703145 774 942717481143204465013832065 775 985905105115157581096212077 776 1031042299511685843077912839 777 1078215786568434397844525574 778 1127516089935054014078775780 779 1179037698883794676228316374 780 1232879239508040313912068635 781 1289143653204766437390357627 782 1347938382745683361522820574 783 1409375566255437850728669704 784 1473572239427827067764116743 785 1540650546325124660563483649 786 1610737959118963762742503458 787 1683967507147435659988884942 788 1760478015676883959941157721 789 1840414354774137842133191082 790 1923927698710903553830452154 791 2011175796339921308699521370 792 2102323252899630834273992015 793 2197541823724437841493884524 794 2297010720355382063627748262 795 2400916929567875288342655608 796 2509455545853445020736197348 797 2622830117915049913383444057 798 2741253009757477657445207894 799 2864945776979876369747483285 800 2994139558900142001502333276 801 3129075487168546945733828579 802 3270005111553687748160851482 803 3417190843612466538038756708 804 3570906418983853165005468703 805 3731437379078235971385001376 806 3899081572963167434768433340 807 4074149680281259804247813914 808 4256965756068536988951484594 809 4447867798377785909422718728 810 4647208339647178365188538316 811 4855355062794689075569418577 812 5072691443055886167719425434 813 5299617416626772571980188148 814 5536550077214576511963055377 815 5783924401645234390711187950 816 6042194005721751804433116062 817 6311831931578182150344148009 818 6593331467821244899571285842 819 6887207003807197897059097635 820 7193994919453751974467835578 821 7514254512044795671434270178 822 7848568961543389284305747432 823 8197546335991989537207469816 824 8561820638639129718641214588 825 8942052898501786702593005073 826 9338932306138678571324335636 827 9753177396483024939902218896 828 10185537280656422341588837437 829 10636792928765269622162378997 830 11107758505757884604123732211 831 11599282762508532766283555837 832 12112250484378076273114180282 833 12647583999593533513088724935 834 13206244749881376586162395574 835 13789234925889646341450126813 836 14397599170031467462723888427 837 15032426349493275207247895823 838 15694851402256610851020175013 839 16386057259099214371816407640 840 17107276844658097223098572483 841 17859795160763263356444547252 842 18644951455374514679889390247 843 19464141480592880444910817222 844 20318819843351582391957729837 845 21210502452538867303176780059 846 22140769066452676416481862544 847 23111265944645448817935575713 848 24123708608374250157173691219 849 25179884714046054514027899569 850 26281657044216462711162671952 851 27430966620885941707436105122 852 28629835946023841786147469283 853 29880372374449411297683477806 854 31184771624397648308954534434 855 32545321431316949249392451835 856 33964405350658171626329208097 857 35444506715648706466320427516 858 36988212756279694522710649933 859 38598218885984516731386846159 860 40277333162737801493146483596 861 42028480931578985877739585293 862 43854709655832773602493441420 863 45759193944593229392521340472 864 47745240784333462352088394141 865 49816294982816907820685331197 866 51975944833803291832227495339 867 54227928011386814448801372253 868 56576137703142400145945828264 869 59024628991625964158430325532 870 61577625494145933201337172589 871 64239526271117683740892722732 872 67014913013712436130794128183 873 69908557521943723452527861456 874 72925429484760862031646467017 875 76070704574183731104604171292 876 79349772865979799298537146406 877 82768247599879525783476057558 878 86331974292829971838992293424 879 90047040219326987099967206920 880 93919784273403159503975001349 881 97956807227432169886076498545 882 102164982403496246147260142927 883 106551466773684860259898741147 884 111123712506326605315893453816 885 115889478975832906657933303323 886 120856845254507728193489722114 887 126034223105409114745771164525 888 131430370496083981331014037296 889 137054405653777101502902513743 890 142915821683511876380796885929 891 149024501771287364127414763437 892 155390734995485433205171397604 893 162025232770498757827435459665 894 168939145947513040188566055636 895 176144082598354201402893382290 896 183652126509311576383154786482 897 191475856412907627235146841606 898 199628365986651887707106907167 899 208123284648964889666164757891 900 216974799183614488828513630599 901 226197676225231708685693013570 902 235807285639728048991802758564 903 245819624834761125121458548603 904 256251344036735324493085475694 905 267119772572260650226429760376 906 278442946193442095131707992282 907 290239635487905641705764909336 908 302529375416039692907110649868 909 315332496019586962896881808521 910 328670154347402608981354918601 911 342564367645990550934046145377 912 357038047864244537536280110383 913 372115037523740147074631920946 914 387820147007893341425880662192 915 404179193325370744467670136461 916 421219040405243572262572904275 917 438967640983621565314507210620 918 457454080143774189145692539359 919 476708620574147446780094867626 920 496762749611148878182544389545 921 517649228136158285363973326073 922 539402141398860350803741593864 923 562056951841798086179979782045 924 585650554003886389435340828606 925 610221331583626340847575922782 926 635809216745841834349939875041 927 662455751758987497911930882034 928 690204153053379008419383573438 929 719099377794194782726973843799 930 749188193066648538466029638768 931 780519247774481477337746755666 932 813143147356772066050330477356 933 847112531432088994225776381529 934 882482154483142160334826764351 935 919308969699449334408536504446 936 957652216099971827181956315450 937 997573509062352965137632700477 938 1039136934390198841479974000608 939 1082409146054864772463711090442 940 1127459467753370440453642017188 941 1174359998429505181782920681871 942 1223185721910723169435994798055 943 1274014620819267376937729523685 944 1326927794921956941196870692985 945 1382009584089336341335665999327 946 1439347696041326769228453537105 947 1499033339063295668965477492861 948 1561161359883371327287728002790 949 1625830386909109273080979676918 950 1693142979029092881270640215763 951 1763205780192856333355769792741 952 1836129679990555150833699102193 953 1912029980462246411143015813403 954 1991026569375259318023503499202 955 2073244100217207015888408119538 956 2158812179161505504509479477387 957 2247865559271987862389860247027 958 2340544342223221743062242057040 959 2436994187823638029801026966275 960 2537366531639320238614755745264 961 2641818811027597870008692211228 962 2750514699901186674725999662572 963 2863624352555722022439172565268 964 2981324656906014136639252425107 965 3103799497489414523692913683581 966 3231240028608062674479848849780 967 3363844957995835243150410078997 968 3501820841410256287622122238104 969 3645382388564686262098376185240 970 3794752780831647263149481265780 971 3950164001164379303405824177496 972 4111857176700377888308302194975 973 4280082934528139180076110229730 974 4455101771116295214374344079828 975 4637184435923048344710815940524 976 4826612329723146641303722893473 977 5023677918209818266111498583850 978 5228685161449803393472255393156 979 5441949959791341511562586393957 980 5663800616847293293327397772797 981 5894578320198850946465061977662 982 6134637640489325818159379928619 983 6384347049602560139006599214471 984 6644089458646271700711715497133 985 6914262776487616796376820632494 986 7195280489615988764018987550559 987 7487572264136980633797435655600 988 7791584570731301792492310019065 989 8107781333443543884016941215669 990 8436644603197701351109151119731 991 8778675256969838531261985621374 992 9134393723582730154435431393002 993 9504340737123194501194928383801 994 9889078119019915247815799263489 995 10289189589858140291530594727124 996 10705281612047395394944313456712 997 11137984264499893765363912879876 998 11587952150520056956227242132359 999 12055865340150096772425425040469 1000 12542430348262614730337883565337