0 0 1 0 2 0 3 1 4 1 5 2 6 4 7 4 8 7 9 9 10 14 11 14 12 26 13 25 14 40 15 47 16 65 17 71 18 108 19 114 20 163 21 188 22 246 23 280 24 383 25 429 26 555 27 653 28 825 29 950 30 1215 31 1393 32 1741 33 2036 34 2488 35 2906 36 3571 37 4128 38 5003 39 5853 40 7032 41 8169 42 9805 43 11370 44 13544 45 15765 46 18621 47 21609 48 25539 49 29537 50 34700 51 40188 52 47004 53 54293 54 63392 55 73086 56 85015 57 97958 58 113548 59 130602 60 151189 61 173496 62 200210 63 229652 64 264350 65 302644 66 347777 67 397485 68 455772 69 520355 70 595398 71 678698 72 775430 73 882542 74 1006378 75 1144215 76 1302505 77 1478713 78 1680910 79 1905722 80 2162953 81 2449417 82 2775745 83 3139418 84 3553211 85 4013665 86 4536272 87 5118626 88 5777581 89 6511549 90 7341160 91 8264367 92 9305861 93 10465300 94 11770219 95 13222553 96 14855276 97 16670625 98 18708427 99 20974333 100 23513266 101 26334787 102 29493100 103 33000397 104 36921220 105 41274064 106 46132886 107 51524392 108 57537141 109 64203722 110 71630283 111 79861425 112 89019814 113 99164379 114 110441918 115 122925403 116 136789470 117 152128687 118 169146904 119 187965111 120 208826483 121 231878429 122 257411254 123 285611471 124 316818558 125 351265478 126 389357017 127 431376794 128 477806539 129 528997280 130 585515566 131 647794083 132 716506801 133 792176908 134 875605543 135 967433931 136 1068604946 137 1179899863 138 1302439655 139 1437165049 140 1585406234 141 1748303651 142 1927426050 143 2124153443 144 2340345608 145 2577656404 146 2838290023 147 3124239565 148 3438103265 149 3782275395 150 4159833068 151 4573635406 152 5027322386 153 5524318190 154 6068912661 155 6665199938 156 7318249097 157 8032931211 158 8815233224 159 9670962257 160 10607167129 161 11630758148 162 12750051296 163 13973243360 164 15310135796 165 16770459729 166 18365742410 167 20107522567 168 22009372299 169 24084933805 170 26350176886 171 28821241753 172 31516882592 173 34456171285 174 37661148032 175 41154302333 176 44961516317 177 49109311909 178 53628040288 179 58548947495 180 63907634064 181 69740845748 182 76090314704 183 82999254762 184 90516520683 185 98692882752 186 107585540020 187 117254057766 188 127765359653 189 139189309514 190 151604126707 191 165091686955 192 179743399669 193 195655099421 194 212933543914 195 231690871616 196 252051645005 197 274146973549 198 298122164581 199 324130349937 200 352340929497 201 382932680438 202 416102926979 203 452060238783 204 491034389885 205 533268479676 206 579029913796 207 628601913429 208 682295439931 209 740440226880 210 803397754379 211 871551595463 212 945321710458 213 1025154088533 214 1111536292537 215 1204986552781 216 1306070681223 217 1415390397359 218 1533601959411 219 1661403688934 220 1799556250547 221 1948869574964 222 2110224966199 223 2284561166015 224 2472898691346 225 2676325039167 226 2896021217373 227 3133246321779 228 3389366477331 229 3665838521934 230 3964241888417 231 4286261390426 232 4633722022357 233 5008571160000 234 5412916589268 235 5849007832513 236 6319278039915 237 6826324492568 238 7372954407574 239 7962164989585 240 8597193559305 241 9281496879520 242 10018806430638 243 10813107101846 244 11668697719875 245 12590169626765 246 13582473037600 247 14650895237229 248 15801133790545 249 17039274553039 250 18371872010254 251 19805927755887 252 21348978721557 253 23009075944722 254 24794882025653 255 26715650514370 256 28781333028646 257 31002560174600 258 33390759412203 259 35958137418053 260 38717810413464 261 41683788540810 262 44871119415347 263 48295875727554 264 51975313474708 265 55927862954989 266 60173303955595 267 64732761014728 268 69628896723458 269 74885912959125 270 80529764377618 271 86588166091514 272 93090830327725 273 100069481959817 274 107558120139533 275 115593044032081 276 124213142256020 277 133459929877554 278 143377869678279 279 154014422508437 280 165420403069407 281 177650046943428 282 190761404904552 283 204816428481519 284 219881408135391 285 236027080598518 286 253329114935626 287 271868246280062 288 291730815335619 289 313008931655302 290 335801073898664 291 360212287404418 292 386354851027408 293 414348515590074 294 444321245121642 295 476409501167421 296 510759068321666 297 547525391466809 298 586874494118615 299 628983377832208 300 674041044276615 301 722248964549141 302 773822218597152 303 828990044723391 304 887997108545299 305 951104145848734 306 1018589376440656 307 1090749251994654 308 1167900033443537 309 1250378658805793 310 1338544501695211 311 1432780377653249 312 1533494505209551 313 1641121668125029 314 1756125404786585 315 1878999347947911 316 2010269667412174 317 2150496613549476 318 2300277243379926 319 2460247193327224 320 2631083724287835 321 2813507754674871 322 3008287260011082 323 3216239603282692 324 3438235331085294 325 3675200838450946 326 3928122610879374 327 4198050267924597 328 4486101301292348 329 4793464549455470 330 5121405490731777 331 5471270202407588 332 5844491277064896 333 6242592329313993 334 6667194606224202 335 7120022115171799 336 7602909010524792 337 8117805419330757 338 8666785699034786 339 9252055050286215 340 9875958745219588 341 10540989630727485 342 11249798442046712 343 12005202305658562 344 12810196269434601 345 13667962931372344 346 14581885325960156 347 15555557823507051 348 16592800532457256 349 17697671624099788 350 18874483432943745 351 20127816384222943 352 21462536987505054 353 22883813569646163 354 24397136383962233 355 26008335366895989 356 27723602614829297 357 29549512413462272 358 31493046354698763 359 33561615921466166 360 35763090553389987 361 38105823093828247 362 40598681153404959 363 43251075767330672 364 46072996435756603 365 49075043385434658 366 52268466715157653 367 55665202691090611 368 59277917479733476 369 63120047962476337 370 67205850582600025 371 71550447226566989 372 76169879777810086 373 81081161664036171 374 86302338784184926 375 91852547396964942 376 97752082150338483 377 104022461070908703 378 110686501515424861 379 117768393094479107 380 125293782464908081 381 133289855124751998 382 141785430055337564 383 150811051438706577 384 160399094279860677 385 170583867203139357 386 181401730320273014 387 192891210402291648 388 205093132385293912 389 218050748370024842 390 231809884322831674 391 246419084502711966 392 261929775097668099 393 278396425869831928 394 295876732644488899 395 314431798174763906 396 334126335624564538 397 355028870861027892 398 377211969321045638 399 400752462198199146 400 425731699328179747 401 452235802023747684 402 480355944918553702 403 510188638490235716 404 541836043138253580 405 575406284786738489 406 611013804812286538 407 648779712506694389 408 688832174882351166 409 731306810171483361 410 776347121992872999 411 824104938540326687 412 874740896062349521 413 928424928919963569 414 985336807889092753 415 1045666686812782552 416 1109615701852874511 417 1177396581107284930 418 1249234311580123798 419 1325366818848343959 420 1406045709274025150 421 1491537027552199971 422 1582122082524056888 423 1678098291310990365 424 1779780097965024225 425 1887499913860502385 426 2001609139438841467 427 2122479211549485902 428 2250502739673761689 429 2386094672087994153 430 2529693559148130580 431 2681762851453104822 432 2842792304149393045 433 3013299421662946928 434 3193831018505756167 435 3384964826739065407 436 3587311230389819488 437 3801515053570316691 438 4028257487471298080 439 4268258078950353542 440 4522276871120816054 441 4791116614372273932 442 5075625143779380240 443 5376697836892819120 444 5695280253695167466 445 6032370868058273829 446 6389023998737933237 447 6766352844289675826 448 7165532736575342286 449 7587804512127388979 450 8034478123009183367 451 8506936381073791642 452 9006638964736464693 453 9535126576470175767 454 10094025388073424735 455 10685051656043367066 456 11310016652447217252 457 11970831787475618843 458 12669514078018816508 459 13408191831935036564 460 14189110711852178179 461 15014640041458115827 462 15887279528121778703 463 16809666257785790282 464 17784582146696084353 465 18814961698496456714 466 19903900262642538319 467 21054662635035080938 468 22270692208831059816 469 23555620508381276613 470 24913277327120688948 471 26347701293976324357 472 27863151102794792206 473 29464117220746642562 474 31155334324639293418 475 32941794272145101422 476 34828759872343849104 477 36821779253176748246 478 38926701106658754793 479 41149690599810215908 480 43497246249531539501 481 45976217539393120888 482 48593823595190362591 483 51357672686767733033 484 54275782892782721211 485 57356603685232041018 486 60609038791375883890 487 64042470078849952114 488 67666782844077348270 489 71492392238254256470 490 75530271234956313257 491 79791979861938959168 492 84289696126529241424 493 89036248345155133444 494 94045149333591803999 495 99330632155975901120 496 104907687918137435309 497 110792105290680777733 498 117000512278086421088 499 123550419906369579479 500 130460268378520925452 501 137749475356951789025 502 145438486957319582652 503 153548831099613003461 504 162103173838200371561 505 171125378303199044714 506 180640566914920891486 507 190675186489904362060 508 201257076943050326047 509 212415543190650054539 510 224181431004293339236 511 236587206406695499730 512 249667039408245189557 513 263456891661396427526 514 277994608883871490329 515 293320017614234520892 516 309475027206348848455 517 326503736612925477451 518 344452546924334520242 519 363370279199614003368 520 383308298619667402894 521 404320644486996298757 522 426464167170007840933 523 449798671504212530142 524 474387067821482559235 525 500295530108107329958 526 527593662541122714538 527 556354673893227097501 528 586655561139372222426 529 618577301745978734886 530 652205056065774413895 531 687628379310826392669 532 724941444623140153718 533 764243276708836943854 534 805637997658322574712 535 849235084413664741352 536 895149639616468456088 537 943502675294420337535 538 994421411238758761169 539 1048039587530524482858 540 1104497793195216373286 541 1163943810446140239209 542 1226532976633220285341 543 1292428563362800185194 544 1361802175052507910854 545 1434834166395935695650 546 1511714081159114141259 547 1592641111796852957608 548 1677824582481074058550 549 1767484455046800386230 550 1861851860630856624826 551 1961169656532216143082 552 2065693011265392800917 553 2175690017365019525216 554 2291442335124719156248 555 2413245866863876725672 556 2541411465133254298639 557 2676265674496498605272 558 2818151510543309657800 559 2967429275823175148609 560 3124477416619609140656 561 3289693420314611322576 562 3463494757547842712733 563 3646319868992082920985 564 3838629201255592210036 565 4040906291816538910268 566 4253658907830643361417 567 4477420238813367124008 568 4712750148394153464558 569 4960236485255345916941 570 5220496458837061120779 571 5494178080048123242667 572 5781961672978965521681 573 6084561458001495133369 574 6402727212699222306565 575 6737246011178090958310 576 7088944048683605107788 577 7458688552262214600581 578 7847389784913939345034 579 8256003144185544580895 580 8685531363214276336911 581 9137026815410545496323 582 9611593931397066107682 583 10110391729661791427421 584 10634636470199265951424 585 11185604432899010939143 586 11764634830665662134931 587 12373132859367919841180 588 13012572895367854805448 589 13684501843106232175112 590 14390542644325280226397 591 15132397951826668657308 592 15911853980243518646412 593 16730784537195888262566 594 17591155248278360892925 595 18495027979774508708769 596 19444565473596918890800 597 20442036198931082913143 598 21489819436217983914335 599 22590410598603020353703 600 23746426807714759483428 601 24960612729621820720113 602 26235846689162281708869 603 27575147069292000401518 604 28981679015087019711034 605 30458761449931566720934 606 32009874425085826927471 607 33638666811144520106162 608 35348964354269850038535 609 37144778106791927271919 610 39030313256889940845721 611 41009978368143902092027 612 43088395055651146147989 613 45270408110818605864478 614 47561096103672316254657 615 49965782476251630677311 616 52490047158256160455008 617 55139738720119974045630 618 57920987097201022482388 619 60840216902030927120102 620 63904161361045466389698 621 67119876894689307655822 622 70494758380276833152830 623 74036555118648217825590 624 77753387547211553664675 625 81653764722770051120288 626 85746602620205362023892 627 90041243273008893866311 628 94547474805505363440667 629 99275552385610891926492 630 104236220152059661395760 631 109440734148071780454092 632 114900886319832787167180 633 120629029615192170264252 634 126638104245762305512166 635 132941665151595582748810 636 139553910736837116823555 637 146489712919666016128117 638 153764648570581527110120 639 161395032386878893950053 640 169397951283509106401863 641 177791300353135695293764 642 186593820482238738573234 643 195825137681521895298134 644 205505804224694634674825 645 215657341659843884783999 646 226302285795301578423659 647 237464233730747082406130 648 249167893043948024891621 649 261439133211018773130147 650 274305039379820355144319 651 287793968582190469355974 652 301935608514630383301011 653 316761038981680323247547 654 332302796142460595208867 655 348594939663950123609277 656 365673122933254115738667 657 383574666442639071145666 658 402338634512361633315172 659 422005915476224499558969 660 442619305508743977950776 661 464223596231047928911422 662 486865666289427045142385 663 510594577056963625869861 664 535461672668477209382738 665 561520684553740985563659 666 588827840696909043038107 667 617441979802968159238082 668 647424670618362041278217 669 678840336603906584531230 670 711756386227984174121251 671 746243349097018469134618 672 782375018213825987287921 673 820228598601442709697667 674 859884862607554197267837 675 901428312149585911667408 676 944947348242198231321036 677 990534448091732261077462 678 1038286350128224381842435 679 1088304247286230357684622 680 1140693988936405261884324 681 1195566291808169658162587 682 1253036960339395687354300 683 1313227116825143324441131 684 1376263441838248570162480 685 1442278425328327377288779 686 1511410628911996121022688 687 1583804959798482424692220 688 1659612956906817669553496 689 1738993089659745371668450 690 1822111070057601358854860 691 1909140178561896604802016 692 2000261604442914533597898 693 2095664801169597137946557 694 2195547857551410886132113 695 2300117885263305223587809 696 2409591423523517144638214 697 2524194861612833496700821 698 2644164880070212309162025 699 2769748911315930591675427 700 2901205620607815781352259 701 3038805408149783432278872 702 3182830933334860514376897 703 3333577662015937726209417 704 3491354437869528056079006 705 3656484078826267317934915 706 3829303999723545170871734 707 4010166862241528025983753 708 4199441253375669763082147 709 4397512393602125077944895 710 4604782876095110141293373 711 4821673438256050976033781 712 5048623767028437789021876 713 5286093339370636568886518 714 5534562299485114855317385 715 5794532374298485906443155 716 6066527828925848985231679 717 6351096463746545069508246 718 6648810654971176491795688 719 6960268440471191583006256 720 7286094652909543400096905 721 7626942102100334423578407 722 7983492808807940763193300 723 8356459292083610171866313 724 8746585912536436836900457 725 9154650273821407907617884 726 9581464684943451105165185 727 10027877685860719786030623 728 10494775639204996455005375 729 10983084390820157275544740 730 11493771002173851295423533 731 12027845557579660345992902 732 12586363049541997779511459 733 13170425345417504190431409 734 13781183238983788794569918 735 14419838590387615231841056 736 15087646558365225087122413 737 15785917928508925692860525 738 16516021541799647116162389 739 17279386827507276945446480 740 18077506445032747252602157 741 18911939039149147548389071 742 19784312113599603111175628 743 20696325027894766875408241 744 21649752122683345178737426 745 22646445978956680775221564 746 23688340816911051251008138 747 24777456040182177973984097 748 25915899931763228386221232 749 27105873507812515482842491 750 28349674536190248820725196 751 29649701726463639766139793 752 31008459098791567804458339 753 32428560539006009989232925 754 33912734547920649772068162 755 35463829192810281691018286 756 37084817269761860367545154 757 38778801685519726583919252 758 40549021068251720294633687 759 42398855616594442110265906 760 44331833197190179162865326 761 46351635700870987289090954 762 48462105668553076173414095 763 50667253197860757881953950 764 52971263142463864697819624 765 55378502616083647235483224 766 57893528814147643801290008 767 60521097166062179732747647 768 63266169832161554315399862 769 66133924559400476157010870 770 69129763911016036160819447 771 72259324885414804912133394 772 75528488940774423220328982 773 78943392441902878937842290 774 82510437547211525575817918 775 86236303553739239969086173 776 90127958719562484907940036 777 94192672583038137124538016 778 98438028799813630288633358 779 102871938518685388373975616 780 107502654318970729189281280 781 112338784732243083586121028 782 117389309372967778723420407 783 122663594702802767624441133 784 128171410455126453609761501 785 133922946746629018866771352 786 139928831904719438158727039 787 146200151039826825903027727 788 152748465393716783903958903 789 159585832495327584520228410 790 166724827157808129629912753 791 174178563350887527344855846 792 181960716985027757598125519 793 190085549644329102633962879 794 198567933307634345591453098 795 207423376097873351559010603 796 216668049102331586203554462 797 226318814307206924862824992 798 236393253692638323189123168 799 246909699535164364311688144 800 257887265967578764844682542 801 269345881847027156451181527 802 281306324985401867422789450 803 293790257797081447130394346 804 306820264422491851854178054 805 320419889387079866231571199 806 334613677858952824029879488 807 349427217569687713727198749 808 364887182466726245118738112 809 381021378167169633571628104 810 397858789286968208005050798 811 415429628721060166627038737 812 433765388954482249839794299 813 452898895486211349122560388 814 472864362452272265990053093 815 493697450536576442118805539 816 515435327263062542317601114 817 538116729764850432942815551 818 561782030131579842676063179 819 586473303438475819529159396 820 612234398566522103486172239 821 639111011925745306628350554 822 667150764199858460375607198 823 696403280233407712210647212 824 726920272189247789364906400 825 758755626107364817718569760 826 791965492003214775099400653 827 826608377647262960218371609 828 862745246175061368090068813 829 900439617681070648666487946 830 939757674957623216943715970 831 980768373544677370159911841 832 1023543556264779815018566946 833 1068158072422324221185987686 834 1114689901855580728424694836 835 1163220284035094622184056794 836 1213833852412104791136728133 837 1266618774226247945509673582 838 1321666895992580749154363334 839 1379073894894101721593408402 840 1438939436317486933850107155 841 1501367337776483238446787758 842 1566465739479757130424644225 843 1634347281807356334430459517 844 1705129289973178128877012760 845 1778933966158880031203880517 846 1855888589418852707992635458 847 1936125723664656812054041007 848 2019783434052526697595544297 849 2107005512107128151703138512 850 2197941709931050404203943268 851 2292747983859966408048504595 852 2391586747940860712519544157 853 2494627137622120069470104533 854 2602045284063005869914181551 855 2714024599482443618219296313 856 2830756073987140081920009916 857 2952438584332559682660752852 858 3079279215091818239968803171 859 3211493592722269136224897653 860 3349306233042641810099732532 861 3492950902649603769753358240 862 3642670994827375594891153689 863 3798719920521440181219323780 864 3961361514973942787152598263 865 4130870460637305246770990419 866 4307532727011062961978901901 867 4491646028067498491675642417 868 4683520297962203541565990206 869 4883478185748037948373382468 870 5091855569843738254044631911 871 5309002093032680433725259625 872 5535281718802476176675646578 873 5771073309862403926046238483 874 6016771229713418614682046166 875 6272785968174042536247762154 876 6539544791805940494070522483 877 6817492420213957391970846553 878 7107091729238859457567621616 879 7408824482094605461125943092 880 7723192089548619164745353541 881 8050716400279938353770330520 882 8391940522600178184527190496 883 8747429678761694579569584655 884 9117772093131066618561853232 885 9503579915548750889926513416 886 9905490181253436933276169844 887 10324165808795913917781790563 888 10760296637429169941616487759 889 11214600505511554404595094913 890 11687824371526294188148411293 891 12180745479374893965589718534 892 12694172569673297518417669996 893 13228947138838382904249302107 894 13785944747828959173484377492 895 14366076382468935489189022498 896 14970289867362565687195328515 897 15599571335480359098200180656 898 16254946755582535786153652491 899 16937483519721183229635932882 900 17648292093157062487931838547 901 18388527729107319290384186603 902 19159392250842132097199553939 903 19962135903735135628715102393 904 20798059279981738086696471310 905 21668515318793262303566995118 906 22574911384992179438157629926 907 23518711429035066357322592939 908 24501438231615911669080063137 909 25524675736111894424439255703 910 26590071472269049593900196218 911 27699339074643500619105461740 912 28854260899459213543537811633 913 30056690743670938825492460202 914 31308556670177004060167119855 915 32611863943264507052695816627 916 33968698078536971954778132964 917 35381228011723376438084169722 918 36851709390947338678725759280 919 38382487997195900695908367442 920 39976003297920507223550095531 921 41634792138876136175436864030 922 43361492579511962770772749923 923 45158847877413980325479455275 924 47029710627522743500739791962 925 48977047062051172823324334564 926 51003941517266549936364592852 927 53113601073518464366945805924 928 55309360375151325198614666102 929 57594686637174751413488980649 930 59973184845840972105551992296 931 62448603160531438353932292234 932 65024838524651029531784647427 933 67705942493501075543834423884 934 70496127287420462207753422739 935 73399772078778196240227719272 936 76421429521742327554792122907 937 79565832534067120537662370474 938 82837901340507091732422361969 939 86242750787808143867364585875 940 89785697941619811855589357976 941 93472269976040730340597721496 942 97308212366932268643902299756 943 101299497400531855366368386683 944 105452333009351538157175501229 945 109773171947774531867932571200 946 114268721320250010829936464180 947 118945952475446548204449330329 948 123812111280248046209654000690 949 128874728787971566487012577124 950 134141632315748487729188820833 951 139620956946544062699488599324 952 145321157471893872449909205436 953 151251020792010258012640197387 954 157419678790559679748334169967 955 163836621702030542813741627801 956 170511711990306598997042942581 957 177455198757726922898928353758 958 184677732704660228451654894139 959 192190381660338015036990852548 960 200004646706492744367116458065 961 208132478916118603706445455789 962 216586296730533086860802081341 963 225379003998747683357915867784 964 234524008704079917563018388457 965 244035242403832115298558563508 966 253927180408854125780379766233 967 264214862730768131427382597139 968 274913915825698385963002237180 969 286040575164382429400156197076 970 297611708659683211404766535247 971 309644840983633468696177773387 972 322158178807370461427276879997 973 335170636998515090170646483994 974 348701865811866164539226670627 975 362772279110566731961855361543 976 377403083656312669690454475692 977 392616309508556772795651894644 978 408434841574178437931389952599 979 424882452350576120881864515208 980 441983835906767719787476149295 981 459764643148682838266354022495 982 478251518416578040394256008417 983 497472137464224968917410816322 984 517455246871396197371602369264 985 538230704943021232974767173485 986 559829524150397208907229440109 987 582283915171824605964847222055 988 605627332592197535521837191362 989 629894522323212326202192690586 990 655121570808175080192776862259 991 681345956077682372296551169379 992 708606600724935346892257706228 993 736943926871911944755829862075 994 766399913200289478414457881242 995 797018154123657736559149665411 996 828843921180424812074748546734 997 861924226729662712281021532963 998 896307890035210414018065129981 999 932045605826408174551329442091 1000 969190015427131171773229000983