-1 1 0 0 1 3 2 2 3 3 4 6 5 10 6 12 7 15 8 22 9 30 10 36 11 44 12 60 13 78 14 96 15 117 16 150 17 190 18 228 19 276 20 340 21 420 22 504 23 603 24 732 25 885 26 1052 27 1245 28 1488 29 1770 30 2088 31 2454 32 2902 33 3420 34 3996 35 4666 36 5460 37 6378 38 7400 39 8583 40 9972 41 11566 42 13344 43 15378 44 17752 45 20448 46 23472 47 26904 48 30876 49 35379 50 40414 51 46116 52 52644 53 60026 54 68268 55 77571 56 88144 57 100068 58 113364 59 128314 60 145224 61 164202 62 185360 63 209049 64 235734 65 265580 66 298800 67 335904 68 377516 69 423936 70 475488 71 532937 72 597108 73 668526 74 747676 75 835671 76 933672 77 1042456 78 1162824 79 1296285 80 1444532 81 1608690 82 1790028 83 1990628 84 2212896 85 2458512 86 2729368 87 3028392 88 3358872 89 3723398 90 4124664 91 4566846 92 5054448 93 5591292 94 6181344 95 6830347 96 7544604 97 8329542 98 9190994 99 10136844 100 11175882 101 12315794 102 13565016 103 14934426 104 16436100 105 18081000 106 19880964 107 21851158 108 24008028 109 26367126 110 28945040 111 31762671 112 34842576 113 38206422 114 41877456 115 45884178 116 50257604 117 55027644 118 60226776 119 65893747 120 72070920 121 78799647 122 86124652 123 94098762 124 102779328 125 112223404 126 122492256 127 133657647 128 145797078 129 158988732 130 173316312 131 188876738 132 205774704 133 224116392 134 244016040 135 265603896 136 289021068 137 314411294 138 341929440 139 371750496 140 404063584 141 439062840 142 476956944 143 517980533 144 562386228 145 610435332 146 662407972 147 718617645 148 779401236 149 845108562 150 916114836 151 992836995 152 1075723496 153 1165240836 154 1261889856 155 1366223710 156 1478837352 157 1600351314 158 1731431280 159 1872809586 160 2025272628 161 2189643808 162 2366804676 163 2557722426 164 2763433884 165 2985027768 166 3223668744 167 3480629815 168 3757275168 169 4055039181 170 4375456520 171 4720198218 172 5091054744 173 5489910618 174 5918781960 175 6379857402 176 6875480088 177 7408120068 178 7980417324 179 8595232418 180 9255623832 181 9964820670 182 10726271104 183 11543704080 184 12421103472 185 13362678604 186 14372922624 187 15456683898 188 16619140576 189 17865765636 190 19202399856 191 20635332756 192 22171278876 193 23817338358 194 25581083892 195 27470657808 196 29494745910 197 31662538962 198 33983831952 199 36469143033 200 39129684154 201 41977324572 202 45024706404 203 48285386378 204 51773808312 205 55505264688 206 59496038464 207 63763565535 208 68326415364 209 73204249464 210 78417994176 211 83990031216 212 89944183860 213 96305680080 214 103101356088 215 110359886950 216 118111775484 217 126389327304 218 135226888412 219 144661124886 220 154731018960 221 165477855356 222 176945507880 223 189180768660 224 202233365456 225 216155955666 226 231004477404 227 246838536012 228 263721448848 229 281720255766 230 300906141088 231 321354897381 232 343146997476 233 366367639094 234 391107242328 235 417462013998 236 445534051896 237 475431435132 238 507268817568 239 541168103866 240 577258609032 241 615677196606 242 656569000602 243 700088225745 244 746398385796 245 795672501322 246 848093977656 247 903857558619 248 963169657024 249 1026248643828 250 1093325899752 251 1164646971508 252 1240472004960 253 1321076162304 254 1406750879728 255 1497805266321 256 1594566676950 257 1697381279734 258 1806615578544 259 1922658089844 260 2045920109816 261 2176836457896 262 2315867331816 263 2463500312832 264 2620251379440 265 2786665881204 266 2963320781888 267 3150827082072 268 3349831120392 269 3561015861330 270 3785103589608 271 4022858849352 272 4275090100684 273 4542651400440 274 4826445651468 275 5127428151324 276 5446608713568 277 5785053816462 278 6143890551480 279 6524310884433 280 6927574372704 281 7355010889398 282 7808025417408 283 8288103184818 284 8796813099216 285 9335811214728 286 9906846523344 287 10511767175799 288 11152524778932 289 11831178801801 290 12549903563544 291 13310995769412 292 14116879884252 293 14970113676634 294 15873396687468 295 16829579319903 296 17841669578484 297 18912839984316 298 20046437856324 299 21245996270916 300 22515242477028 301 23858106515544 302 25278733666176 303 26781497699985 304 28371011315304 305 30052136892204 306 31830001519752 307 33710013046392 308 35697872976192 309 37799589841836 310 40021497368064 311 42370273865037 312 44852958179880 313 47476966227270 314 50250112989996 315 53180635906026 316 56277214578336 317 59548991149586 318 63005596935912 319 66657180648501 320 70514432650292 321 74588610069252 322 78891568967808 323 83435798455196 324 88234450425780 325 93301370479842 326 98651136752904 327 104299101122298 328 110261425637628 329 116555120458320 330 123198090765984 331 130209186458004 332 137608246767016 333 145416146662500 334 153654853542480 335 162347487117855 336 171518373965856 337 181193104222782 338 191398599994302 339 202163187572802 340 213516663944040 341 225490366027368 342 238117253116272 343 251431993967529 344 265471047748312 345 280272748453056 346 295877404242036 347 312327402345464 348 329667307532712 349 347943964786458 350 367206619037280 351 387507041376711 352 408899648734488 353 431441628559654 354 455193083041776 355 480217180938966 356 506580302749052 357 534352192017768 358 563606128846152 359 594419112541980 360 626872037406552 361 661049876175543 362 697041888608012 363 734941841087865 364 774848219283168 365 816864450167468 366 861099152757000 367 907666401852186 368 956685985145968 369 1008283671507348 370 1062591512262264 371 1119748157742454 372 1179899167760256 373 1243197335494914 374 1309803049168496 375 1379884671882090 376 1453618915989984 377 1531191233829436 378 1612796251495200 379 1698638224428744 380 1788931488330800 381 1883900930007444 382 1983782507368320 383 2088823795402885 384 2199284528900124 385 2315437169075568 386 2437567526708612 387 2565975415896834 388 2700975306714060 389 2842897006384514 390 2992086405516528 391 3148906260509496 392 3313736977523142 393 3486977430740316 394 3669045855240996 395 3860380783006658 396 4061441983565520 397 4272711446109354 398 4494694447094976 399 4727920669262472 400 4972945329359034 401 5230350355653406 402 5500745663843472 403 5784770493817374 404 6083094760690708 405 6396420465134424 406 6725483217374688 407 7071053832998587 408 7433939950106616 409 7814987717124102 410 8215083611752104 411 8635156345075122 412 9076178795340432 413 9539170026395272 414 10025197457058720 415 10535379131788884 416 11070886031127684 417 11632944483473748 418 12222838750858272 419 12841913734816260 420 13491577734902208 421 14173305327805038 422 14888640447798984 423 15639199608938103 424 16426675196103636 425 17252838899201218 426 18119545380542880 427 19028736109657416 428 19982443286347288 429 20982793934111112 430 22032014263187472 431 23132434231949201 432 24286492219499196 433 25496739901298382 434 26765847436478528 435 28096608890086722 436 29491947794439012 437 30954922951756736 438 32488734597983160 439 34096730843957379 440 35782414290136656 441 37549448927057502 442 39401667455123880 443 41343078931407376 444 43377876631521480 445 45510446249876952 446 47745374586518128 447 50087458620069372 448 52541714844856272 449 55113389009312238 450 57807966418445820 451 60631182692631774 452 63589034848960876 453 66687792858175380 454 69934011856042536 455 73334544893120796 456 76896556077662736 457 80627534280721446 458 84535307601880620 459 88628058468957744 460 92914339215730464 461 97403088323408626 462 102103647546545280 463 107025779785401303 464 112179687536875940 465 117576032129469720 466 123225953985900108 467 129141093765372856 468 135333614202846456 469 141816222874612344 470 148602196157813312 471 155705404226119494 472 163140336883233144 473 170922130489220168 474 179066596275430080 475 187590249878065368 476 196510341877706400 477 205844889626012232 478 215612710688675808 479 225833457720406411 480 236527654545096840 481 247716733751476932 482 259423076169449620 483 271670052029681772 484 284482063562541198 485 297884589381732508 486 311904231055198284 487 326568761654620209 488 341907176020125156 489 357949743125452836 490 374728060987670340 491 392275113900501058 492 410625331709417496 493 429814651555678248 494 449880582582494960 495 470862273366975699 496 492800581779836736 497 515738147744711616 498 539719469445976272 499 564790982733124098 500 591001143406185416 501 618400512906189624 502 647041848018598872 503 676980194325459338 504 708272983069814112 505 740980132017688116 506 775164150989067968 507 810890251783158573 508 848226462140219520 509 887243744392596506 510 928016119549664208 511 970620796529105061 512 1015138306159586774 513 1061652640678652292 514 1110251399555914236 515 1161025941339616538 516 1214071541136510960 517 1269487554528635280 518 1327377588850885184 519 1387849681517138793 520 1451016484987440312 521 1516995459273475454 522 1585909073006546328 523 1657885012751636952 524 1733056400141151368 525 1811562017832190716 526 1893546545423704848 527 1979160805014358378 528 2068562015961017328 529 2161914059956843083 530 2259387757695811000 531 2361161156800466358 532 2467419830566556352 533 2578357188769577564 534 2694174801947899128 535 2815082738839332378 536 2941299916521118408 537 3073054464643629996 538 3210584105333235636 539 3354136548452140392 540 3503969901760888584 541 3660353097542497878 542 3823566337440202448 543 3993901555216661133 544 4171662896982105420 545 4357167220637856444 546 4550744616489676992 547 4752738948762239298 548 4963508417577660252 549 5183426143349192580 550 5412880775777831496 551 5652277127212424791 552 5902036829964069984 553 6162599019756409608 554 6434421047759444684 555 6717979221013410588 556 7013769570867266904 557 7322308651880743906 558 7644134373922452480 559 7979806867337944635 560 8329909380855646560 561 8695049214983659416 562 9075858693950783916 563 9472996176148817916 564 9887147102809315008 565 10319025088004073480 566 10769373053392334360 567 11238964407768156279 568 11728604271234748752 569 12239130747469444270 570 12771416247921949536 571 13326368868120624702 572 13904933816029433360 573 14508094896348965568 574 15136876055069453088 575 15792342984610258865 576 16475604789625129140 577 17187815717861049438 578 17930176960897938070 579 18703938525302517018 580 19510401174446594232 581 20350918445933882952 582 21226898750056182168 583 22139807550044472126 584 23091169624587439356 585 24082571418180724368 586 25115663485408372452 587 26192163030196343146 588 27313856540785737756 589 28482602526691012056 590 29700334364510366416 591 30969063253966717296 592 32290881285250498548 593 33667964624736992070 594 35102576826800013744 595 36597072273516876546 596 38153899743718997236 597 39775606119380976540 598 41464840238037755424 599 43224356893516484328 600 45057020986907667012 601 46965811836800680926 602 48953827658582961344 603 51024290215660342602 604 53180549645097596016 605 55426089467867778610 606 57764531794771905192 607 60199642731563372184 608 62735337986455196008 609 65375688691529920872 610 68124927450531945240 611 70987454617392031780 612 73967844809452488552 613 77070853668439244274 614 80301424883259626376 615 83664697479941346975 616 87166013383617691968 617 90810925267333719862 618 94605204703578421920 619 98554850624978846250 620 102666098100183424128 621 106945427441657669760 622 111399573663385551216 623 116035536296216409478 624 120860589568211699880 625 125882292968930340903 626 131108502218011189460 627 136547380647332810046 628 142207411005646203972 629 148097407707158612964 630 154226529547094516544 631 160604292895331791848 632 167240585378803651744 633 174145680077039670156 634 181330250256903754260 635 188805384659740896138 636 196582603353737752584 637 204673874179146651342 638 213091629815897854288 639 221848785489253336038 640 230958757328796190260 641 240435481412120251838 642 250293433526693669808 643 260547649668391577442 644 271213747294885019776 645 282307947369496087608 646 293847097233462423696 647 305848694328432752464 648 318330910790724726228 649 331312618957809648888 650 344813417830035339876 651 358853660513277954042 652 373454482667942259912 653 388637832010293637434 654 404426498914916006856 655 420844148148448315647 656 437915351764560905020 657 455665623212411951820 658 474121452713981757696 659 493310343945587900866 660 513260852058817945632 661 534002623100246428602 662 555566434892836943736 663 577984239420311391993 664 601289206755807594600 665 625515770602337610512 666 650699675516455506168 667 676878025863354645366 668 704089336551736589712 669 732373585625251775940 670 761772268791603305136 671 792328455945533451778 672 824086849742174126112 673 857093846308110085038 674 891397598182299291796 675 927048079552265782797 676 964097153851475614266 677 1002598643817238149610 678 1042608404113868049624 679 1084184396597125118406 680 1127386768296709174952 681 1172277932229836912628 682 1218922651164934006272 683 1267388124423709735000 684 1317744077810879987760 685 1370062856800185639840 686 1424419523111988855744 687 1480891954784827402788 688 1539560949844580001624 689 1600510333717663659772 690 1663827070542068211264 691 1729601378494804621086 692 1797926849256020927844 693 1868900571776406186000 694 1942623260522806412952 695 2019199388339219419697 696 2098737324062530392168 697 2181349475082610520076 698 2267152435045721616812 699 2356267136859780658020 700 2448819011162765941680 701 2544938150470125071530 702 2644759479227414580744 703 2748422929951319335437 704 2856073625645480874776 705 2967862068736882733232 706 3083944336790075128764 707 3204482285210585847386 708 3329643757152846566448 709 3459602800912362638694 710 3594539895094793993440 711 3734642181805574742924 712 3880103708108600554716 713 4031125676072357280416 714 4187916701736436639296 715 4350693083279061874032 716 4519679078672192967784 717 4695107193186609564864 718 4877218477125689229648 719 5066262834110935340010 720 5262499340249352678360 721 5466196574595221391048 722 5677632961337017545386 723 5897097124081129030974 724 6124888252612312780980 725 6361316482600488597182 726 6606703288743841392924 727 6861381891775425427758 728 7125697679770335371232 729 7400008644287873018358 730 7684685831906093251368 731 7980113811639405839544 732 8286691158741660602664 733 8604830955502896832014 734 8934961309673770140848 735 9277525891080949889862 736 9632984487010587636336 737 10001813577051989935944 738 10384506928122561052200 739 10781576210320344511710 740 11193551634266556944152 741 11620982610725740031352 742 12064438433323557696096 743 12524508985103371568092 744 13001805469681474768512 745 13496961167897110806492 746 14010632220889866069372 747 14543498440453714280532 748 15096264147538974157104 749 15669659039921597790792 750 16264439090100323320464 751 16881387474394375591389 752 17521315534240063738336 753 18185063770845880961004 754 18873502874411939590392 755 19587534789027272766138 756 20328093814388242672416 757 21096147745657045649670 758 21892699052831158226744 759 22718786100897873511197 760 23575484412082393904304 761 24463907971689519593102 762 25385210579097272531328 763 26340587245359577070202 764 27331275638914895445888 765 28358557581106417791888 766 29423760593285164748544 767 30528259497161515123089 768 31673478070116792108060 769 32860890757413965245830 770 34092024443320657711488 771 35368460283047371798158 772 36691835597457044510604 773 38063845832750187875770 774 39486246587413225987344 775 40960855708603302966891 776 42489555460203952019820 777 44074294765056982406136 778 45717091523969671487268 779 47420035013978168417184 780 49185288368418293056944 781 51015091141650739271904 782 52911761961393349081184 783 54877701271491206775693 784 56915394168036263306310 785 59027413332071124747580 786 61216422062230871371152 787 63485177410551506622504 788 65836533424766722074068 789 68273444500767485857944 790 70798968849033298292544 791 73416272078716136019609 792 76128630903164735626320 793 78939436971062800345188 794 81852200827505881215180 795 84870556009212154328082 796 87998263278184319950416 797 91239214998562144970170 798 94597439661575476339584 799 98077106563376985121671 800 101682530640673681574906 801 105418177469538248552652 802 109288668432973423352220 803 113298786062671889630484 804 117453479560574280517200 805 121757870506333570939008 806 126217258757010933873824 807 130837128545198598763338 808 135623154781948272302772 809 140581209571437765238718 810 145717368944552697900600 811 151037919818433709141740 812 156549367189248352043488 813 162258441566054463071988 814 168172106653896905138832 815 174297567294158033453148 816 180642277670420407131000 817 187213949788766613367224 818 194020562241751361236484 819 201070369265166191102700 820 208371910096989053628552 821 215934018648641892509426 822 223765833499029499774392 823 231876808221727343037129 824 240276722055996166395664 825 248975690933103496140996 826 257984178869826931931712 827 267313009740921154175714 828 276973379442683578935072 829 286976868460635237311958 830 297335454854778191788400 831 308061527675814225218049 832 319167900826111099910532 833 330667827380171913466270 834 342575014379864398943280 835 354903638119610632108524 836 367668359937194608157600 837 380884342526910789264924 838 394567266792342258382248 839 408733349256025371980921 840 423399360043777809410496 841 438582641462639143585005 842 454301127192010878424748 843 470573362107581567911956 844 487418522758213572199848 845 504856438517258684378646 846 522907613430488646912576 847 541593248782862542491834 848 560935266407023878013844 849 580956332757842283402084 850 601679883778124690576772 851 623130150580701471839160 852 645332185972854509135904 853 668311891850621475027546 854 692096047491423768637760 855 716712338773598826311901 856 742189388352282067220568 857 768556786822811581860670 858 795845124903858385550112 859 824086026672680681926638 860 853312183885881494511696 861 883557391420955223827784 862 914856583875069208921056 863 947245873357796108007827 864 980762588515624726000956 865 1015445314828181573655660 866 1051333936217402818549220 867 1088469678011253330595953 868 1126895151304849113208320 869 1166654398764164239842408 870 1207792941918976499332464 871 1250357829992164569410292 872 1294397690313896641912132 873 1339962780371819064524988 874 1387105041550013862974784 875 1435878154610070503762648 876 1486337596969233800441496 877 1538540701833429242422746 878 1592546719244837938202528 879 1648416879104407248061377 880 1706214456231512950565712 881 1766004837526129702756310 882 1827855591300973785634308 883 1891836538851955947701226 884 1958019828337351926944520 885 2026480011039574724736648 886 2097294120085805763403608 887 2170541751704800619060107 888 2246305149099525911588232 889 2324669289019132967298840 890 2405721971116446803149544 891 2489553910178419814262090 892 2576258831319646927573056 893 2665933568233301805355184 894 2758678164596864372313960 895 2854595978731525022260326 896 2953793791617143574015952 897 3056381918369364748808448 898 3162474323288881853732604 899 3272188738594636955385574 900 3385646786956126803898380 901 3502974107945221319090376 902 3624300488531717152913712 903 3749759997748968811649115 904 3879491125659758088576588 905 4013636926758372021641036 906 4152345167949154587802464 907 4295768481244286896299522 908 4444064521327862367517512 909 4597396128139768768084968 910 4755931494637723766337600 911 4919844339898722143134899 912 5089314087726020648289552 913 5264526050934940062933336 914 5445671621496205392888100 915 5632948466718939064206468 916 5826560731660915041273492 917 6026719247961625410852920 918 6233641749299832949686168 919 6447553093681228568634927 920 6668685492768008351581216 921 6897278748471009483802092 922 7133580497031930956975796 923 7377846460827738390681668 924 7630340708136339474261120 925 7891335921112422103236390 926 8161113672230094034331024 927 8439964709454249991300095 928 8728189250410470621040164 929 9026097285834155951561918 930 9334008892588309546664448 931 9652254556545487930544280 932 9981175505638310414234140 933 10321124053395041718851736 934 10672463953286558090592264 935 11035570764218028800042905 936 11410832227508650810793400 937 11798648655716252312629926 938 12199433333674596159652032 939 12613612932119283438927804 940 13041627934289427984292416 941 13483933075907267855127650 942 13940997798950262250036872 943 14413306719639478769276625 944 14901360111080769121546488 945 15405674401011917582367912 946 15926782685122864920784608 947 16465235256426711096560122 948 17021600151173492195790912 949 17596463711817299508030252 950 18190431167562950543559256 951 18804127233030545091462759 952 19438196725592326379993760 953 20093305201956945762609726 954 20770139614593803548231224 955 21469408988603986274510844 956 22191845119662421956443232 957 22938203293678903764874104 958 23709263028845374341760320 959 24505828840752659991572068 960 25328731031280207603137160 961 26178826501988027633739195 962 27056999592762221208932232 963 27964162946483467288989318 964 28901258400510750598196844 965 29869257905801185659537140 966 30869164474511696379696384 967 31902013156948793559994488 968 32968872048758448807617886 969 34070843329279902341976168 970 35209064332015205192784072 971 36384708648189585601404496 972 37598987264406682721585532 973 38853149735438174827719912 974 40148485393218720004482912 975 41486324593143583010122080 976 42868039998798861358266084 977 44295047906293775653700574 978 45768809609399723182924560 979 47290832806730817456243990 980 48862673052237199451096564 981 50485935250326496443917100 982 52162275196968347283451704 983 53893401168170955315711517 984 55681075557259705813878360 985 57527116562437039773566244 986 59433399926147146595731816 987 61401860727807607644808332 988 63434495231516255124778224 989 65533362790396321080250560 990 67700587809292727972596704 991 69938361767576040104601411 992 72248945303862393354902848 993 74634670364518844407726692 994 77097942417879412024424832 995 79641242736146486821813226 996 82267130747010434181686928 997 84978246457088383267602690 998 87777312949345809373035336 999 90667138956720369500988924 1000 93650621514232715604057096