-1 1 0 0 1 3 2 2 3 5 4 6 5 12 6 12 7 22 8 22 9 39 10 40 11 63 12 68 13 106 14 112 15 164 16 182 17 257 18 282 19 390 20 432 21 584 22 652 23 859 24 964 25 1253 26 1404 27 1794 28 2024 29 2556 30 2880 31 3594 32 4054 33 5016 34 5662 35 6930 36 7830 37 9516 38 10744 39 12959 40 14640 41 17546 42 19800 43 23590 44 26612 45 31536 46 35560 47 41919 48 47236 49 55443 50 62422 51 72941 52 82076 53 95538 54 107400 55 124558 56 139912 57 161716 58 181496 59 209094 60 234464 61 269336 62 301728 63 345621 64 386870 65 441984 66 494256 67 563282 68 629338 69 715556 70 798752 71 906146 72 1010598 73 1144122 74 1274832 75 1440373 76 1603544 77 1808364 78 2011416 79 2264264 80 2516336 81 2827827 82 3139932 83 3522814 84 3908336 85 4378124 86 4853136 87 5428338 88 6012404 89 6715406 90 7431864 91 8289442 92 9166528 93 10210820 94 11282320 95 12551679 96 13858116 97 15398582 98 16988330 99 18854529 100 20785586 101 23042874 102 25384116 103 28110078 104 30943804 105 34230728 106 37654660 107 41611935 108 45742200 109 50499760 110 55473952 111 61185218 112 67166664 113 74013374 114 81194880 115 89391480 116 98001200 117 107800758 118 118107840 119 129808345 120 142130080 121 156082711 122 170792560 123 187409634 124 204947304 125 224713552 126 245595024 127 269078943 128 293910294 129 321778364 130 351269920 131 384302265 132 419286072 133 458395820 134 499845104 135 546098721 136 595151690 137 649794910 138 707779896 139 772265575 140 840732928 141 916754508 142 997510904 143 1087039819 144 1182189318 145 1287519924 146 1399510148 147 1523308371 148 1654985432 149 1800348418 150 1955016708 151 2125538044 152 2307033304 153 2506880109 154 2719649272 155 2953648974 156 3202844456 157 3476586702 158 3768172600 159 4088121945 160 4428998256 161 4802628264 162 5200768722 163 5636710925 164 6101326244 165 6609543396 166 7151262912 167 7743244637 168 8374327024 169 9063316941 170 9797888600 171 10599137370 172 11453467904 173 12384529408 174 13377339648 175 14458402101 176 15611222836 177 16865490132 178 18203064092 179 19657186954 180 21207930672 181 22892501908 182 24689028096 183 26639138275 184 28718854368 185 30974732628 186 33380513496 187 35988247567 188 38769208832 189 41781567948 190 44993935904 191 48471300306 192 52179404164 193 56190825846 194 60468218908 195 65092613990 196 70023350742 197 75350862836 198 81030935340 199 87164468737 200 93703445858 201 100760408084 202 108283279388 203 116397547700 204 125046816764 205 134370969208 206 144309014752 207 155016839805 208 166428592188 209 178717939404 210 191813890320 211 205909875345 212 220929492876 213 237088124776 214 254303692276 215 272815958359 216 292536914616 217 313733397664 218 336311222760 219 360567288174 220 386401021536 221 414142682862 222 443685120048 223 475395626192 224 509160320072 225 545387582937 226 583956703172 227 625321646161 228 669354834832 229 716560796974 230 766805117440 231 820648403988 232 877949539248 233 939331306178 234 1004646117852 235 1074585698212 236 1148996361872 237 1228646247948 238 1313376097936 239 1404038743867 240 1500470072992 241 1603616768286 242 1713310783082 243 1830602791131 244 1955322009560 245 2088634302944 246 2230367631144 247 2381815462092 248 2542806332040 249 2714775021412 250 2897552875920 251 3092731156990 252 3300146726376 253 3521564097216 254 3756828868912 255 4007897355503 256 4274627759606 257 4559188680862 258 4861455474672 259 5183831698118 260 5526215229664 261 5891269615968 262 6278921550548 263 6692122242499 264 7130834559864 265 7598327948064 266 8094609985456 267 8623302142742 268 9184466648544 269 9782114295868 270 10416373430112 271 11091685401455 272 11808257914026 273 12571008383384 274 13380239108868 275 14241393837665 276 15154886975360 277 16126744098688 278 17157511750852 279 18253858622130 280 19416486355008 281 20652774366662 282 21963605577792 283 23357144808421 284 24834486119104 285 26404662105496 286 28069011948984 287 29837526935202 288 31711830007590 289 33702971443447 290 35812901760528 291 38053840901254 292 40428116681292 293 42949240740866 294 45619974440556 295 48455255773075 296 51458343275416 297 54645749739024 298 58021302747164 299 61603253597742 300 65396080046860 301 69419952381336 302 73680089929072 303 78198780949102 304 82982089357528 305 88054640655484 306 93423459200646 307 99115749470466 308 105139626546608 309 111525140199592 310 118281642569856 311 125442322184063 312 133017932522344 313 141045124157690 314 149536236089308 315 158531737081314 316 168045758162928 317 178122978470896 318 188779552262520 319 200064801032747 320 211997161050992 321 224631071752504 322 237987540829160 323 252126649286012 324 267072299747358 325 282890791194838 326 299609282451284 327 317300924942346 328 335996537097348 329 355776820937448 330 376676704466544 331 398785208648552 332 422141872836592 333 446844882191448 334 472938946577216 335 500532345239347 336 529675581405616 337 560488051194134 338 593026744465486 339 627423299095988 340 663741963102544 341 702127852956784 342 742653332738904 343 785478357533986 344 830684361177408 345 878447632344152 346 928859734204680 347 982114932314301 348 1038316095959904 349 1097677273557010 350 1160313946660144 351 1226461931132406 352 1296250770243316 353 1369940227649598 354 1447675515757488 355 1529742741440022 356 1616304568355516 357 1707676077575096 358 1804039358873944 359 1905741357070240 360 2012985775761456 361 2126154596472559 362 2245475558904016 363 2371369165075439 364 2504089872183504 365 2644100527008544 366 2791685270912976 367 2947353493283750 368 3111422301039136 369 3284452232991666 370 3466796989651568 371 3659073314471986 372 3861675511588208 373 4075282075417130 374 4300332344097332 375 4537572647418321 376 4787492251160960 377 5050911993906664 378 5328376472055168 379 5620788351906105 380 5928753524215360 381 6253264508168680 382 6594995069257088 383 6955036378216365 384 7334137333928132 385 7733497403825208 386 8153948624117276 387 8596809330654036 388 9063003520625428 389 9553979983538582 390 10070764401272544 391 10614948711719953 392 11187670994283366 393 11790680243044328 394 12425238733800272 395 13093267751863258 396 13796166760916244 397 14536046023813548 398 15314456492205880 399 16133715679901005 400 16995541763354562 401 17902479515413350 402 18856431649680192 403 19860192103088176 404 20915867167334620 405 22026523921014552 406 23194493170146144 407 24423141377956522 408 25715046879114364 409 27073904239451246 410 28502564613779664 411 30005082092670150 412 31584608438802624 413 33245591642865624 414 34991514596968104 415 36827256793635706 416 38756665771030908 417 40785093647463800 418 42916789403236288 419 45157622752771011 420 47512284505394048 421 49987211140695978 422 52587579613647052 423 55320446921437320 424 58191524782931244 425 61208549466796791 426 64377820779398904 427 67707818473560454 428 71205488914685676 429 74880125507122164 430 78739385276538240 431 82793451942963901 432 87050763449681976 433 91522477582513646 434 96217890188780568 435 101149224598489218 436 106326718905582800 437 111763761888967172 438 117471626268998424 439 123464975366612246 440 129756217690431008 441 136361410211674359 442 143294207981545028 443 150572191646966050 444 158210384032777424 445 166228031384252708 446 174641656969562320 447 183472327519493239 448 192738211904520392 449 202462366352027358 450 212664764124147966 451 223370635343630548 452 234601931329581340 453 246386257257554296 454 258747732399356708 455 271716556393106058 456 285319224065330576 457 299588768800908030 458 314554287893941108 459 330251909399262426 460 346713581051749440 461 363978810054425282 462 382082665516190208 463 401068343907069882 464 420974331673566064 465 441847852574237312 466 463731133636865524 467 486675794294046816 468 510728155127079996 469 535944632663620012 470 562376026399416992 471 590083987317023933 472 619124214472475088 473 649564069752632052 474 681464610848107704 475 714899429514434550 476 749935443000495768 477 786653038123984890 478 825125538180162848 479 865440740507875843 480 907678970539799712 481 951936106239139216 482 998300125254543708 483 1046875715675145536 484 1097759216199124358 485 1151064919097756568 486 1206898296879269028 487 1265384110207545981 488 1326637807709665304 489 1390795558875912528 490 1457983706409357464 491 1528350851872436182 492 1602035232274177560 493 1679198994449788476 494 1759993359403879888 495 1844595230148643710 496 1933169998638904136 497 2025910641070410832 498 2122998013030447824 499 2224642596119117255 500 2331042117153555232 501 2442426120444014320 502 2559010736512612144 503 2681046265475985487 504 2808768909722765640 505 2942451565661279696 506 3082352323112141592 507 3228768675221562873 508 3381982574924121568 509 3542318286128753554 510 3710083774456670400 511 3885632436943401117 512 4069300590299089110 513 4261473331369556424 514 4462517871372854836 515 4672853795285328514 516 4892881974814470656 517 5123059511773057044 518 5363823945909279296 519 5615673185270127179 520 5879084707366696800 521 6154600798550973050 522 6442742428296945384 523 6744100139810562868 524 7059242257376645100 525 7388811791840457880 526 7733428619963898784 527 8093792791141278539 528 8470580295438935736 529 8864553182009451947 530 9276448508892858896 531 9707095709164738842 532 10157298290573890080 533 10627958912565436916 534 11119953377348058552 535 11634263909691785860 536 12171844952951237472 537 12733765174023427092 538 13321064548138853176 539 13934905643690882589 540 14576421448127008704 541 15246876521629727180 542 15947504983106223520 543 16679682158037803471 544 17444752108266485642 545 18244210437831173604 546 19079520712884394848 547 19952309130157935829 548 20864169133769278020 549 21816868694215795788 550 22812142386956096836 551 23851912075676143724 552 24938065673198621824 553 26072692071339146400 554 27257845757781610664 555 28495796886322263464 556 29788780873698446940 557 31139264558540409442 558 32549679849615528288 559 34022706979588188757 560 35560991220549447488 561 37167444299879970600 562 38844943140143808668 563 40596650569173184042 564 42425694979203050112 565 44335511531949337976 566 46329501566074441532 567 48411395570751659586 568 50584891100972560736 569 52854038870077458462 570 55222857858850202784 571 57695745959039931359 572 60277070884379518472 573 62971606883450448988 574 65784099978519679040 575 68719732357502542622 576 71783660379555527046 577 74981508352650864054 578 78318877652948843970 579 81801871696941196180 580 85436574424473156736 581 89229608382821735832 582 93187580720577567432 583 97317676415795597870 584 101627069819434023788 585 106123555181165173584 586 110814921666438934524 587 115709623462076096468 588 120816116069896314084 589 126143568410223978620 590 131701158067064820352 591 137498827951586955453 592 143546538038661687768 593 149855069304637610302 594 156435229352313019056 595 163298706498436843670 596 170457226533389890004 597 177923460004270076084 598 185710127196357625104 599 193830961837930102724 600 202299761222464401932 601 211131409752019566426 602 220340870941632639312 603 229944274419823863120 604 239957846369254907648 605 250399063816211667248 606 261285519863810674776 607 272636149327930218782 608 284470024910455742296 609 296807658477688343616 610 309669724100801480688 611 323078439525020346336 612 337056211771940590794 613 351627103614491812770 614 366815397190427651592 615 382647150580110268425 616 399148674621620348976 617 416348184986512208626 618 434274187113929936928 619 452957229494677600697 620 472428191353640067328 621 492720143185668059724 622 513866531511786905280 623 535903153062558084695 624 558866230613110647784 625 582794507581845509175 626 607727208611406866252 627 633706261744005837558 628 660774137059123631140 629 688976204002442210668 630 718358441015415010752 631 748969936034154792660 632 780860459649924457232 633 814083117258570345112 634 848691777873518157808 635 884743886896885903910 636 922297742266514045064 637 961415477338176937190 638 1002160175584405293344 639 1044599033624830243089 640 1088800305205814023792 641 1134836654994429931950 642 1182781922052962008608 643 1232714675623183788825 644 1284714787767165306432 645 1338867203014064495744 646 1395258309267092086152 647 1453979933866932572808 648 1515125501262569506158 649 1578794268765678912892 650 1645087258848797429108 651 1714111748625758765426 652 1785976963972721429020 653 1860798837573060486324 654 1938695451353397192672 655 2019792078779812239583 656 2104216361360313186756 657 2192103651775158149322 658 2283591909417410635584 659 2378827361886235727152 660 2477959103716218482112 661 2581145094761430883894 662 2688546445400011439360 663 2800333771391578382153 664 2916681147933965236656 665 3037772841690096766048 666 3163796915116530058080 667 3294952357531613745506 668 3431442320128063494152 669 3573481669195348489332 670 3721289831168594322720 671 3875098792428349657745 672 4035145532622884741808 673 4201680496851513302558 674 4374959594324161569076 675 4555253170194325488144 676 4742837545385692307514 677 4938004516881635151436 678 5141052413250737038680 679 5352296153826089499208 680 5572057793096471095760 681 5800677170925116485296 682 6038501917537927040056 683 6285898728742818728585 684 6543242801737055400600 685 6810929771199886206204 686 7089364544554352126624 687 7378973936823244875744 688 7680194872312693269952 689 7993487758250073404108 690 8319324018103456744944 691 8658200246266271733243 692 9010625036383943135040 693 9377133961720033095912 694 9758275659925009090260 695 10154627686219117308637 696 10566781814003439776160 697 10995360810632891155102 698 11441002911131915357316 699 11904379569114339427446 700 12386179058620179716792 701 12887125255675278614194 702 13407960320906659546416 703 13949464570332482986810 704 14512438188935553931828 705 15097722252541666972440 706 15706179419928830160316 707 16338716171098862223300 708 16996262422767492376416 709 17679795051969739179452 710 18390316376907207570336 711 19128879038662679943264 712 19896563286369113547612 713 20694503293853512802496 714 21523863184930711777320 715 22385864866062639783996 716 23281762724261641860344 717 24212873061350372464540 718 25180547393477122022896 719 26186203577306522542718 720 27231297636495155192304 721 28317356675147187742040 722 29445949152764566903114 723 30618719685578771626992 724 31837357687467688224216 725 33103634165339268611468 726 34419368639288180381868 727 35786468044075191449456 728 37206891837371477983696 729 38682693125565033737583 730 40215981864299996462800 731 41808968333365694434832 732 43463924328872311944400 733 45183229118857347897974 734 46969328521337248901864 735 48824783479519362322050 736 50752226914620976138016 737 52754415067222061497004 738 54834182008137471826188 739 56994493900508525862782 740 59238401046138928012480 741 61569095231423496045712 742 63989859180401979292160 743 66504127156584721059857 744 69115431687527973298672 745 71827467604063637297944 746 74644035894441963511212 747 77569111372432067672088 748 80606783511999258977100 749 83761327946241858475192 750 87037144126156813864704 751 90438830863445929119627 752 93971120649159692122112 753 97638959465072435264796 754 101447437589865555264672 755 105401873916068754179218 756 109507743062933655109920 757 113770764448900809156030 758 118196825521406735746892 759 122792075848499759280315 760 127562846266500323830976 761 132515748268790023043830 762 137657588862488998132560 763 142995475547621919130268 764 148536726663768290023536 765 154288982268807808242312 766 160260109745820766501376 767 166458320907477370176437 768 172892072622295613754884 769 179570190488510833210670 770 186501764227116960559888 771 193696278287782877033724 772 201163501743888100865988 773 208913626212792151838070 774 216957149975305493893008 775 225305023613421892011769 776 233968528063316134361716 777 242959428395573629934600 778 252289845496854829482548 779 261972418440761427572242 780 272020169478728123656256 781 282446675474013732785020 782 293265925867148664535960 783 304492503671198973643473 784 316141436061185954342982 785 328228385455811158877592 786 340769492363645744693952 787 353781577104999461282191 788 367281974530322860963240 789 381288746965930359453376 790 395820510401939672047872 791 410896659277200699862854 792 426537183715182694124628 793 442762906796803024411152 794 459595292402932818713888 795 477056695658954075734014 796 495170160921956484641888 797 513959686117872958591694 798 533450010389951290374432 799 553666893088328949972108 800 574636890573948297666338 801 596387650661537015363190 802 618947678049760580382124 803 642346645061887559771322 804 666615145148601022635968 805 691785020816265894375388 806 717889104623415247754880 807 744961565234624918739026 808 773037635305212705732476 809 802153976649393679315866 810 832348394380141538363160 811 863660222233685688430585 812 896130022302743282952064 813 929799991615670769502204 814 964713646771342377042384 815 1000916252930538274145285 816 1038454492629577357495228 817 1077376918403972556500152 818 1117733605025480110032588 819 1159576627043850632075334 820 1202959693658189189367584 821 1247938652531956760438260 822 1294571106474400885565736 823 1342916944957006252370434 824 1393037941744207548244288 825 1444998315616448035919424 826 1498864308051378981322928 827 1554704774739771577336179 828 1612590742378892310825600 829 1672596032652946954873310 830 1734796797159250754576768 831 1799272175614896927260149 832 1866103807893665153525564 833 1935376528315445203915793 834 2007177853727497920384816 835 2081598715833087154424076 836 2158732924204672823668560 837 2238677938713482412470220 838 2321534306314426575734228 839 2407406475749262746821722 840 2496402206893427881208320 841 2588633430022313130881533 842 2684215626458755109010844 843 2783268734815071585837234 844 2885916501626590240125012 845 2992287437111825321872356 846 3102514134422100616610544 847 3216734277598931544470418 848 3335089928012464417344108 849 3457728587339138960878792 850 3584802449702269691108234 851 3716469522644794185306750 852 3852892843423812781408768 853 3994241661113091592523188 854 4140690615439704955791904 855 4292420983319396530534347 856 4449619818557585791306028 857 4612481266298153889664274 858 4781205661842934459825200 859 4956000916681469900155810 860 5137081574612660317597824 861 5324670273220039662009912 862 5518996755406462560548728 863 5720299410387017683613233 864 5928824238672446843207352 865 6144826476870511772032524 866 6368569514076224586725116 867 6600326605002912899277743 868 6840379735657258243347872 869 7089021429564091534804648 870 7346553560521653958306656 871 7613289256939966780364848 872 7889551659386616032526288 873 8175675928328075795619366 874 8472007944088650634723952 875 8778906423568128860394318 876 9096741560146272588838920 877 9425897255249414164138472 878 9766769695640048851406056 879 10119769706020284702491652 880 10485321261050657311971872 881 10863863965510563000946134 882 11255851498292377517958738 883 11661754226989058018896732 884 12082057581009010984447268 885 12517264807829898094823040 886 12967895272276478820121840 887 13434487362068312444841542 888 13917596710197018018517264 889 14417799257805095480719504 890 14935689396490733747434592 891 15471883196986504290556731 892 16027016468109049824861808 893 16601748160161116991337712 894 17196758337130230602821800 895 17812751764216681114874378 896 18450455789769699451748168 897 19110624126848914785413648 898 19794034641268679390587004 899 20501493337632553493549328 900 21233832049736385723897186 901 21991912642076027681272966 902 22776624598737672180218216 903 23588889451969796177647037 904 24429658265565231482756412 905 25299916302710905512963660 906 26200680399740326191262992 907 27133003886130754951971507 908 28097973844377406061434284 909 29096716295699051489678742 910 30130393341656472475335520 911 31200208629856070404308898 912 32307404372805193028136464 913 33453267108671118936436300 914 34639124592735073855983180 915 35866351869073090755527854 916 37136368029839122874883460 917 38450642614586989090984088 918 39810692232481306437864696 919 41218087306878371940426986 920 42674448555432036639184640 921 44181454098498432377573964 922 45740835791972796708073668 923 47354386719081048474570964 924 49023957370653388944843360 925 50751463540917624802451052 926 52538882349786607432021056 927 54388260564376811578695189 928 56301710457759870316429424 929 58281418579098310226642830 930 60329641443187189842363600 931 62448714773330311346227666 932 64641049015876922854470124 933 66909139081259583984139688 934 69255559677613765350617752 935 71682975576766444926568371 936 74194136760914008436846172 937 76791889241792391367639846 938 79479170014281806670946304 939 82259018458508831058054922 940 85134571094146090319173120 941 88109073596798337105918284 942 91185875346672325385054760 943 94368442092287099033296149 944 97660350287104984432222032 945 101065300435385696913198216 946 104587111210294878727859376 947 108229733518597189218923927 948 111997244393695412433556128 949 115893861817834647860187348 950 119923938383474123586330216 951 124091976913758458617124245 952 128402623885587473635343864 953 132860685891307057207501790 954 137471122816821128748143604 955 142239065189770041282673582 956 147169807106025210609667856 957 152268824512063682246782980 958 157541767873201744285758376 959 162994481440447092456599970 960 168632995653865084477914784 961 174463547446902038332402051 962 180492572378338931242713200 963 186726726029938344216405177 964 193172875860527801229478212 965 199838123755836714984341016 966 206729797598367840671475168 967 213855475031467720209009250 968 221222974738792725382944790 969 228840381488005825377784396 970 236716037113826482977962224 971 244858566910277463493569040 972 253276870311528713531758188 973 261980148705340275473195444 974 270977895806172769249154392 975 280279926966396709977202678 976 289896369236450138694048600 977 299837692254521756536010110 978 310114697988893711868069984 979 320738553291167573665215662 980 331720779316341676101729840 981 343073285829247288248647244 982 354808360298379978779973896 983 366938704050061311272351561 984 379477421032577490133693080 985 392438055917693132433740604 986 405834582532253441761632904 987 419681444012065443427733742 988 433993540898797944466673776 989 448786273456927208345239744 990 464075529434528264503739712 991 479877728659972326261655767 992 496209810466050317903320008 993 513089280689425248489971564 994 530534198758471329930056872 995 548563227225143788591109322 996 567195618517962349952173984 997 586451267142982343046311172 998 606350696104507878874473660 999 626915111919251359364850657 1000 648166390708638202515967520