-1 1 0 2 1 3 2 4 3 7 4 10 5 17 6 22 7 32 8 44 9 62 10 80 11 112 12 144 13 193 14 248 15 323 16 410 17 530 18 664 19 845 20 1054 21 1324 22 1634 23 2037 24 2498 25 3082 26 3760 27 4601 28 5580 29 6789 30 8186 31 9891 32 11876 33 14271 34 17052 35 20393 36 24260 37 28876 38 34224 39 40557 40 47888 41 56540 42 66516 43 78240 44 91760 45 107560 46 125748 47 146943 48 171288 49 199555 50 231984 51 269496 52 312466 53 362051 54 418722 55 483935 56 558384 57 643806 58 741164 59 852637 60 979452 61 1124330 62 1288926 63 1476531 64 1689354 65 1931477 66 2205700 67 2517087 68 2869300 69 3268490 70 3719376 71 4229569 72 4805016 73 5455092 74 6187392 75 7013321 76 7942528 77 8989044 78 10164878 79 11487267 80 12971326 81 14638017 82 16506252 83 18601703 84 20947784 85 23575862 86 26515058 87 29803447 88 33477134 89 37582524 90 42163976 91 47277997 92 52979260 93 59336183 94 66415934 95 74301596 96 83075234 97 92837544 98 103688916 99 115750940 100 129146112 101 144021488 102 160525852 103 178836789 104 199135160 105 221634716 106 246554832 107 274153003 108 304694416 109 338488821 110 375856750 111 417169925 112 462815084 113 513238362 114 568905096 115 630350052 116 698132974 117 772893544 118 855303924 119 946129178 120 1046174734 121 1156354470 122 1277632884 123 1411099765 124 1557908516 125 1719358067 126 1896825104 127 2091856178 128 2306093340 129 2541375115 130 2799657532 131 3083125011 132 3394103902 133 3735186800 134 4109138264 135 4519031299 136 4968147412 137 5460126532 138 5998858300 139 6588649911 140 7234108116 141 7940323549 142 8712746316 143 9557388723 144 10480690692 145 11489746227 146 12592158528 147 13796288902 148 15111104912 149 16546454225 150 18112901648 151 19822035025 152 21686290856 153 23719290968 154 25935661196 155 28351402425 156 30983697836 157 33851326600 158 36974460074 159 40375117891 160 44076958200 161 48105780948 162 52489307644 163 57257742784 164 62443543952 165 68082041403 166 74211205844 167 80872333106 168 88109804716 169 95971851394 170 104510308556 171 113781460719 172 123845800960 173 134768965482 174 146621493106 175 159479868197 176 173426283816 177 188549796754 178 204946107140 179 222718839117 180 241979333740 181 262848078683 182 285454521216 183 309938654687 184 336450868580 185 365153710392 186 396221772384 187 429843660111 188 466221926884 189 505575261484 190 548138494272 191 594165031232 192 643926934896 193 697717645916 194 755852156908 195 818670042843 196 886535760866 197 959842026802 198 1039010251772 199 1124494320939 200 1216781194696 201 1316395122388 202 1423898454896 203 1539896347307 204 1665037804444 205 1800020947476 206 1945594335980 207 2102562849665 208 2271789352530 209 2454201265554 210 2650792612188 211 2862631385696 212 3090862040822 213 3336713732074 214 3601503346216 215 3886644719537 216 4193652275966 217 4524151364984 218 4879882603360 219 5262713448562 220 5674643377764 221 6117816849614 222 6594529424864 223 7107242312880 224 7658589579136 225 8251394444290 226 8888677770208 227 9573676329578 228 10309852731432 229 11100915933012 230 11950832819252 231 12863851203485 232 13844513332964 233 14897681686775 234 16028554653208 235 17242695503682 236 18546050555028 237 19944981675127 238 21446287319384 239 23057239006644 240 24785605595988 241 26639694259669 242 28628378455976 243 30761143914209 244 33048120855868 245 35500135610517 246 38128747628320 247 40946307462844 248 43965999231986 249 47201905704654 250 50669056996248 251 54383503635678 252 58362372286328 253 62623947820842 254 67187737013480 255 72074560675239 256 77306626431450 257 82907632150787 258 88902848956772 259 95319237387829 260 102185541992830 261 109532421716702 262 117392557657464 263 125800799415599 264 134794287663268 265 144412618462387 266 154697982570416 267 165695349844277 268 177452627507248 269 190020867078250 270 203454443961438 271 217811289701473 272 233153095621988 273 249545573390104 274 267058685838040 275 285766939258411 276 305749644764732 277 327091246218594 278 349881615981740 279 374216422671966 280 400197465704856 281 427933087659903 282 457538552363560 283 489136507299230 284 522857410649976 285 558840049630758 286 597232022652970 287 638190320253014 288 681881869070280 289 728484182921461 290 778185976192880 291 831187893278072 292 887703199987384 293 947958600636062 294 1012195016864974 295 1080668502857076 296 1153651122191264 297 1231431972631915 298 1314318173004384 299 1402636010459610 300 1496732050500168 301 1596974421230692 302 1703754061337312 303 1817486157229670 304 1938611545629216 305 2067598321475838 306 2204943413421272 307 2351174382563286 308 2506851191407608 309 2672568215467886 310 2848956228781450 311 3036684653091712 312 3236463785321810 313 3449047312015995 314 3675234807264900 315 3915874542871122 316 4171866288638524 317 4444164452351246 318 4733781217603594 319 5041790051707558 320 5369329220427166 321 5717605705815652 322 6087899141866840 323 6481566189207545 324 6900044940223906 325 7344859802979776 326 7817626430068210 327 8320057169532431 328 8853966577987892 329 9421277502985532 330 10024027247261792 331 10664374354368817 332 11344605498615292 333 12067143053244592 334 12834552789170316 335 13649552314012258 336 14515019671426200 337 15434002749288542 338 16409728881864976 339 17445615335694548 340 18545280028390532 341 19712553212974315 342 20951489439046992 343 22266380569825937 344 23661769125542590 345 25142462781464230 346 26713549248995536 347 28380412419455757 348 30148748954681904 349 32024586259547235 350 34014300972938928 351 36124638971150309 352 38362735971179886 353 40736139789352514 354 43252833291134228 355 45921259153905853 356 48750345423197936 357 51749533054548536 358 54928804364477676 359 58298713656310799 360 61870418884402176 361 65655715701859215 362 69667072691159080 363 73917669206966369 364 78421434564509420 365 83193090090942828 366 88248192703736980 367 93603181628479340 368 99275426846070380 369 105283280982487616 370 111646133154949872 371 118384466593239190 372 125519918470177546 373 133075343873723423 374 141074882269587252 375 149544028507531563 376 158509706632835114 377 168000348682694563 378 178045976637573676 379 188678289843509353 380 199930755978080304 381 211838708020737210 382 224439445200390784 383 237772340532901605 384 251878952817115234 385 266803145865513456 386 282591212727509836 387 299292007855074025 388 316957084855437960 389 335640842963125220 390 355400679758032954 391 376297153458054698 392 398394152188037596 393 421759073762174886 394 446463013253993112 395 472580962110646483 396 500192015953030080 397 529379595054434819 398 560231674499288208 399 592841028265685865 400 627305484090648448 401 663728193626401203 402 702217914598885248 403 742889309761064799 404 785863259196850032 405 831267191070705315 406 879235427221052584 407 929909549011832247 408 983438779677576748 409 1039980388919370874 410 1099700115816561060 411 1162772616176819175 412 1229381930217167696 413 1299721977084622900 414 1373997071932190040 415 1452422472473541193 416 1535224950547701072 417 1622643396058943330 418 1714929448638095864 419 1812348164858128274 420 1915178716161290560 421 2023715125833073434 422 2138267039984517682 423 2259160541413868948 424 2386739001114226520 425 2521363976865993692 426 2663416153483611600 427 2813296334765402168 428 2971426481513354140 429 3138250806322714967 430 3314236919308913214 431 3499877036162622644 432 3695689242501211848 433 3902218826649888600 434 4120039674618361412 435 4349755740199373888 436 4592002583759388054 437 4847448993490620580 438 5116798682502800872 439 5400792076429792396 440 5700208184737946786 441 6015866571379834658 442 6348629417800715892 443 6699403694972096809 444 7069143437289019200 445 7458852136113691924 446 7869585245637210388 447 8302452820027751321 448 8758622274391198444 449 9239321289776263574 450 9745840854620485976 451 10279538464228437590 452 10841841470562438188 453 11434250605392795740 454 12058343669000815916 455 12715779409034915358 456 13408301581652557104 457 14137743221219883766 458 14906031110665713252 459 15715190480553441553 460 16567349928973911068 461 17464746592237161850 462 18409731558513336904 463 19404775556461626948 464 20452474911084312350 465 21555557801055866059 466 22716890809911736988 467 23939485807712162551 468 25226507155773399540 469 26581279273629479052 470 28007294561085033034 471 29508221717257938582 472 31087914449825744244 473 32750420619304749887 474 34499991812015619512 475 36341093389721885623 476 38278415010123607240 477 40316881669585781276 478 42461665262930264828 479 44718196715309334429 480 47092178681757736510 481 49589598873364164080 482 52216744006553441852 483 54980214438639399933 484 57886939487195710964 485 60944193500933629548 486 64159612680858374288 487 67541212724278113544 488 71097407291838502348 489 74837027375414721177 490 78769341568654321680 491 82904077323652638227 492 87251443197404796180 493 91822152177612939470 494 96627446093587153120 495 101679121208385670528 496 106989555000322049484 497 112571734237047864720 498 118439284353039923468 499 124606500241325602370 500 131088378473308544650 501 137900651065746875090 502 145059820812173396886 503 152583198306656707073 504 160488940681039107104 505 168796092193105011168 506 177524626691110108308 507 186695492102429640261 508 196330656976573872248 509 206453159241430184603 510 217087157208357024908 511 228257982996983016108 512 239992198421313140372 513 252317653520937777414 514 265263547785615406820 515 278860494270977146553 516 293140586661034606318 517 308137469490318944833 518 323886411589540590144 519 340424382983877912914 520 357790135316903380116 521 376024286046817354369 522 395169406498096086664 523 415270114034210543461 524 436373168445674701344 525 458527572839587324472 526 481784679137272784782 527 506198298488318537349 528 531824816721247755822 529 558723315163060212039 530 586955696962899839636 531 616586819277944711875 532 647684631473358976288 533 680320319722329563276 534 714568458176291328320 535 750507167121570738337 536 788218278312632885208 537 827787507930812231366 538 869304637380826765964 539 912863702409226894794 540 958563190781388262052 541 1006506249039357848480 542 1056800898603843702658 543 1109560261783913042903 544 1164902797987011689220 545 1222952550737451880057 546 1283839405828157232356 547 1347699361262050502288 548 1414674809343133655712 549 1484914831625812109840 550 1558575507121195534768 551 1635820234525316165945 552 1716820068910378348500 553 1801754073705000993012 554 1890809688450949038408 555 1984183113228316368133 556 2082079710287461180244 557 2184714423851016478866 558 2292312218679863817028 559 2405108538443620352637 560 2523349784550289131796 561 2647293816559164296674 562 2777210474898105967132 563 2913382127099618001823 564 3056104238349476780034 565 3205685967660118086206 566 3362450790541840017156 567 3526737149589806842595 568 3698899133946560313956 569 3879307189172426263870 570 4068348858578111408328 571 4266429557675694602686 572 4473973382905489810228 573 4691423956428945088930 574 4919245308257663137400 575 5157922797653603408110 576 5407964075193358297060 577 5669900087588379616654 578 5944286126787894364588 579 6231702925626052842732 580 6532757801685978966474 581 6848085851825792393992 582 7178351199198279081944 583 7524248295407896857207 584 7886503279809952411168 585 8265875398810527422036 586 8663158487360616708888 587 9079182515735503999392 588 9514815203998199697264 589 9970963707489510886218 590 10448576375967041769188 591 10948644590007839630390 592 11472204677540221643856 593 12020339914413871564285 594 12594182612138361697460 595 13194916297017719427858 596 13823777984098953211378 597 14482060550506751410724 598 15171115211895244195852 599 15892354106961764592543 600 16647252994093752734992 601 17437354065497004860380 602 18264268883246180013900 603 19129681443041990168919 604 20035351370517880949116 605 20983117256352426324368 606 21974900135466887436496 607 23012707117074553788963 608 24098635171335550118376 609 25234875079935776525668 610 26423715556858770497252 611 27667547547266168422269 612 28968868711314862082568 613 30330288101472287484181 614 31754531040765055043786 615 33244444211220730775891 616 34803000960597022127540 617 36433306837413339627340 618 38138605363094183600488 619 39922284052056024854978 620 41787880689323040656008 621 43739089877386485191106 622 45779769862734867123584 623 47913949654724505584306 624 50145836448130686620244 625 52479823363081413395441 626 54920497514704034539724 627 57472648427302943286198 628 60141276806472215675224 629 62931603685167999119100 630 65849079958308371840224 631 68899396323229972528393 632 72088493641830533868110 633 75422573743136720585809 634 78908110683493551058228 635 82551862484638879455792 636 86360883368340608181876 637 90342536509507489690793 638 94504507328056022583734 639 98854817343224731903701 640 103401838612356869899040 641 108154308779766825076026 642 113121346759594233267204 643 118312469080340324273282 644 123737606917029469207480 645 129407123840937203432171 646 135331834315035532450656 647 141523022967524248897920 648 147992464673989286835868 649 154752445483179625706638 650 161815784419530947078712 651 169195856200261051957333 652 176906614902965489119688 653 184962618624599201472288 654 193379055170802941146786 655 202171768819766649811564 656 211357288202867234100224 657 220952855349844210159052 658 230976455944297886898740 659 241446850841130538088906 660 252383608895552361507578 661 263807141159438215206950 662 275738736498806956155586 663 288200598692707664271170 664 301215885071772762623748 665 314808746761579442119684 666 329004370593932506283024 667 343829022756454575639027 668 359310094248843648889760 669 375476148221846193544274 670 392356969272978019277864 671 409983614781153693250050 672 428388468360387921343948 673 447605295521328284513277 674 467669301627408997484140 675 488617192241507661695872 676 510487235957055492047088 677 533319329817170371752390 678 557155067423500594451956 679 582037809846645380954674 680 608012759448199235355460 681 635127036735239710139798 682 663429760366336014525352 683 692972130439559321352041 684 723807515191326276723264 685 755991541246981238320092 686 789582187562483116878384 687 824639883209349612969318 688 861227609153600980174264 689 899411004192989730955891 690 939258475215542220267020 691 980841311956787803853982 692 1024233806431963572501644 693 1069513377234689205494120 694 1116760698892717096419188 695 1166059836487480272538175 696 1217498385743497486202582 697 1271167618810781458665520 698 1327162635962989228166768 699 1385582523452171702361531 700 1446530517760862047967584 701 1510114176511458008609105 702 1576445556293061859808506 703 1645641397686325478917803 704 1717823317767421805659536 705 1793118010393891831816277 706 1871657454576098735092320 707 1953579131260972835243506 708 2039026248856169599966396 709 2128147977847125606640317 710 2221099694861442770470660 711 2318043236560896712869226 712 2419147163743873607118540 713 2524587036068505964151378 714 2634545697809910464518792 715 2749213575094102917288712 716 2868788985054987788868016 717 2993478457391810030072070 718 3123497068809041228779250 719 3259068790853599917951036 720 3400426851669730512906156 721 3547814112226859077927756 722 3701483457582093231236276 723 3861698203776230344729482 724 4028732520969504119636954 725 4202871873462845187356842 726 4384413477258914250654292 727 4573666775859217303802994 728 4770953935003319734985432 729 4976610357100900108284937 730 5190985216118433690997216 731 5414442013729870712972268 732 5647359157553192962643492 733 5890130562345349633776348 734 6143166275042198008304024 735 6406893124583938934683103 736 6681755397482417001164084 737 6968215540143984380931436 738 7266754888979423931226792 739 7577874429393454940495310 740 7902095584766231467171184 741 8239961036604220001424558 742 8592035577060008380601216 743 8958906995089789955577586 744 9341186997541914763824560 745 9739512166543593040938465 746 10154544954580185655111632 747 10586974718740017240500560 748 11037518795627936505605060 749 11506923618534482992686720 750 11995965878481004608577854 751 12505453730850188888852162 752 13036228049348428170647020 753 13589163729141415945761567 754 14165171041045100315780496 755 14765197038755355218021654 756 15390227021144553011679480 757 16041286051761143128082510 758 16719440537717605281325928 759 17425799870267211826441232 760 18161518129424114006247576 761 18927795855103966872066338 762 19725881887321608941128256 763 20557075278113171592990093 764 21422727277914950129388480 765 22324243399270947857623024 766 23263085560812087233083576 767 24240774314598981093607671 768 25258891159997871866284616 769 26319080947418208104794398 770 27423054375325218320385860 771 28572590584110353884573160 772 29769539850495126551854248 773 31015826386324762349919292 774 32313451245709142910184764 775 33664495344661573425661554 776 35071122597496040003681076 777 36535583174449701830725844 778 38060216885117294045214544 779 39647456692504113903017593 780 41299832362634788495834624 781 43019974254889897780796090 782 44810617258384493436392112 783 46674604879953340643968031 784 48614893489462029983671538 785 50634556728430906589128524 786 52736790088126418163695752 787 54924915663560478722985529 788 57202387090020486265899092 789 59572794669058087795096339 790 62039870691062347446571598 791 64607494961869239395512194 792 67279700541073689583252876 793 70060679700058914874178042 794 72954790107990158267511120 795 75966561254392251282105599 796 79100701117182240194431716 797 82362103085426108285098338 798 85755853146361399985990976 799 89287237346652585030412320 800 92961749538141364811657608 801 96785099418808289905479736 802 100763220879981757592299668 803 104902280671315787186520339 804 109208687395403881067410616 805 113689100844414943103536288 806 118350441691511356237547278 807 123199901550363644062826028 808 128244953416480652346482160 809 133493362504666652597309984 810 138953197497353981810744264 811 144632842219193102474396527 812 150541007753754366710703300 813 156686745018872688717359733 814 163079457817676589692998112 815 169728916383066691990182997 816 176645271433959727256456364 817 183839068762387686056748710 818 191321264371136526001694480 819 199103240182435853473800844 820 207196820338852886243997544 821 215614288118428162300295669 822 224368403486782996173541008 823 233472421309873990252609710 824 242940110251816882648691140 825 252785772383212733631167100 826 263024263526214938165141432 827 273671014363656246128593214 828 284742052340423336623168408 829 296254024386422041426480442 830 308224220491412236040659252 831 320670598163227040598544564 832 333611807801899475847373138 833 347067219023540997911242338 834 361056947968902800329860788 835 375601885632963676971346986 836 390723727253058430738904856 837 406445002794571731523953503 838 422789108574482427742773036 839 439780340064659073563753807 840 457443925918164070253738468 841 475806063263551721570423503 842 494893954313605769966179916 843 514735844336809836689405751 844 535361061041415693135504112 845 556800055423950449673981664 846 579084444135694639140442756 847 602247053422776565033013658 848 626321964697347286564356022 849 651344561799560789342312902 850 677351580012040353999404704 851 704381156890929300875837926 852 732472884979728227880858548 853 761667866474705930530904582 854 792008769912933326177144264 855 823539888956754353759359920 856 856307203350939630731227760 857 890358442131725347431099927 858 925743149169553661808049056 859 962512751130492944262878300 860 1000720627944125134483837940 861 1040422185869069206190885548 862 1081674933250327868491260260 863 1124538559066261249559709933 864 1169075014366233745012295006 865 1215348596703848005361132154 866 1263426037674162914848571680 867 1313376593667428794482121376 868 1365272139955613658714723968 869 1419187268232417929113432575 870 1475199387731491812657179966 871 1533388830052300210630311683 872 1593838957827392813063215696 873 1656636277369896033850004296 874 1721870555444673383112642144 875 1789634940312010925043195115 876 1860026087197654209696074640 877 1933144288348808445583313231 878 2009093607841047437930775596 879 2087982021307263461735986155 880 2169921560765513929090782668 881 2255028464729236328810345338 882 2343423333789444256953482680 883 2435231291865591563022059899 884 2530582153328380263965426700 885 2629610596205352310674075530 886 2732456341687172908416727360 887 2839264340160601544532653203 888 2950184964001727383588073104 889 3065374207371694271198883468 890 3184993893265270224680402540 891 3309211888071863572814711350 892 3438202323917305430034977624 893 3572145829064605373224982226 894 3711229766661234031867032094 895 3855648482131057396280106516 896 4005603559519068094293120016 897 4161304087108360900734231562 898 4322966932639541138668456344 899 4490817028474837763036029770 900 4665087667060705866209365984 901 4846020807055621214964428098 902 5033867390502108007065134464 903 5228887671435850906701955578 904 5431351556337964427243867568 905 5641538956851255741202215555 906 5859740155195484203327490580 907 6086256182732402321655755985 908 6321399212146541302890807736 909 6565492963724573906838284984 910 6818873126232347439399827048 911 7081887792906711913541752071 912 7354897913096685545200606824 913 7638277760107774022802330490 914 7932415415821914643534445280 915 8237713272686117606424928864 916 8554588553682854900951931608 917 8883473850917265925576737288 918 9224817683477642450344833524 919 9579085075249188432002446893 920 9946758153383957077819621348 921 10328336768155017868638294087 922 10724339134947431307577550872 923 11135302499165487059699175180 924 11561783824861916248761898148 925 12004360507923511756681418256 926 12463631114675694972683123764 927 12940216146799261206735649607 928 13434758833482617651527589196 929 13947925951765626163785673382 930 14480408676063358079798098476 931 15032923457893114227016003244 932 15606212936862516917762827438 933 16201046884013926753098756750 934 16818223178657304616070575714 935 17458568819863648119015286098 936 18122940973830578974413892304 937 18812228058374403156559450286 938 19527350865845169466902746704 939 20269263725806919321295744177 940 21038955708870469683460538520 941 21837451873114857756121386769 942 22665814554581872034186834040 943 23525144703380211396311214366 944 24416583266987471849014931460 945 25341312622393832981404376576 946 26300558058786565590225898356 947 27295589312533949733183982933 948 28327722156286278251350588726 949 29398320044075139954428182532 950 30508795814355360141732735312 951 31660613453001819692816513349 952 32855289918340933967747773704 953 34094397030369031935478372483 954 35379563426382109963166753800 955 36712476585318820090432121188 956 38094884923195777976343140444 957 39528599962096918544124519861 958 41015498575261182608008662066 959 42557525310901071254993601602 960 44156694797472851033236254972 961 45815094233213433795047704378 962 47534885962853277504659784592 963 49318310144515284046719420414 964 51167687509910479539255987178 965 53085422221048709508512607680 966 55074004826790315896297233016 967 57136015322679483407044783505 968 59274126317615069684752637624 969 61491106311037214769110471136 970 63789823084431042888861522708 971 66173247211079529903109486595 972 68644455688129049227290380160 973 71206635695170701769631611336 974 73863088483680963307840141600 975 76617233401814197482855078480 976 79472612059189602840434794700 977 82432892636474227605993345395 978 85501874344723942384240844420 979 88683492039614046589093930702 980 91981820995862363574792375142 981 95401081847328899328504000788 982 98945645698458973138381045862 983 102620039412930143630161096687 984 106428951085558521475579649384 985 110377235703726480952004417630 986 114469921004802316112540675508 987 118712213536242678109089801919 988 123109504925291315504953208560 989 127667378365422720732997452282 990 132391615326917067157351232884 991 137288202499203674019817698907 992 142363338972864120147796494850 993 147623443669453796801874950461 994 153075163027571748279027073640 995 158725378953894248563824554772 996 164581217048176937849534185628 997 170650055111535058891514848008 998 176939531947620243436466535972 999 183457556466637395315489125335 1000 190212317102474958983299864232