-1 1 0 2 1 3 2 6 3 9 4 14 5 22 6 32 7 46 8 66 9 93 10 128 11 176 12 236 13 315 14 420 15 550 16 718 17 932 18 1198 19 1534 20 1956 21 2476 22 3120 23 3919 24 4896 25 6095 26 7562 27 9341 28 11504 29 14126 30 17284 31 21090 32 25666 33 31140 34 37692 35 45515 36 54818 37 65878 38 79000 39 94523 40 112872 41 134522 42 160004 43 189969 44 225152 45 266370 46 314616 47 371002 48 436780 49 513449 50 602682 51 706379 52 826762 53 966342 54 1127960 55 1314907 56 1530908 57 1780160 58 2067516 59 2398446 60 2779120 61 3216626 62 3718936 63 4295052 64 4955246 65 5711084 66 6575584 67 7563544 68 8691616 69 9978512 70 11445432 71 13116184 72 15017498 73 17179554 74 19636208 75 22425410 76 25589896 77 29177528 78 33241876 79 37843136 80 43048612 81 48933535 82 55582236 83 63088884 84 71558600 85 81108952 86 91871072 87 103991105 88 117632216 89 132976138 90 150225132 91 169604647 92 191365400 93 215786104 94 243176900 95 273882245 96 308284576 97 346808766 98 389926150 99 438159346 100 492088142 101 552354942 102 619671160 103 694824991 104 778688670 105 872227042 106 976507676 107 1092710592 108 1222139644 109 1366235694 110 1526589624 111 1704957302 112 1903276816 113 2123685734 114 2368540776 115 2640440294 116 2942247068 117 3277114131 118 3648513992 119 4060268676 120 4516583476 121 5022084959 122 5581860324 123 6201501460 124 6887154272 125 7645570064 126 8484162944 127 9411073628 128 10435236482 129 11566453966 130 12815479100 131 14194102673 132 15715249512 133 17393085000 134 19243128000 135 21282375252 136 23529438596 137 26004690806 138 28730426088 139 31731036361 140 35033199308 141 38666084804 142 42661581084 143 47054536703 144 51883025314 145 57188635464 146 63016781044 147 69417040362 148 76443526756 149 84155285954 150 92616729592 151 101898108116 152 112076018480 153 123233957282 154 135462923112 155 148862063928 156 163539381328 157 179612496634 158 197209474664 159 216469718814 160 237544943624 161 260600221028 162 285815115942 163 313384918844 164 343521972148 165 376457108332 166 412441209464 167 451746885610 168 494670293140 169 541533104599 170 592684628820 171 648504106086 172 709403192196 173 775828632274 174 848265152808 175 927238589274 176 1013319252640 177 1107125567568 178 1209328004484 179 1320653311071 180 1441889082252 181 1573888695798 182 1717576622712 183 1873954159111 184 2044105611896 185 2229204953162 186 2430522998192 187 2649435146634 188 2887429708736 189 3146116880740 190 3427238419104 191 3732678042884 192 4064472640716 193 4424824343630 194 4816113502556 195 5240912662211 196 5702001605834 197 6202383522846 198 6745302408608 199 7334261787177 200 7973044825630 201 8665735969900 202 9416744213908 203 10230828090094 204 11113122536948 205 12069167780472 206 13104940341976 207 14226886358845 208 15441957385770 209 16757648819056 210 18182041167520 211 19723844375345 212 21392445376100 213 23197959146788 214 25151283512392 215 27264157925462 216 29549226544632 217 32020105916612 218 34691457542976 219 37579065720384 220 40699921026000 221 44072309797806 222 47715910076532 223 51651894463860 224 55903040327804 225 60493847918499 226 65450666947372 227 70801832160894 228 76577808588672 229 82811347136198 230 89537651177784 231 96794554967398 232 104622714681812 233 113065812901328 234 122170777511782 235 131988016017919 236 142571666252456 237 153979864666836 238 166275033404252 239 179524187356636 240 193799262635440 241 209177467909202 242 225741660074622 243 243580745982288 244 262790111975404 245 283472083027714 246 305736413552048 247 329700812006002 248 355491501465232 249 383243818657812 250 413102854028060 251 445224135464116 252 479774358688576 253 516932167412552 254 556888986445288 255 599849911365126 256 646034658492110 257 695678579023660 258 749033741668256 259 806370088282855 260 867976667181376 261 934162949322490 262 1005260232798832 263 1081623141264692 264 1163631222552544 265 1251690654002176 266 1346236061299264 267 1447732458321556 268 1556677315836736 269 1673602767234582 270 1799077960287852 271 1933711564361232 272 2078154442912672 273 2233102502068218 274 2399299726570628 275 2577541414937330 276 2768677626737576 277 2973616855539722 278 3193329941740512 279 3428854240726788 280 3681298062608488 281 3951845400568370 282 4241760966312212 283 4552395552060670 284 4885191739510144 285 5241689977860252 286 5623535054164920 287 6032482980467705 288 6470408324119386 289 6939312009080835 290 7441329617474648 291 7978740222901878 292 8553975788736452 293 9169631166376582 294 9828474731056584 295 10533459694863924 296 11287736138740088 297 12094663808300668 298 12957825720765852 299 13881042632857750 300 14868388423089736 301 15924206444820716 302 17053126909521980 303 18260085363879543 304 19550342327877992 305 20929504164700652 306 22403545258161916 307 23978831577594022 308 25662145714531024 309 27460713481233748 310 29382232166126960 311 31434900546495100 312 33627450765455684 313 35969182186225644 314 38469997342975716 315 41140440115394100 316 43991736261208216 317 47035836448393250 318 50285461937967576 319 53754153076739998 320 57456320768277796 321 61407301101103580 322 65623413323184488 323 70122021362350968 324 74921599104866862 325 80041799656303369 326 85503528821406552 327 91329023054407918 328 97541932145356916 329 104167406922911346 330 111232192271330152 331 118764725776131464 332 126795242330469856 333 135355885054578330 334 144480822900389832 335 154206375334257319 336 164571144514482312 337 175616155403715964 338 187385004280880534 339 199924016145148536 340 213282411532082656 341 227512483291066564 342 242669783905843376 343 258813323972495524 344 276005782483434256 345 294313729604279228 346 313807862668832604 347 334563256157694047 348 356659626470967824 349 380181612350633822 350 405219071855673720 351 431867396845648646 352 460227845981517464 353 490407897308419462 354 522521621546742584 355 556690077280247587 356 593041729295790420 357 631712891401310548 358 672848195122149568 359 716601085753043420 360 763134347327577636 361 812620658153079159 362 865243178649678540 363 921196173331100729 364 980685668865882916 365 1043930150264249532 366 1111161297351468848 367 1182624763807157029 368 1258581001174939544 369 1339306130382056074 370 1425092863447578152 371 1516251478204350310 372 1613110849017800864 373 1716019536647700610 374 1825346940570494960 375 1941484517264521584 376 2064847068151187708 377 2195874101086022086 378 2335031269509262108 379 2482811893588863888 380 2639738567923817000 381 2806364860627582768 382 2983277108872542424 383 3171096316251147392 384 3370480157603544608 385 3582125097266606996 386 3806768627020487748 387 4045191630351949398 388 4298220880010231964 389 4566731676206403394 390 4851650633207361872 391 5153958622491940263 392 5474693881074574706 393 5814955294068644926 394 6175905861047387704 395 6558776356271414630 396 6964869193395705208 397 7395562505835588642 398 7852314454567377288 399 8336667775772840419 400 8850254581397354574 401 9394801426386491798 402 9972134657103538928 403 10584186056200290280 404 11232998800023116652 405 11920733745495067350 406 12649676064311388032 407 13422242243228753857 408 14240987470227705688 409 15108613427371570494 410 16027976512282730344 411 17002096511319189470 412 18034165748748964936 413 19127558737496805644 414 20285842358388750944 415 21512786596232672863 416 22812375862557943678 417 24188820936407383978 418 25646571556216848032 419 27190329697543930895 420 28825063573231043524 421 30556022394496319438 422 32388751933451308304 423 34329110929662065178 424 36383288385586577412 425 38557821798050482878 426 40859616375380946204 427 43295965292391603168 428 45874571038115014936 429 48603567914030742260 430 51491545743523015500 431 54547574856438873060 432 57781232415924794364 433 61202630158183290108 434 64822443619429024656 435 68651942928157933766 436 72703025244858437492 437 76988248935511452680 438 81520869569668662424 439 86314877838552359797 440 91385039493507556200 441 96746937410283255117 442 102417015890011079952 443 108412627313410553201 444 114752081270708988624 445 121454696296006974128 446 128540854341374971884 447 136032058132863283874 448 143950991557833912272 449 152321583240608716142 450 161169073471407626290 451 170520084661911621862 452 180402695509561121356 453 190846519061928745340 454 201882784882175293040 455 213544425526746399940 456 225866167557135928712 457 238884627318721464250 458 252638411731408547336 459 267168224349149230007 460 282516976958319762552 461 298729906998497569614 462 315854701103419961256 463 333941625074831062758 464 353043660617580388956 465 373216649180782790836 466 394519443267082767260 467 417014065590143462110 468 440765876479464913730 469 465843749951528248180 470 492320258887126350872 471 520271869776647207025 472 549779147518028521648 473 580926970776172961316 474 613804758437880557368 475 648506707722828348002 476 685132044538887364352 477 723785286699200895270 478 764576520648971364820 479 807621692381905891614 480 853042913259850536340 481 900968781484322893456 482 951534720005532898100 483 1004883331693172222130 484 1061164772633783826022 485 1120537144462008734312 486 1183166906677569779272 487 1249229309946531873754 488 1318908851434303200012 489 1392399753269149374204 490 1469906465288734418652 491 1551644193278522040441 492 1637839453969923375280 493 1728730658127927148304 494 1824568723122757193472 495 1925617716448045063338 496 2032155531719161094400 497 2144474598759898805362 498 2262882629463851318424 499 2387703401198651223558 500 2519277579606973641664 501 2657963582748047375584 502 2804138488617498052584 503 2958198988181893415004 504 3120562386167623898344 505 3291667651951871958676 506 3471976523016665001840 507 3661974663545650778991 508 3862172880867448536888 509 4073108402579512311202 510 4295346217322712372996 511 4529480482319496220555 512 4776136000937869054018 513 5035969773699894481240 514 5309672626317194661532 515 5597970918507407135410 516 5901628337525139080468 517 6221447780528925635200 518 6558273330102479838328 519 6912992327454576408330 520 7286537548037565024804 521 7679889484550250846076 522 8094078742527229651988 523 8530188553964102384930 524 8989357414686873722196 525 9472781851444849180320 526 9981719324989928189712 527 10517491275701975312130 528 11081486318630603480040 529 11675163595148736954875 530 12300056288753450597232 531 12957775312905558904430 532 13650013179171851202680 533 14378548054323546622970 534 15145248015452326639400 535 15952075512591887106576 536 16801092048779251962872 537 17694463087957073249674 538 18634463201606608101364 539 19623481465512051649950 540 20664027118591510283664 541 21758735496289047135398 542 22910374251607099366740 543 24121849877470395330860 544 25396214544752355101252 545 26736673270964176569370 546 28146591435306797206072 547 29629502656517906020013 548 31189117050711676847164 549 32829329887209496468494 550 34554230661197080250496 551 36368112602918723060046 552 38275482644034830550792 553 40281071862725935992644 554 42389846430127080377988 555 44607019081722766274829 556 46938061138426547797540 557 49388715103212901438742 558 51965007860364656686856 559 54673264505649081716314 560 57520122837042226047244 561 60512548536986950297932 562 63657851078597662167844 563 66963700389716972204967 564 70438144310289265205384 565 74089626880146344010260 566 77927007496004067648456 567 81959580978249655845410 568 86197098589960257230084 569 90649790052538136328464 570 95328386604380256783504 571 100244145151123769023539 572 105408873558228096516216 573 110834957138973299036212 574 116535386393377332990480 575 122523786056066429303611 576 128814445513777990129698 577 135422350655938911175074 578 142363217224649395965330 579 149653525733418718504194 580 157310558027150420403120 581 165352435559166137388712 582 173798159464495956888496 583 182667652512255075286392 584 191981803023678394852812 585 201762510846303734919978 586 212032735478887545795840 587 222816546445912162795504 588 234139176025008830123712 589 246027074435283945133020 590 258507967599406009013360 591 271610917597396803616888 592 285366385935381428711140 593 299806299758097981671678 594 314964121139759242036448 595 330874919593906062676583 596 347575447949206538754988 597 365104221744748199983848 598 383501602305254185440328 599 402809883663841376009887 600 423073383507442107318488 601 444338538327844694645580 602 466654002969486019578540 603 490070754773666944218162 604 514642202527773465536704 605 540424300437389655235462 606 567475667348899624125136 607 595857711460312178951874 608 625634760768622013567920 609 656874199513064515063452 610 689646610885147052779864 611 724025926288368897626889 612 760089581443096547033996 613 797918679645163302284594 614 837598162500435152562456 615 879216988471854085699698 616 922868319590359915376408 617 968649716696629386688650 618 1016663343596784653938952 619 1067016180532140597299450 620 1119820247380712164043600 621 1175192837026620594772264 622 1233256759352753175485744 623 1294140596332079306062329 624 1357978968713941927148496 625 1424912814823464107416811 626 1495089682014974592217772 627 1568664031344103739086394 628 1645797556047973727768164 629 1726659514448748004458448 630 1811427077922760238396880 631 1900285694605559271264504 632 1993429469532533085917912 633 2091061561945363269465198 634 2193394600526464557284236 635 2300651117356837694081530 636 2413064001427466273279448 637 2530876972570579086387147 638 2654345076714841938096240 639 2783735203407902629839182 640 2919326626590757346726632 641 3061411569651207264505038 642 3210295795828305083645088 643 3366299225086228647533312 644 3529756578624543268116840 645 3701018052242409693611788 646 3880450019827046967941464 647 4068435768291759567093760 648 4265376265346180765154370 649 4471690961541166508997648 650 4687818628093098654990570 651 4914218232057330002670258 652 5151369850488236061132160 653 5399775625293945542202698 654 5659960760567423631279668 655 5932474564252303233896904 656 6217891536081830079240372 657 6516812503812643630306122 658 6829865809861997267182576 659 7157708550547575293122990 660 7501027870223444160678832 661 7860542312704038974040122 662 8237003232470599682013640 663 8631196268261307159016739 664 9043942881757705873424528 665 9476101964196024077520184 666 9928571513852909121379052 667 10402290387481085680253462 668 10898240128901729175896336 669 11417446878097144893491132 670 11960983364289881981050504 671 12529970986642928193796164 672 13125581986370373155394420 673 13749041714209150638853852 674 14401630997370441529022332 675 15084688610264317243624268 676 15799613853473516504724062 677 16547869245642177900842354 678 17330983333143210366956144 679 18150553622594098079656985 680 19008249641505644782631572 681 19905816132571818476845376 682 20845076387341826312891312 683 21827935725258213625308648 684 22856385124297538056011640 685 23932505009713431339134092 686 25058469207656057823654756 687 26236549070727557852660348 688 27469117782830489255613572 689 28758654850976035688283206 690 30107750792041340159483192 691 31519112022801267622418822 692 32995565961909746873280356 693 34540066352870156023551596 694 36155698817413584740157920 695 37845686649098843288266276 696 39613396857359430804404616 697 41462346472650983912641068 698 43396209123798691274423136 699 45418821899108497077567203 700 47534192503289370090769024 701 49746506722737260113802498 702 52060136212255406841579092 703 54479646616831243252539229 704 57009806042658118401128288 705 59655593892181359525876646 706 62422210078563740591974740 707 65315084635606203726871276 708 68339887739826710488846704 709 71502540162094438147454282 710 74809224166939283495355288 711 78266394878408938298075004 712 81880792132128843876865020 713 85659452834035355028087208 714 89609723847100732148527220 715 93739275428251469496065020 716 98056115238600347220235252 717 102568602951068910475790868 718 107285465480472329750229112 719 112215812862174344019032280 720 117369154806497855758649292 721 122755417957198418075244652 722 128384963883475082800709038 723 134268607836207687122117672 724 140417638300373536103963732 725 146843837376911558141543574 726 153559502028670416306226432 727 160577466226500873773145664 728 167911124033034146109940784 729 175574453663229324091090979 730 183582042562376601059925832 731 191949113543911469059543431 732 200691552031130835698656592 733 209825934448707833617498006 734 219369557811780729682846872 735 229340470562345683898389518 736 239757504704716159543560376 737 250640309293926668673060176 738 262009385333158495324813196 739 273886122138553439315077630 740 286292835232161968649212116 741 299252805826248097331901500 742 312790321964748593882914040 743 326930721390362701801026870 744 341700436208534497220758768 745 357127039422487555638370840 746 373239293416485152649519332 747 390067200467623358193335586 748 407642055369723847518214472 749 425996500256282981722524040 750 445164581712958834661835900 751 465181810273743683189542499 752 486085222398781567257051232 753 507913445035754612892424220 754 530706762870883859000545508 755 554507188379876538710101623 756 579358534793608577892033608 757 605306492097965170850126398 758 632398706192080622909621080 759 660684861334228426814530954 760 690216766009821251917331792 761 721048442361395953835254930 762 753236219326088939239869320 763 786838829631960632381694397 764 821917510810613102130641104 765 858536110389871171397218404 766 896761195436873936862477628 767 936662166628760335057153763 768 978311377035239334940704236 769 1021784255804723033311082962 770 1067159436953380303460711808 771 1114518893464451044299119011 772 1163948076913458269078217996 773 1215536062843579489738292446 774 1269375702124402792788160280 775 1325563778536609841896868044 776 1384201172834811468029021716 777 1445393033550825730112952766 778 1509248954810148092930816756 779 1575883161445233989192738004 780 1645414701700511408961174956 781 1717967647835781789185459856 782 1793671304946868492683262600 783 1872660428335051355680586572 784 1955075449770001600780722058 785 2041062713004623022637189012 786 2130774718914432650084549392 787 2224370380648897711638306222 788 2322015289197507113779630468 789 2423881989789317029619698780 790 2530150269561294670552968456 791 2641007456948015840173104522 792 2756648733263175321146859176 793 2877277456961970327585782442 794 3003105501092742959103327356 795 3134353604466345623336624382 796 3271251737092552597879393280 797 3414039480454511226375816774 798 3562966423214738764301155680 799 3718292572969557847943815246 800 3880288784693158421643808094 801 4049237206537711451973943450 802 4225431743682175910012767172 803 4409178540949672708065575152 804 4600796484941586337106358680 805 4800617726465937116734523664 806 5008988224068086015740266520 807 5226268309503533274118484852 808 5452833276025496519059084092 809 5689073990394150379780775644 810 5935397529549926182153043664 811 6192227842930157360778678118 812 6460006441446665874460649928 813 6739193114181671214401283316 814 7030266673900722628777183768 815 7333725732524265138936777772 816 7650089507744011154791149812 817 7979898662016564617297310160 818 8323716175214798563550718388 819 8682128252267387210711802852 820 9055745267168709976517458648 821 9445202744795149804669689854 822 9851162382019676955367690648 823 10274313109674620056207562796 824 10715372196972759607331683352 825 11175086400059419231008514472 826 11654233156433163792424033680 827 12153621827040131389483590762 828 12674094987917021765963825536 829 13216529773330434059810180870 830 13781839272435692693196881112 831 14370973981556626118966361956 832 14984923314269077394885505066 833 15624717171555340530528070794 834 16291427574384348773873783504 835 16986170361163411308021697616 836 17710106952601728533991717664 837 18464446186623943182199241944 838 19250446226073739670569301920 839 20069416542053127156399823066 840 20922719975852677520272891744 841 21811774882541788314730979653 842 22738057359406158311372522192 843 23703103562542261238518069976 844 24708512115045849106277942516 845 25755946610363583845241923598 846 26847138214513964914995721680 847 27983888371025977754828075364 848 29168071612591527024461100388 849 30401638483580940209825508172 850 31686618577729839396847565332 851 33025123695470697556681837694 852 34419351125553644171999730088 853 35871587055778795285591794470 854 37384210117846795413342059696 855 38959695071525622389835267339 856 40600616633530279371351853864 857 42309653456718048653191689774 858 44089592265415787214001971768 859 45943332152917591659794314000 860 47873889047421348728280497280 861 49884400352911525855544229548 862 51978129771743364897825390276 863 54158472315940753059965763152 864 56428959514486802650173549688 865 58793264824162932233163880176 866 61255209251779375898001462156 867 63818767195937937978855843570 868 66488072516776854888302219088 869 69267424842468235452481568712 870 72161296121571152967042182192 871 75174337430688498307158036109 872 78311386047233632109808927784 873 81577472797484170240862565162 874 84977829690485392623641640368 875 88517897848765291092205774731 876 92203335747237695800984664368 877 96040027772099789571458977654 878 100034093111976202965197840752 879 104191894994024367983349000190 880 108520050278195504515837257104 881 113025439423343152494823677548 882 117715216839387198487991638398 883 122596821640276556168301288861 884 127677988813048748220526666548 885 132966760818860330671070546960 886 138471499642459153484194463488 887 144200899307188644928806975076 888 150163998873256451244493223012 889 156370195937665696235916892628 890 162829260654897716569019215512 891 169551350298151277997744229252 892 176547024381685918158469727696 893 183827260365587159165874025048 894 191403469965069889015700898520 895 199287516087264261681195731738 896 207491730419287086008150942428 897 216028931692291975876090132932 898 224912444647114671315541239468 899 234156119728087106463602983472 900 243774353532586232336019489734 901 253782110044912581625737178348 902 264194942684160416278362078144 903 275029017196847401144428494256 904 286301135426218522431247052436 905 298028759991327892817047849344 906 310230039910234683530817620556 907 322923837202927279582544654101 908 336129754510914506352920917032 909 349868163771796121136955552294 910 364160235988548459731559243636 911 379027972134736996260284863320 912 394494235238397499551011702272 913 410582783688913404086829830096 914 427318305812860979999710990580 915 444726455766497978936852363260 916 462833890794337819549755739412 917 481668309905082303675636759156 918 501258494018083647693412710952 919 521634347635473681339917888029 920 542826942097136902360094588312 921 564868560477817262180665975320 922 587792744187838769380403777104 923 611634341341190003025996975153 924 636429556957075294071771634048 925 662216005063473628660378463686 926 689032762773773326196099858056 927 716920426410169430214462587946 928 745921169750224816642930393748 929 776078804475808683957458432970 930 807438842906540875543855014592 931 840048563102891053609816936026 932 873957076427211882847987711408 933 909215397654229011002863441044 934 945876517725871811115696238536 935 983995479248811778304449723451 936 1023629454836684502422392529114 937 1064837828402710770009199926302 938 1107682279512307246469704098040 939 1152226870909292178397896510183 940 1198538139333451632195372793308 941 1246685189751542120200459011662 942 1296739793128271412871388764144 943 1348776487868426436655216648054 944 1402872685066111148253204373704 945 1459108777702024094706445544130 946 1517568253934851161034491169696 947 1578337814638180134694453749560 948 1641507495339866763584360250520 949 1707170792726503767096188707022 950 1775424795881571832061453558720 951 1846370322431992288568502862326 952 1920112059784162471277468492252 953 1996758711637144551164520375264 954 2076423149967504965233278346548 955 2159222572687372855127521201186 956 2245278667184610820009545344560 957 2334717779961578767548110196592 958 2427671092596830995523817943828 959 2524274804262227465603910255400 960 2624670321036372485598350227696 961 2729004452264027988904244082787 962 2837429614220194940463710497884 963 2950104041346926128907309197180 964 3067192005340638129710778767060 965 3188864042377741346155223817152 966 3315297188776816966110738771080 967 3446675225406351050075747066190 968 3583188931158201865604342321242 969 3725036345818540535509396739608 970 3872423042679981071937433092000 971 4025562411251018411369919266385 972 4184675950431737135061174387752 973 4349993572538054663165962476204 974 4521753918570536894138791001016 975 4700204685138088124996526955662 976 4885602963461587808508829811948 977 5078215590897842050619701448974 978 5278319515440056110437639379336 979 5486202173667434556592544563882 980 5702161882633497835769358089420 981 5926508246200288179733893333714 982 6159562576343845076987909205296 983 6401658329975182752194244912188 984 6653141561840521770268600426736 985 6914371394084737329290620899182 986 7185720503082912147739118340592 987 7467575624166547038684055738679 988 7760338074893413107370589303616 989 8064424297533252708658078360856 990 8380266421465579475307866756304 991 8708312846210719445225207497822 992 9049028845841005125805557053648 993 9402897195545712802351928018388 994 9770418821150952140748918438464 995 10152113472424308853456750644818 996 10548520421023639715971725515880 997 10960199183980059521899453017314 998 11387730273636877832113294810960 999 11831715974999077030702503889678 1000 12292781151481910953110939793308