-1 1 0 0 1 3 2 3 3 8 4 8 5 16 6 17 7 33 8 35 9 59 10 65 11 105 12 116 13 175 14 198 15 292 16 330 17 466 18 533 19 736 20 842 21 1132 22 1304 23 1725 24 1985 25 2576 26 2974 27 3809 28 4394 29 5555 30 6415 31 8030 32 9261 33 11475 34 13234 35 16264 36 18734 37 22843 38 26296 39 31849 40 36613 41 44058 42 50602 43 60551 44 69452 45 82669 46 94714 47 112205 48 128378 49 151402 50 173015 51 203217 52 231916 53 271355 54 309287 55 360612 56 410474 57 476995 58 542266 59 628217 60 713254 61 823900 62 934256 63 1076269 64 1218884 65 1400538 66 1584192 67 1815913 68 2051524 69 2346189 70 2647470 71 3021196 72 3405137 73 3877781 74 4365598 75 4961867 76 5579732 77 6329966 78 7110370 79 8052106 80 9034996 81 10214213 82 11448926 83 12922225 84 14469190 85 16305689 86 18239186 87 20523588 88 22934304 89 25769757 90 28768675 91 32281048 92 36003214 93 40345330 94 44955342 95 50312985 96 56010527 97 62608636 98 69636163 99 77747217 100 86397972 101 96350945 102 106979742 103 119171855 104 132206614 105 147116138 106 163072914 107 181275551 108 200774990 109 222962066 110 246750360 111 273751684 112 302723866 113 335533327 114 370762360 115 410569693 116 453339232 117 501565885 118 553410620 119 611753805 120 674505211 121 744987788 122 820829866 123 905861196 124 997394056 125 1099839201 126 1210155886 127 1333419361 128 1466193719 129 1614314935 130 1773907130 131 1951675283 132 2143252764 133 2356338104 134 2586020038 135 2841130828 136 3116153874 137 3421216090 138 3750131454 139 4114502626 140 4507402458 141 4942116909 142 5410902228 143 5928961302 144 6487649984 145 7104355390 146 7769445326 147 8502792024 148 9293678740 149 10164806551 150 11104273805 151 12137997426 152 13252781528 153 14478200265 154 15799650936 155 17250861912 156 18815702452 157 20532621165 158 22383835876 159 24413152920 160 26601007895 161 28997289833 162 31580521391 163 34407490899 164 37454672216 165 40786680459 166 44377808514 167 48301543181 168 52529863126 169 57146312147 170 62120430950 171 67547155738 172 73393470634 173 79767217575 174 86632723686 175 94112441619 176 102167955828 177 110938259955 178 120382141126 179 130657308461 180 141719725768 181 153748277510 182 166696127524 183 180766106290 184 195908649990 185 212353667039 186 230049013312 187 249255202036 188 269917733586 189 292331710174 190 316440612160 191 342578616313 192 370687635848 193 401145986100 194 433894625374 195 469361707391 196 507488019992 197 548757986565 198 593113234512 199 641101693726 200 692667088263 201 748429015549 202 808334867906 203 873085091048 204 942632665260 205 1017769232452 206 1098455714234 207 1185586586385 208 1279133548696 209 1380107021207 210 1488492910610 211 1605432321616 212 1730929460328 213 1866272713680 214 2011489481054 215 2168034087468 216 2335962921587 217 2516917242423 218 2710989300866 219 2920030882924 220 3144178190524 221 3385520076320 222 3644246220370 223 3922712355711 224 4221172793914 225 4542283669889 226 4886376989978 227 5256446936581 228 5652918435676 229 6079166025146 230 6535725298570 231 7026398647539 232 7551852937418 233 8116371770395 234 8720777205466 235 9369893938609 236 10064726899640 237 10810709118358 238 11609060415932 239 12465897594976 240 13382692303012 241 14366329785855 242 15418576116215 243 16547179944872 244 17754250773776 245 19048507195498 246 20432458503114 247 21915912674288 248 23501843471128 249 25201282202508 250 27017741303565 251 28963625532717 252 31043070961546 253 33270024073302 254 35649341832094 255 38196700968228 256 40917790469758 257 43830228550091 258 46940663168374 259 50268890583864 260 53822662513376 261 57624218216073 262 61682578242784 263 66022721460727 264 70655125201944 265 75607840008888 266 80893013903048 267 86542140697722 268 92569282254654 269 99009791502921 270 105879920428165 271 113219346239884 272 121046824626600 273 129406877415596 274 138321119763402 275 147839499935767 276 157986895773210 277 168819332535521 278 180365407553824 279 192687950218897 280 205819794393962 281 219831386296678 282 234760381296042 283 250685750436651 284 267650631863220 285 285743535858500 286 305013830546512 287 325560698361640 288 347440581052427 289 370764598352005 290 395597217769990 291 422062908703942 292 450235238225136 293 480253601944835 294 512201877007281 295 546236144522220 296 582451955412166 297 621024039250326 298 662061156399346 299 705758874484122 300 752240891513624 301 801726055216714 302 854354945365176 303 910372412652726 304 969938104312876 305 1033325909530712 306 1100716999340598 307 1172417684593373 308 1248633419063928 309 1329706705337254 310 1415870377558800 311 1507507330142033 312 1604881253652010 313 1708420112761450 314 1818422353685742 315 1935366221253716 316 2059589289056932 317 2191625882866687 318 2331857603321694 319 2480881314195094 320 2639128131912662 321 2807264644614297 322 2985777630922344 323 3175411399405288 324 3376715270621684 325 3590520169014603 326 3817445654916282 327 4058419162229440 328 4314139100523990 329 4585640414935136 330 4873709989979520 331 5179502513193270 332 5503904101463154 333 5848202780214319 334 6213395916809894 335 6600919983006709 336 7011897017808022 337 7447928725986216 338 7910276801211389 339 8400726828309405 340 8920696875843088 341 9472177118403006 342 10056760652197552 343 10676665236904574 344 11333679797325670 345 12030275206609896 346 12768459407284474 347 13550984720099885 348 14380103947596576 349 15258882300410528 350 16189846231085910 351 17176408723830496 352 18221401944058344 353 19328625343916858 354 20501252498563980 355 21743512240059602 356 23058959282802952 357 24452299418928300 358 25927512706505580 359 27489834642566531 360 29143719796333867 361 30894991828582693 362 32748634491410090 363 34711124387434442 364 36788035224686732 365 38986568314254468 366 41312954856004222 367 43775200361859217 368 46380268551927102 369 49137057171800967 370 52053345790521210 371 55139021857912946 372 58402773311692072 373 61855585205234757 374 65507156541177616 375 69369689395708567 376 73454007795512498 377 77773662983352495 378 82340730433036018 379 87170256748149258 380 92275709060325580 381 97673791041692140 382 103379516942527668 383 109411426334742207 384 115786252909507709 385 122524569868792928 386 129645021307527894 387 137170432640535013 388 145121569929616808 389 153523752390939623 390 162400102379070590 391 171778699874082088 392 181685282993078219 393 192150987425903400 394 203204454291998882 395 214880200789376740 396 227210088940288260 397 240232377261386201 398 253982500425277084 399 268502855563214735 400 283832839098951046 401 300019425382920225 402 317106402906936322 403 335145807355530368 404 354186295070738576 405 374285497319173606 406 395497464219559956 407 417886012080679052 408 441511166013872286 409 466443577627828324 410 492749889194913850 411 520508304814205109 412 549792793264965974 413 580689902003984302 414 613281709689083826 415 647663979084358143 416 683927763648955186 417 722179002623355217 418 762518679016998800 419 805063967867779395 420 849926835400574246 421 897236859734913130 422 947118152883689980 423 999713982062305275 424 1055161887522993978 425 1113620242142756229 426 1175241428797191372 427 1240200486110976238 428 1308666199131549422 429 1380831990071520324 430 1456884765394466330 431 1537038222105880360 432 1621499282971340324 433 1710504001485666325 434 1804281404748608880 435 1903092193709730675 436 2007189800183381592 437 2116862093402131794 438 2232389443694471818 439 2354089661838813436 440 2482272847002392416 441 2617289801953153992 442 2759483426891618548 443 2909240871314363287 444 3066941218303056796 445 3233011652833728580 446 3407871162834182586 447 3591991024072615908 448 3785834224788721514 449 3989920589078618704 450 4204761611050912985 451 4430930561938380966 452 4668992397451092764 453 4919579218807702912 454 5183314893146311894 455 5460896265378451677 456 5753012106086905432 457 6060430499697893593 458 6383911707123109586 459 6724302186333767505 460 7082440927991656326 461 7459260597244477351 462 7855686869602390440 463 8272747217787715543 464 8711462742035415596 465 9172965163293474254 466 9658380606805979074 467 10168955403022582887 468 10705931245631849776 469 11270680444393333016 470 11864571838555926430 471 12489116191645125727 472 13145822198279176636 473 13836352759946641513 474 14562370377430588156 475 15325705098993068880 476 16128188541767466116 477 16971834359775336105 478 17858660085534401632 479 18790881025192704232 480 19770719056035288145 481 20800610920011790647 482 21883003053567534222 483 23020575319218489330 484 24216020880967885336 485 25472286486664878884 486 26792336334925584245 487 28179410099089652909 488 29636769659802297842 489 31167976144816055824 490 32776618324904873665 491 34466610032878288927 492 36241898939015956416 493 38106785807875275418 494 40065612282615188096 495 42123103539864007833 496 44284033619835662376 497 46553593148142374095 498 48937030650114189366 499 51440047124422043616 500 54068411675143712622 501 56828384845927138131 502 59726306791676669664 503 62769051414225033913 504 65963585176650079786 505 69317454222624906947 506 72838311809840260632 507 76534440745924807206 508 80414247282799677754 509 84486821362969966357 510 88761394673342075250 511 93247941367419129084 512 97956597824671407937 513 102898306697474509408 514 108084195759941735434 515 113526268324048009648 516 119236738389351678190 517 125228770681499399436 518 131515769130816987924 519 138112170009113565309 520 145032680570079132954 521 152293128997960907685 522 159909649835325235878 523 167899594710700642171 524 176280660958839142492 525 185071867364894964598 526 194292622148025195058 527 203963768248163287786 528 214106586594841573332 529 224743915770351855180 530 235899086221127139150 531 247597119459265139343 532 259863588592788985880 533 272725902577530542272 534 286212088144068628914 535 300352164985198446419 536 315176843840330918754 537 330718998901780201101 538 347012276480750866474 539 364092671340013263931 540 381997040008199417416 541 400764788198878187666 542 420436282460448151288 543 441054656323936339930 544 462664113573080508582 545 485311861277359878920 546 509046297539479099484 547 533919080118199236501 548 559983191056991619252 549 587295150185436384196 550 615912948551727076680 551 645898416714013036167 552 677315018389167119202 553 710230384109025931195 554 744713955956629563254 555 780839697869434606283 556 818683581760383769988 557 858326486503722453251 558 899851515129811368736 559 943347095332086540014 560 988904116779584568554 561 1036619246839115974566 562 1086591876365872639502 563 1138927665246343016859 564 1193735284302997640790 565 1251130206234554205063 566 1311231230503199349186 567 1374164536283260114567 568 1440059976386368592364 569 1509055409931585724881 570 1581292750502704117280 571 1656922597426647306374 572 1736100022445129276296 573 1818989519738430763122 574 1905760514427966533004 575 1996592652814130921688 576 2091671015004079283882 577 2191191768250563331965 578 2295357064917180417241 579 2404381083315434421454 580 2518484591074651952820 581 2637901399482923438774 582 2762872571117264264554 583 2893653315406784337520 584 3030506818096955120574 585 3173711607577122324947 586 3323554982396998323594 587 3480340879842459264939 588 3644382876288720640932 589 3816012591575927724440 590 3995572235467566050460 591 4183423583578573559139 592 4379940041605092915152 593 4585516230901383311002 594 4800559540453284142920 595 5025500362695039180066 596 5260783101409083750952 597 5506877101029819434356 598 5764267076761340205420 599 6033464783442347947556 600 6314998832176000772621 601 6609427147839617971396 602 6917326134411243104704 603 7239303973411022920951 604 7575989097881626275176 605 7928044387457714318828 606 8296154908605778002654 607 8681043065646928276465 608 9083455562379762027376 609 9504179572243937474841 610 9944028873830501071710 611 10403861107484064737240 612 10884563034441791271312 613 11387068951546441801869 614 11912345020840448774558 615 12461408918717276170284 616 13035313179723247609048 617 13635166161428621943602 618 14262114342948944862214 619 14917364692088796086658 620 15602165855678269059864 621 16317832021151905445469 622 17065722932195623000884 623 17847269342892198350746 624 18663951788380722538360 625 19517327736051191117076 626 20409009036922760709094 627 21340690885127632950480 628 22314127871506430006972 629 23331164869811683718302 630 24393711609588140312870 631 25503775615176028518410 632 26663435210280674079844 633 27874874643994780840000 634 29140355434554149909786 635 30462253825257285034764 636 31843030369741079568360 637 33285269869888447444409 638 34791649099527464999104 639 36364979386218299537013 640 38008172364569433193833 641 39724285374221544648073 642 41516485127972108727786 643 43388096109365531623195 644 45342562034509701663552 645 47383497444481120726901 646 49514646833089978049696 647 51739939641860890534939 648 54063446919042986722751 649 56489439938279248801344 650 59022344246850108350070 651 61666802143347765853946 652 64427623965471232241018 653 67309854677130743023153 654 70318722238063296279910 655 73459708566863504093602 656 76738494826245926858220 657 80161037045593865507947 658 83733508146841548521512 659 87462378528316096049103 660 91354354646932492616748 661 95416464884445726511830 662 99655994491927005117204 663 104080577080116014499228 664 108698125721960842500550 665 113516930430642973155625 666 118545585205297626088906 667 123793091883559234673354 668 129268782904415539978466 669 134982431946877733316724 670 140944172172241738319790 671 147164614086818542644554 672 153654759013661255272198 673 160426124645297866500946 674 167490653482213432712094 675 174860846571315516567038 676 182549666635118434928152 677 190570680523354554641051 678 198937956742872164000646 679 207666217183503500060176 680 216770728744140518481262 681 226267464929811504694170 682 236172991254219969465792 683 246504637343101593844537 684 257280375777681852302044 685 268519005379929206780079 686 280240023144887257835708 687 292463819426562045723976 688 305211542589896245328658 689 318505306861892568220242 690 332368049316101820493710 691 346823751202364464621806 692 361897286858063920087816 693 377614659381750339884268 694 394002841046047611769182 695 411090024235603968802765 696 428905452916419971698422 697 447479689817260145438067 698 466844438489273881744682 699 487032827772423445136793 700 508079223957586730358618 701 530019533645947818264717 702 552891005503286568354934 703 576732552690890366043312 704 601584543678440275878972 705 627489145500106141664958 706 654490103068322767643970 707 682633104588610309229672 708 711965548791590551224960 709 742536933925035469064346 710 774398612295698182621460 711 807604204347457542505435 712 842209339877930118859174 713 878272098807692758320236 714 915852738409202226857796 715 955014162474306423135526 716 995821633864733444755920 717 1038343273893836117058594 718 1082649759478831352164200 719 1128814854668375720822489 720 1176915091646854339510114 721 1227030336462399496419323 722 1279243453102864868051071 723 1333640905609743318941362 724 1390312404414043452592144 725 1449351547160737133233145 726 1510855446460612439855597 727 1574925411897916840866933 728 1641666558321433740380780 729 1711188531665450195541485 730 1783605096869839801748970 731 1859034910311975281347744 732 1937601086411555535205576 733 2019432019649244886432551 734 2104660928877421668239326 735 2193426732090837899005461 736 2285873567429468462573078 737 2382151724068073929022464 738 2482417138861980730527234 739 2586832386936866461679416 740 2695566152892705114972648 741 2808794284903201062742652 742 2926699239357404229720468 743 3049471202520869038295567 744 3177307507458715140106360 745 3310413827568712418829170 746 3449003564593981321368438 747 3593299118612793364127091 748 3743531245913840160901560 749 3899940410319645749395114 750 4062776109662572313622355 751 4232298313629486123914626 752 4408776757542622955923346 753 4592492472243728399023062 754 4783737043850811442464180 755 4982814241551661220243172 756 5190039241975637051923750 757 5405740361140600774923635 758 5630258242048516211111616 759 5863947697427866573713840 760 6107176859133291131362480 761 6360329138749013852736310 762 6623802337346387155463218 763 6898010731464369557343702 764 7183384141755073820349420 765 7480370152336634621012541 766 7789433136836107287444658 767 8111056619620006573965918 768 8445742257726656540299862 769 8794012353022225901522783 770 9156408788501418841157720 771 9533495700994071800345955 772 9925858370304484604373312 773 10334106062707806999781131 774 10758870871394978759649202 775 11200810741651590733694122 776 11660608261078036458918782 777 12138973878038807458181300 778 12636644640136825957874146 779 13154387618260912023619790 780 13692998591810212451258792 781 14253305691454719583456364 782 14836168029631155697161940 783 15442479575968971884893044 784 16073167731614000009023818 785 16729197452163557235682949 786 17411569764419737103133192 787 18121326152625538292997245 788 18859547016307034867229080 789 19627356336611510722080075 790 20425920073968232869709540 791 21256451132403312225005086 792 22120207695833830365235320 793 23018498509376726231058091 794 23952681153192145385796254 795 24924167661019498033502751 796 25934422730604800581452068 797 26984969700990881093430819 798 28077388698701998676956472 799 29213322996692005465808768 800 30394477095619656396669025 801 31622623488823718701397592 802 32899600678206285915940886 803 34227320371163043026738086 804 35607765430801926901739290 805 37042997532416066873463262 806 38535155048003836210431584 807 40086461191637838706768482 808 41699221838522539548130178 809 43375834190491925247607877 810 45118784530145480632803805 811 46930657439707116420062116 812 48814133491122520488450348 813 50771999053640406753301072 814 52807143921137724751829328 815 54922571746049513694739158 816 57121397605616911276409112 817 59406859102202717609977211 818 61782313870634714056248598 819 64251251387509835835269366 820 66817290422336447951026444 821 69484191601160788295907543 822 72255854804801358055821078 823 75136332535037663251319123 824 78129827263882963503420950 825 81240705653668637587325964 826 84473495862023809720093704 827 87832902670480946421373821 828 91323804750628411686092334 829 94951270759367007051133586 830 98720556572580839350387050 831 102637122408904103468040985 832 106706630038223847626803860 833 110934960999785919362640655 834 115328213793907901603667424 835 119892723264478278759319219 836 124635057783427216288110080 837 129562039872170145691799032 838 134680743389667029553003068 839 139998515472148257924702286 840 145522973736999136777464134 841 151262029625200922078561147 842 157223885634816781540823314 843 163417060156003852195988184 844 169850384749560946392591824 845 176533030570139882860101482 846 183474505707155675873856678 847 190684683297969595001682685 848 198173798950472353907018916 849 205952480654551401223103638 850 214031746307850548583647610 851 222423035540795424080281360 852 231138207369423947264212524 853 240189574056653885866836099 854 249589898918683618811703220 855 259352432353073268767120465 856 269490909828051534910777210 857 280019590216377749309327617 858 290953253999976740845709568 859 302307244057486179824475002 860 314097464119997388337949786 861 326340422169705419412713754 862 339053229186180874666034020 863 352253645323666476216599561 864 365960078991266318503902497 865 380191635987211806145831548 866 394968118960655084986069654 867 410310079692701248321652270 868 426238818992158542763805856 869 442776442325347527198222352 870 459945860203220567336614770 871 477770847374959880643836956 872 496276043769363474369020106 873 515487017481083527485064102 874 535430266335118188924395928 875 556133284909273594384787694 876 577624566797036151676071448 877 599933675925523221947582735 878 623091249598976577471759100 879 647129074388159640041946663 880 672080090044250385133859972 881 697978470253412229093259328 882 724859627519017402965583701 883 752760299094033499198013639 884 781718552938323063914149600 885 811773879161622317780460795 886 842967197172189609914878538 887 875340952984585515394078573 888 908939127686235694448838058 889 943807340987036110984582669 890 979992861141512450804588290 891 1017544715141559633130261623 892 1056513700243882133000695902 893 1096952501233028042461526462 894 1138915703716748710702676286 895 1182459918914005195503475330 896 1227643798894862640764216714 897 1274528169377438380083698196 898 1323176047104022535141801598 899 1373652781162116503303933266 900 1426026072704727946719475658 901 1480366125343837477223015460 902 1536745667440340863021093968 903 1595240112153609760323060548 904 1655927582545440159121534490 905 1718889081906977663832764147 906 1784208521941379106153418696 907 1851972904029400615619777085 908 1922272350777396220280994766 909 1995200298925473653661583443 910 2070853534571054462667178260 911 2149332398468854018948955087 912 2230740825265635080554224484 913 2315186561989541310570949183 914 2402781211659021929525475118 915 2493640465810429969928735234 916 2587884152873520388585245832 917 2685636485640915125797516894 918 2787026114834231425235615466 919 2892186392477228108149281808 920 3001255431110666017933683294 921 3114376384092909975497665282 922 3231697510958231577392271882 923 3353372475734589721581200936 924 3479560418979441807151544232 925 3610426275274618574094978899 926 3746140852516010219657127970 927 3886881169820160980762678605 928 4032830544689652626119394438 929 4184178952645560553096212566 930 4341123122939193922594077440 931 4503866921309186347914752872 932 4672621454962710588944052460 933 4847605479946051190426351490 934 5029045516174749703143429926 935 5217176281002372791119255853 936 5412240815139536711275895050 937 5614490944107613643360894737 938 5824187415951525827961555680 939 6041600392373719999177097740 940 6267009599215326548950552858 941 6500704849181296970476336165 942 6742986206139327569777656498 943 6994164541470044484669815730 944 7254561713313353673298297792 945 7524511158708447560627527322 946 7804358089003346620113865864 947 8094460120088796422868797813 948 8395187485279120557040608028 949 8706923706092314402819715840 950 9030065824009371678278881800 951 9365025114410633366762161914 952 9712227338726947834180533028 953 10072113504310208095089752404 954 10445140138603556829398652126 955 10831780097902689277904895362 956 11232522865294351992103919344 957 11647875411455089885134922194 958 12078362518238079509231068200 959 12524527694858288545751618703 960 12986933529147837535145212234 961 13466162662691796195311471318 962 13962818171922429373130847180 963 14477524605998904129410711601 964 15010928400071637378445737088 965 15563698979942910221186485918 966 16136529210004833803982607032 967 16730136568977198133264842829 968 17345263635207096130897728247 969 17982679338056267587948773939 970 18643179483448008891284582330 971 19327588085769866211640689129 972 20036757936765005781399198920 973 20771572023128488120969924982 974 21532944142066736684986719350 975 22321820410097982183405312976 976 23139179928845865265765059164 977 23986036390908247627491377306 978 24863438799710404370066195998 979 25772473178682607631886394182 980 26714263349275965875779513546 981 27689972750089432601034363886 982 28700805277448369527342845768 983 29748007221547444433236960067 984 30832868174309751511863264018 985 31956723090065061765562880199 986 33120953265747232426664616076 987 34326988534109186068848041382 988 35576308321679880633877800168 989 36870443983030053674369447748 990 38210979942298802822749246320 991 39599556177569488925597053736 992 41037869452191696753748748760 993 42527675958906817505248869454 994 44070792647635636291009052384 995 45669100039610213085798656650 996 47324543658772511567023322934 997 49039137026825609071148280539 998 50814963205896702243010891440 999 52654177986118888863658746973 1000 54559011547754756298339235713