0 0 1 0 2 0 3 0 4 1 5 2 6 3 7 7 8 10 9 16 10 23 11 35 12 47 13 70 14 93 15 126 16 169 17 228 18 294 19 391 20 501 21 648 22 827 23 1057 24 1329 25 1683 26 2105 27 2631 28 3266 29 4056 30 4992 31 6156 32 7538 33 9221 34 11234 35 13664 36 16549 37 20033 38 24152 39 29077 40 34904 41 41844 42 50012 43 59710 44 71100 45 84541 46 100318 47 118869 48 140552 49 165998 50 195670 51 230346 52 270719 53 317767 54 372389 55 435894 56 509471 57 594765 58 693407 59 807487 60 939109 61 1091039 62 1265998 63 1467454 64 1699062 65 1965226 66 2270612 67 2620939 68 3022187 69 3481592 70 4006936 71 4607382 72 5292834 73 6075028 74 6966569 75 7982219 76 9138177 77 10453050 78 11947289 79 13644510 80 15570525 81 17754991 82 20230633 83 23034617 84 26208059 85 29797729 86 33855197 87 38438853 88 43613491 89 49452009 90 56035252 91 63454293 92 71809922 93 81215326 94 91796197 95 103693027 96 117061856 97 132077141 98 148932238 99 167842960 100 189048880 101 212816618 102 239441975 103 269254139 104 302617855 105 339938409 106 381665205 107 428296515 108 480384544 109 538541503 110 603444924 111 675845157 112 756572811 113 846546314 114 946781697 115 1058402005 116 1182648417 117 1320891564 118 1474646004 119 1645582331 120 1835545358 121 2046569230 122 2280898050 123 2541004343 124 2829615101 125 3149732006 126 3504663489 127 3898049704 128 4333899536 129 4816620946 130 5351066288 131 5942566817 132 6596987618 133 7320769755 134 8120994050 135 9005431985 136 9982623077 137 11061933454 138 12253648545 139 13569044487 140 15020495876 141 16621561901 142 18387115248 143 20333442567 144 22478398186 145 24841525111 146 27444234268 147 30309949707 148 33464321856 149 36935397806 150 40753873549 151 44953298656 152 49570370463 153 54645178569 154 60221552854 155 66347350899 156 73074868525 157 80461182896 158 88568631321 159 97465219847 160 107225187178 161 117929485488 162 129666442921 163 142532335314 164 156632158949 165 172080308239 166 189001482999 167 207531485338 168 227818283074 169 250022953444 170 274320921815 171 300903077184 172 329977222523 173 361769384676 174 396525510162 175 434513010560 176 476022737054 177 521370800453 178 570900877318 179 624986344321 180 684032968795 181 748481418699 182 818810391443 183 895539561543 184 979233227918 185 1070503763036 186 1170015860386 187 1278490578391 188 1396710274804 189 1525523342302 190 1665849948739 191 1818687568404 192 1985117654959 193 2166312108682 194 2363541018733 195 2578180216978 196 2811720269935 197 3065775282983 198 3342093335737 199 3642566750698 200 3969244185538 201 4324342598202 202 4710261266783 203 5129595708073 204 5585153923047 205 6079972591128 206 6617335870843 207 7200794227051 208 7834186194908 209 8521660237914 210 9267699926853 211 10077149317693 212 10955242052177 213 11907630799170 214 12940420890600 215 14060204437571 216 15274099187989 217 16589788053954 218 18015563961610 219 19560375617371 220 21233879271280 221 23046491653954 222 25009449687995 223 27134871704469 224 29435826271892 225 31926402940309 226 34621791566739 227 37538364000510 228 40693765461308 229 44107008828157 230 47798579829346 231 51790545814673 232 56106676818213 233 60772570941916 234 65815793620222 235 71266022100461 236 77155205549494 237 83517731443890 238 90390609585321 239 97813663593730 240 105829742305139 241 114484940069053 242 123828839467699 243 133914764613976 244 144800059747206 245 156546380292557 246 169220012493280 247 182892207728027 248 197639549034796 249 213544334918254 250 230694999502029 251 249186552900705 252 269121062640632 253 290608158724850 254 313765584988738 255 338719778078649 256 365606498682043 257 394571494882086 258 425771224528141 259 459373614953330 260 495558889264924 261 534520436014496 262 576465754019067 263 621617447400007 264 670214305497772 265 722512440886930 266 778786523157827 267 839331079868733 268 904461905608639 269 974517548512357 270 1049860918862157 271 1130880986952644 272 1217994618717400 273 1311648514152761 274 1412321301251506 275 1520525748076494 276 1636811150421403 277 1761765855168084 278 1896019981772421 279 2040248299512784 280 2195173328357804 281 2361568618331653 282 2540262281307101 283 2732140727241283 284 2938152685209623 285 3159313458446781 286 3396709500759357 287 3651503260426736 288 3924938386770535 289 4218345242321662 290 4533146824072023 291 4870865033664044 292 5233127409058462 293 5621674254172974 294 6038366289114359 295 6485192754076292 296 6964280100287106 297 7477901197827049 298 8028485205444758 299 8618628028698382 300 9251103524587372 301 9928875375514257 302 10655109804715522 303 11433189052794797 304 12266725802756145 305 13159578469782090 306 14115867560079371 307 15139993011774358 308 16236652740380277 309 17410862298993347 310 18667975895632196 311 20013708675018426 312 21454160529235472 313 22995841342005582 314 24645697954798559 315 26411142757637511 316 28300084218827341 317 30320959254769533 318 32482767782870727 319 34795109357609919 320 37268222263919819 321 39913024967895720 322 42741160333104480 323 45765042502986708 324 48997906895344478 325 52453863210907433 326 56147951942931379 327 60096204292906090 328 64315706024226063 329 68824665163046379 330 73642484127799949 331 78789836202430972 332 84288746988827028 333 90162680761687491 334 96436632420588689 335 103137224972529303 336 110292813305213754 337 117933594197020616 338 126091723395377578 339 134801439725637787 340 144099197140670789 341 154023804692446490 342 164616575422553636 343 175921484176115746 344 187985335430865089 345 200857941174078727 346 214592310023409030 347 229244847657299688 348 244875569866217174 349 261548328329335223 350 279331050554085150 351 298295994129501570 352 318520016869635358 353 340084863051428413 354 363077467476772498 355 387590277625366523 356 413721595796449202 357 441575941578758123 358 471264436732228712 359 502905212904183438 360 536623844468439547 361 572553807006181935 362 610836963942175425 363 651624081966272307 364 695075378001948244 365 741361098478456871 366 790662133942642054 367 843170669911869851 368 899090877305852954 369 958639643524959534 370 1022047347845570978 371 1089558682388625919 372 1161433522699791091 373 1237947849411883506 374 1319394725433095189 375 1406085330376092478 376 1498350057118584734 377 1596539672486830242 378 1701026547446937209 379 1812205959108522878 380 1930497470470298934 381 2056346390567242308 382 2190225321550299353 383 2332635795758609569 384 2484110009980151809 385 2645212660412637340 386 2816542886253932745 387 2998736325944308024 388 3192467294799729943 389 3398451088632515269 390 3617446422994192249 391 3850258013282924443 392 4097739306338634167 393 4360795369495688870 394 4640385948808081151 395 4937528703233259437 396 5253302627696872016 397 5588851672740978943 398 5945388575010824635 399 6324198907311973909 400 6726645363965542767 401 7154172291345966033 402 7608310480957510338 403 8090682236225260163 404 8603006732155052157 405 9147105680485036881 406 9724909321470523074 407 10338462756542479189 408 10989932645178653612 409 11681614282036611824 410 12415939080114546408 411 13195482478012244144 412 14022972299739967045 413 14901297587405989770 414 15833517938195803002 415 16822873368494960113 416 17872794739843986207 417 18986914772392185365 418 20169079684158295446 419 21423361484902809115 420 22754070966921234135 421 24165771425061293845 422 25663293152693326037 423 27251748749836611568 424 28936549295054831014 425 30723421421665312243 426 32618425355273504012 427 34627973958011415946 428 36758852842454197115 429 39018241605975285466 430 41413736255102089112 431 43953372876617855406 432 46645652632251600588 433 49499568140357503759 434 52524631329466039572 435 55730902834509013553 436 59129023029482443118 437 62730244775571503014 438 66546467988313966455 439 70590276111959771490 440 74874974615438888193 441 79414631608239678316 442 84224120702576878846 443 89319166231410891601 444 94716390961915048888 445 100433366426447601807 446 106488666025218120329 447 112901921036569468623 448 119693879705177456758 449 126886469559463586145 450 134502863146314021486 451 142567547351446026732 452 151106396513152649470 453 160146749516663125641 454 169717491098526140180 455 179849137569189768740 456 190573927207112332662 457 201925915555770725383 458 213941075903303933294 459 226657405201846608002 460 240115035735426075423 461 254356352821916702153 462 269426118890075313075 463 285371604248630436867 464 302242724923916201809 465 320092187917861415071 466 338975644301949291009 467 358951850537497680756 468 380082838481033017836 469 402434094507734293164 470 426074748259315175805 471 451077771496459766507 472 477520187614665156378 473 505483292355716796027 474 535052886331524454009 475 566319519950140525646 476 599378751424491576186 477 634331418517292353830 478 671283924773006779324 479 710348540960637266882 480 751643722555733895943 481 795294444063065273932 482 841432551093780969577 483 890197131084269562253 484 941734903664690808530 485 996200631659066874542 486 1053757553828649448810 487 1114577840444956065960 488 1178843072918474786517 489 1246744748684766721666 490 1318484812699851226221 491 1394276216873854535705 492 1474343508933460713898 493 1558923452182517925520 494 1648265677804028353945 495 1742633371327694675320 496 1842303995074378933617 497 1947570048372358470851 498 2058739867541842375809 499 2176138467630835025966 500 2300108428102576938380 501 2431010824665098599316 502 2569226209667398947681 503 2715155643481395664705 504 2869221779540993472559 505 3031870005709306652316 506 3203569644916991896192 507 3384815218020218555772 508 3576127772120068957926 509 3778056277597523936798 510 3991179097434581193575 511 4216105532412222994236 512 4453477446117390752060 513 4703970973720247647586 514 4968298318851586813776 515 5247209642949585844057 516 5541495051843105148354 517 5851986684389696138808 518 6179560908416372418267 519 6525140629275371334957 520 6889697716791594031058 521 7274255556457532579736 522 7679891731233463576435 523 8107740840406683494692 524 8558997462506220260539 525 9034919269384485291529 526 9536830299164132811688 527 10066124395884832563480 528 10624268824319386202107 529 11212808068589094379783 530 11833367823895022141280 531 12487659190869252720364 532 13177483082793429615083 533 13904734856149516217240 534 14671409175772248567420 535 15479605126124129757142 536 16331531581084977460068 537 17229512844937102820893 538 18175994578170722845175 539 19173550022065311643229 540 20224886537024756231545 541 21332852470022109925006 542 22500444367617347212145 543 23730814551441578316123 544 25027279074241657824465 545 26393326075067128746513 546 27832624553482882924952 547 29349033583243292252102 548 30946611987274766342148 549 32629628496437520456669 550 34402572416067877083297 551 36270164825005489114202 552 38237370333470205393744 553 40309409426944157509312 554 42491771425016138602270 555 44790228085033434657483 556 47210847882361292931651 557 49760011000045888340781 558 52444425062798709143827 559 55271141651334920509743 560 58247573635402047409458 561 61381513365081441399796 562 64681151762446491563716 563 68155098357052881285763 564 71812402311452847265898 565 75662574484477026877385 566 79715610582978274055478 567 83982015454460311724024 568 88472828576219689111157 569 93199650798553014492363 570 98174672403064383302011 571 103410702539246345428517 572 108921200106292583868943 573 114720306149475683376788 574 120822877844536786788870 575 127244524146169864599683 576 134001643181154461005490 577 141111461469613655528264 578 148592075062734536833373 579 156462492688527077646369 580 164742681002481796636746 581 173453612043572386261555 582 182617313001795555491773 583 192256918407407797803746 584 202396724858267398937978 585 213062248406076899145039 586 224280284729116965228335 587 236078972223910279182113 588 248487858155645539739972 589 261537968012545271996934 590 275261878217401292339324 591 289693792355410705314825 592 304869621086191735647601 593 320827065914377252226591 594 337605707002699319816134 595 355247095218665332666617 596 373794848616279145876249 597 393294753562181202060703 598 413794870726846286612065 599 435345646170202178930928 600 458000027763289917259959 601 481813587197192319662539 602 506844647843795873125023 603 533154418743522753473432 604 560807135009685243038923 605 589870204950744395120040 606 620414364227551906814331 607 652513837375442366834630 608 686246507038235572026317 609 721694091275265434126147 610 758942329321263807475983 611 798081176194373082965780 612 839205006567927357894714 613 882412828338607236689437 614 927808506345740202331823 615 975500996715146543273479 616 1025604592325058338946151 617 1078239179912085935927018 618 1133530509361468360115413 619 1191610475748280195980823 620 1252617414724853134255175 621 1316696411874281422643624 622 1383999626680995595896349 623 1454686631796377441410460 624 1528924768311257759502965 625 1606889517776725513395593 626 1688764891751542691061119 627 1774743839686885605354560 628 1865028675999261269984891 629 1959831527217975852924732 630 2059374800137210699481263 631 2163891671941677933401580 632 2273626603322370380346928 633 2388835875641537174633140 634 2509788153257764533179008 635 2636765072168697770882857 636 2770061856185265221010998 637 2909987961902331545583245 638 3056867753792012492055867 639 3211041210801763591127238 640 3372864665906078608542598 641 3542711580121766933603929 642 3720973352569398300145918 643 3908060168230367922372515 644 4104401885128068980642147 645 4310448962734776347681040 646 4526673433491857872697500 647 4753569919410865887694598 648 4991656695816665708334901 649 5241476804381130950036365 650 5503599217697797677786029 651 5778620057743351105170096 652 6067163870682663137196843 653 6369884960578420611544631 654 6687468784686998295953381 655 7020633413136187731971543 656 7370131055911632326051754 657 7736749660203277263083227 658 8121314581305936804652951 659 8524690330403982515633649 660 8947782402725514719745234 661 9391539189699747477933584 662 9856953978920358302578174 663 10345067045879502776267670 664 10856967841621069458664958 665 11393797280638491679005795 666 11956750133542457386168080 667 12547077529216708682299781 668 13166089571397703245494288 669 13815158074824301375762291 670 14495719426340306690893413 671 15209277576562177501054407 672 15957407167981633066578598 673 16741756805623157006882380 674 17564052476656351864933644 675 18426101125636004385400869 676 19329794392347173605001845 677 20277112519530144561871804 678 21270128438091167795985434 679 22311012037729231098993472 680 23402034631269118030888377 681 24545573621344487572080995 682 25744117378466151086786152 683 27000270339895917535140489 684 28316758339171970432902799 685 29696434176551431633288751 686 31142283441098459194046222 687 32657430595603436241926438 688 34245145336021799782819858 689 35908849237619066850772279 690 37652122700555380115554210 691 39478712208185264350874046 692 41392537911942590822274078 693 43397701557271343985770672 694 45498494765708719851226467 695 47699407688870108695411854 696 50005138050787514557027311 697 52420600595752969713822298 698 54950936959581378389044413 699 57601525982969157311007479 700 60377994486454012025039959 701 63286228527310415221597911 702 66332385159616080366812583 703 69522904719627068066890159 704 72864523659577784185591084 705 76364287954003907192973761 706 80029567103749455274460241 707 83868068763887269979415890 708 87887854022937135949024867 709 92097353361927544355596203 710 96505383323101646295701984 711 101121163919331515472261209 712 105954336816667458374588182 713 111014984323823212753347287 714 116313649223877771775279735 715 121861355484968685684026540 716 127669629888358836526317124 717 133750524613883089436160850 718 140116640824526420031655574 719 146781153293650965966695948 720 153757836120284409251444016 721 161061089579801469023711081 722 168705968159387695310855848 723 176708209829760750621460828 724 185084266606857979367849502 725 193851336459465881616834634 726 203027396621191820904613263 727 212631238367641318291438950 728 222682503322296237984911439 729 233201721357265070905870650 730 244210350157933199466604406 731 255730816523447871855237238 732 267786559478072953081451898 733 280402075271605881437898088 734 293602964350413772031341027 735 307415980384074690141900840 736 321869081436261018528560650 737 336991483372225611503263955 738 352813715599212774447437666 739 369367679240159440534252590 740 386686707845349755102255483 741 404805630751076117626436373 742 423760839199022265698445332 743 443590355334849507249113161 744 464333904209524970923192875 745 486032988912103540534893868 746 508730968968161186027005912 747 532473142143691678549125781 748 557306829800228785130423696 749 583281465953048823531290615 750 610448690190761352202231451 751 638862444621207151346145083 752 668579075015580242670181185 753 699657436329864062162937608 754 732159002790259543475057557 755 766147982737065183274563697 756 801691438429695931979115136 757 838859411023969836244901552 758 877725050941710361360313464 759 918364753861869169493713294 760 960858302572042810826325397 761 1005289014929187903734819380 762 1051743898188819890003288094 763 1100313809972750222831139170 764 1151093626156776412084057090 765 1204182415971417425254657691 766 1259683624621098281644991894 767 1317705263739849395809715544 768 1378360110014927982231113353 769 1441765912323495688963765510 770 1508045607741943850769309330 771 1577327546802337883114315078 772 1649745728386116997181255405 773 1725440044661314138513155664 774 1804556536486532590030593032 775 1887247659722396064806533150 776 1973672562909575047615834502 777 2063997376791435637145592389 778 2158395516179273704300064081 779 2257047994678624274935363067 780 2360143752816708888430389848 781 2467880000133324636601113305 782 2580462571820843526531795547 783 2698106300523086432941632037 784 2821035403928139734314304575 785 2949483888816285216719842615 786 3083695972251615192688707865 787 3223926520634178635418654310 788 3370441507359174466971682843 789 3523518489860331126525308111 790 3683447106846736109448895596 791 3850529596575543392268967045 792 4025081337037765609115738462 793 4207431408970270877313336446 794 4397923182644753756263647051 795 4596914929423335930208487734 796 4804780459111206042851581039 797 5021909784178809577883850484 798 5248709811970210122105582526 799 5485605066059821902869783278 800 5733038437967453114883196069 801 5991471970490937906330836194 802 6261387673967298090954183081 803 6543288376826779157246736625 804 6837698611860009847353364535 805 7145165539676333006034179974 806 7466259910891844931590435273 807 7801577068648229934189080733 808 8151737993128921886228952009 809 8517390389806809614503187249 810 8899209823228503874940028413 811 9297900898213419510636113403 812 9714198490422515228852000959 813 10148869028330768356488550798 814 10602711828720305212394307052 815 11076560487896825652422523079 816 11571284330921561628063361168 817 12087789921243732895462479679 818 12627022633215365829748596528 819 13189968290070633824843007313 820 13777654870056668727598408700 821 14391154283511263070339042470 822 15031584223796195060292146611 823 15700110095112213152405106268 824 16397947020344233612317467822 825 17126361932212152624439304382 826 17886675751135132615879890727 827 18680265653354378639421304264 828 19508567433002615655398767048 829 20373077961956766871607223428 830 21275357751465123248338564213 831 22217033619700606940755633990 832 23199801469559042020630753387 833 24225429181194642164560481419 834 25295759623965754708154944065 835 26412713792651216404169157998 836 27578294072993102100804234476 837 28794587641824100443331444001 838 30063770007248934354798438461 839 31388108694568038994669245779 840 32769967083859904063784141393 841 34211808405374923974370455744 842 35716199899140155016245481074 843 37285817145429858512986206246 844 38923448573023082710780681191 845 40632000152445570444875173797 846 42414500281681042139242224288 847 44274104872135121851245486287 848 46214102642946018688037783739 849 48237920632058234643668938869 850 50349129932811322135659013037 851 52551451665143707621603445891 852 54848763190874225370149241183 853 57245104582899874401840277602 854 59744685358539935903733488435 855 62351891487662533654968184596 856 65071292686652627064764894124 857 67907650009718819602644292979 858 70865923749493019135153300100 859 73951281659350383787603596271 860 77169107510370042582471975459 861 80525009996368235567715776174 862 84024832000967836889596097612 863 87674660241220106156068411027 864 91480835302869178231964375405 865 95449962082945607975029401136 866 99588920655995618896841024244 867 103904877580895881164133819874 868 108405297665873223034133077099 869 113097956210042938331623690848 870 117990951740502032468063632082 871 123092719264763088858572484375 872 128412044059094371264269760555 873 133958076014140505120143203120 874 139740344560039741120293035675 875 145768774194126559433450289806 876 152053700635216576975996561660 877 158605887629412499520723035611 878 165436544433349796332987182742 879 172557344001816959728092036489 880 179980441907742466574024318856 881 187718496023636943499761727439 882 195784686994719626851091620917 883 204192739535141032808286055054 884 212956944579944154521801492411 885 222092182326682485335975488573 886 231613946201940354774520434975 887 241538367789377437023998463608 888 251882242757350773440152838597 889 262663057825652201215780051313 890 273899018812442938693354939491 891 285609079804068188164223210310 892 297812973492099551939880281927 893 310531242723679750176368577644 894 323785273313039504742439492823 895 337597328163918439686952459425 896 351990582754557744040031924403 897 366989162038940074218641095394 898 382618178820039434316547293051 899 398903773653008497216602012351 900 415873156338481128430540531948 901 433554649068501696150887507637 902 451977731290018647708875344314 903 471173086353395775116644616337 904 491172650016009600835794047465 905 512009660873713391463157800719 906 533718712795766966984547624623 907 556335809441754760281425365825 908 579898420942052535290291193774 909 604445542826553888979494704164 910 630017757289641737003737462380 911 656657296882785576899943403297 912 684408110729673619093075321398 913 713315933362448114721841768443 914 743428356281414196704291166856 915 774794902344535619924772300322 916 807467103097127404756440493980 917 841498579156403998523345034744 918 876945123769955338866989655033 919 913864789671800702243528247986 920 952317979364425359082737111196 921 992367538960136552802277279691 922 1034078855720197869094573470659 923 1077519959435513551882406161157 924 1122761627798152284029610800166 925 1169877495918722463867954295776 926 1218944170150554489328757185529 927 1270041346387809307549414915877 928 1323251933011033855271692132033 929 1378662178660322547778647254904 930 1436361805023138024588081274498 931 1496444144830993748780974814495 932 1559006285266625195026081581993 933 1624149216990975378967053310027 934 1691977989007314912474290049991 935 1762601869588107091145159331297 936 1836134513498836460068239729022 937 1912694135761945722314311131328 938 1992403692213293746425883504168 939 2075391067113158083398079153078 940 2161789268083783160438175808299 941 2251736628655821941618241293270 942 2345377018716760104075300120190 943 2442860063165549960932467017663 944 2544341369089243757214695671128 945 2649982761789405440445234585517 946 2759952529998525466130361038568 947 2874425680639568146436496777987 948 2993584203495176106541915270508 949 3117617346166945786842704187696 950 3246721899719604062828821904707 951 3381102495419863929990571905250 952 3520971912995251200243784621720 953 3666551400854280108890245134872 954 3818071008726050080929703042787 955 3975769933194645411784128628105 956 4139896876621682917329133386886 957 4310710419968977478226989570726 958 4488479410052622814106935062669 959 4673483361779823663632494184012 960 4866012875940609269176530405613 961 5066370073148116775021212570520 962 5274869044543502938935939552323 963 5491836319904734861108204453869 964 5717611353822574155414051033965 965 5952547030632017005670601235159 966 6197010188813336758761274084004 967 6451382165603710564192745821999 968 6716059362588252154749937662058 969 6991453833068135349387094533627 970 7277993892033435716125260147940 971 7576124749599359101621960790938 972 7886309168796727493240339888884 973 8209028148640975002108569365820 974 8544781633438535563154340428631 975 8894089249325401520470367029173 976 9257491069069868618077444040508 977 9635548406210082723433068753440 978 10028844639637041248009905832811 979 10437986069775204972437686161602 980 10863602807555922851271795404854 981 11306349697423493461019452170017 982 11766907275659966030446106154613 983 12245982765362754607875708358726 984 12744311109458890113542134077684 985 13262656043191303261364837721347 986 13801811207566011468399819208967 987 14362601305304514953261655307190 988 14945883300903192097847703139164 989 15552547666461065742988605648637 990 16183519674999097629082732894582 991 16839760743058205810116409917335 992 17522269824429603585056511190794 993 18232084856939880978587739989247 994 18970284264284612334093977567563 995 19737988514978233738925560240581 996 20536361740564620784123975331103 997 21366613415312273455711884845197 998 22230000099700418000790955199358 999 23127827250087734026476066078688 1000 24061451097043954897106594336552