0 0 1 0 2 1 3 2 4 3 5 5 6 8 7 12 8 18 9 25 10 37 11 49 12 68 13 91 14 123 15 165 16 215 17 278 18 362 19 465 20 603 21 760 22 962 23 1209 24 1524 25 1911 26 2374 27 2934 28 3629 29 4471 30 5514 31 6728 32 8208 33 9982 34 12139 35 14720 36 17772 37 21390 38 25732 39 30889 40 37049 41 44231 42 52749 43 62782 44 74671 45 88640 46 104963 47 124049 48 146477 49 172694 50 203399 51 238966 52 280437 53 328645 54 384805 55 449926 56 525243 57 612317 58 713173 59 829678 60 964299 61 1119004 62 1297267 63 1502303 64 1738272 65 2009145 66 2319612 67 2675225 68 3082808 69 3549173 70 4082669 71 4691201 72 5385964 73 6178207 74 7081623 75 8110162 76 9279967 77 10609594 78 12120921 79 13836815 80 15784233 81 17990647 82 20490943 83 23321779 84 26526049 85 30149087 86 34242652 87 38865098 88 44083556 89 49970015 90 56607182 91 64082534 92 72500814 93 81974417 94 92631922 95 104611959 96 118070879 97 133183165 98 150146469 99 169175250 100 190512102 101 214418488 102 241196756 103 271174929 104 304723019 105 342243555 106 384186663 107 431051595 108 483397541 109 541834771 110 607046630 111 679775845 112 760863735 113 851227922 114 951893136 115 1063978766 116 1188728585 117 1327515521 118 1481865461 119 1653447599 120 1844116738 121 2055896353 122 2291049127 123 2552047271 124 2841632139 125 3162802376 126 3518872199 127 3913486960 128 4350675190 129 4834844388 130 5370864510 131 5964054420 132 6620309888 133 7346073400 134 8148451312 135 9035214182 136 10014913961 137 11096929610 138 12291579144 139 13610141742 140 15065024998 141 16669775092 142 18439315863 143 20389942119 144 22539551803 145 24907693824 146 27515807330 147 30387343087 148 33548006245 149 37025858183 150 40851654402 151 45058936487 152 49684489965 153 54768425936 154 60354650016 155 66491045508 156 73229965637 157 80628541750 158 88749207472 159 97660006272 160 107435284655 161 118156007688 162 129910653778 163 142795549613 164 156915827676 165 172385948860 166 189330727275 167 207886076454 168 228200131921 169 250434057559 170 274763478288 171 301379344639 172 330489718134 173 362320741615 174 397118604047 175 435150868206 176 476708612275 177 522108164917 178 571693499110 179 625838183482 180 684948347991 181 749464829298 182 819866778945 183 896674114984 184 980451571067 185 1071811844153 186 1171420062617 187 1279997704945 188 1398327663535 189 1527258726194 190 1667711718883 191 1820684511537 192 1987259353120 193 2168608638164 194 2366003245247 195 2580819659758 196 2814549268578 197 3068806982204 198 3345341841838 199 3646046957109 200 3972972183110 201 4328335313521 202 4714537027067 203 5134173825100 204 5590055132383 205 6085218901704 206 6622950827042 207 7206802884294 208 7840615342841 209 8528538202415 210 9275057190664 211 10085018039833 212 10963656874353 213 11916628264622 214 12950040108291 215 14070486947117 216 15285089352764 217 16601533039454 218 18028114071606 219 19573784074205 220 21248203162886 221 23061791323010 222 25025789865280 223 27152320725171 224 29454457091943 225 31946293045273 226 34643023580191 227 37561025698361 228 40717950263761 229 44132815602711 230 47826114348035 231 51819919983020 232 56138010288695 233 60805990100721 234 65851433116863 235 71304024892028 236 77195723864760 237 83560926861960 238 90436653793052 239 97862738308527 240 105882041480594 241 114540668983552 242 123888217058980 243 133978022189150 244 144867443309441 245 156618150893459 246 169296447735384 247 182973602017065 248 197726214794360 249 213636602764770 250 230793221607784 251 249291102027909 252 269232335513278 253 290726574490963 254 313891588796140 255 338853841980684 256 365749124024856 257 394723212949501 258 425932598481986 259 459545240562342 260 495741400062637 261 534714502416693 262 576672088284331 263 621836801984425 264 670447478515283 265 722760278055205 266 779049921650379 267 839610989684748 268 904759332760694 269 974833556854775 270 1050196637957824 271 1131237611653283 272 1218373416593259 273 1312050824001353 274 1412748541513884 275 1520979420661485 276 1637292846882370 277 1762277259486493 278 1896562875693837 279 2040824566327345 280 2195784964973526 281 2362217736066285 282 2540951117096218 283 2732871642973863 284 2938928180800042 285 3160136178837980 286 3397582245931436 287 3652428990828572 288 3925920232208708 289 4219386509251814 290 4534251014239284 291 4872035847365727 292 5234368762328798 293 5622990280272305 294 6039761358826697 295 6486671488167526 296 6965847385825222 297 7479562198273989 298 8030245375579162 299 8620493128063061 300 9253079646257965 301 9930968954214245 302 10657327643537523 303 11435538329140880 304 12269214100060926 305 13162213799200774 306 14118658387019086 307 15142948274239321 308 16239781874075020 309 17414175261170414 310 18671483209743576 311 20017421447844923 312 21458090492698019 313 23000000867822347 314 24650100104333796 315 26415801318822092 316 28305013749414483 317 30326175115026635 318 32488286177530304 319 34800947377313393 320 37274397954847118 321 39919557364800044 322 42748069525347372 323 45772349665340977 324 49005634366394201 325 52462034555183532 326 56156592021500903 327 60105339320351880 328 64325363638605381 329 68834874496761440 330 73653275916335936 331 78801242845107452 332 84300802653764738 333 90175421445133291 334 96450096070672517 335 103151451592833847 336 110307845069575078 337 117949475547481753 338 126108501158414654 339 134819163231440048 340 144117918393563766 341 154043578479001035 342 164637459478781926 343 175943539296328442 344 188008625663501449 345 200882533992558770 346 214618276512635391 347 229272262679960484 348 244904512254555525 349 261578881083877231 350 279363301111467137 351 298330034549843341 352 318555944103539630 353 340122779133142965 354 363117479834091996 355 387632499359622050 356 413766145984849220 357 441622945553131122 358 471314026393928708 359 502957527052270027 360 536679029220863037 361 572612016118751910 362 610898359235320592 363 651688833658927137 364 695143665202380648 365 741433109640362669 366 790738067353387172 367 843250734155236721 368 899175291776455563 369 958728638965436990 370 1022141167009775111 371 1089657580576767433 372 1161537768439666445 373 1238057725025373663 374 1319510527813552287 375 1406207371726593358 376 1498478665738013608 377 1596675193531393020 378 1701169343765366403 379 1812356412115533668 380 1930655981191278695 381 2056513380524624924 382 2190401233849692015 383 2332821096035649610 384 2484305187630154789 385 2645418229779676982 386 2816759387892179971 387 2998964327860474501 388 3192707393802151524 389 3398703911742655074 390 3617712629091087694 391 3850538294556651918 392 4098034390018546543 393 4361106019412649326 394 4640712967337250234 395 4937872933200293450 396 5253664954393603476 397 5589233025938068969 398 5945789931125812058 399 6324621291676396694 400 6727089853411515282 401 7154640016568810858 402 7608802629257783598 403 8091200054059769400 404 8603551528201237326 405 9147678828681949999 406 9725512264228142044 407 10339097007980531532 408 10990599794592307730 409 11682315997518950349 410 12416677112619815281 411 13196258665165670861 412 14023788570175910929 413 14902155964896426298 414 15834420546472628445 415 16823822436080556703 416 17873792605141602132 417 18987963888864830724 418 20170182625842313892 419 21424520952167496862 420 22755289792839448423 421 24167052581511006950 422 25664639757199600508 423 27253164072199261877 424 28938036764919399075 425 30724984636164389584 426 32620068087068251813 427 34629700163525996495 428 36760666670606565861 429 39020147407290441610 430 41415738591679982977 431 43955476531844599338 432 46647862621553166333 433 49501889721765702700 434 52527070015474087516 435 55733464404108297418 436 59131713540817663476 437 62733070578964221366 438 66549435740024000000 439 70593392788540880970 440 74878247529298861088 441 79418068423006746252 442 84227729449944572305 443 89322955327877099621 444 94720369227293242647 445 100437543102752738680 446 106493050796506617309 447 112906524049432787573 448 119698711590339046346 449 126891541454296336649 450 134508186719065513401 451 142573134825425764698 452 151112260693027509627 453 160152903814822295674 454 169723949563900540127 455 179855914916770050886 456 190581038848933159960 457 201933377633008403033 458 213948905320028760863 459 226665619660194785037 460 240123653773213173390 461 254365393850522332877 462 269435603235346721301 463 285381553192191020245 464 302253160747898280319 465 320103133950864850976 466 338987124967250732595 467 358963891403099796920 468 380095466312197679179 469 402447337321703224984 470 426088635383544437863 471 451092333627682071516 472 477535456882298081136 473 505499302386269455875 474 535069672317813750667 475 566337118722583622905 476 599397201525842168271 477 634350760280348626632 478 671304200402056973298 479 710369794616267972465 480 751666000444722228278 481 795317794530056495243 482 841457024719247103553 483 890222780784468324364 484 941761784798432851555 485 996228802137907646512 486 1053787074232329954635 487 1114608774141568860049 488 1178875486190257302321 489 1246778710859047745035 490 1318520396287395651454 491 1394313497710578175746 492 1474382566331249771760 493 1558964369083699920621 494 1648308540945547192386 495 1742678271410820289994 496 1842351026942396417247 497 1947619311195672921434 498 2058791465011551954038 499 2176192508160186748819 500 2300165025039235689752 501 2431070096509339179273 502 2569288280303539028695 503 2715220642415537159422 504 2869289842152678151465 505 3031941273511988060619 506 3203644265830598624765 507 3384893346655228320862 508 3576209570074325764965 509 3778141913765081814351 510 3991268748330402700996 511 4216199382506850303808 512 4453575688190917579614 513 4704073809226799964136 514 4968405958303872630925 515 5247322306317318423573 516 5541612968969684416159 517 5852110095426610379039 518 6179690064276757779851 519 6525275792105863936771 520 6889839160467498858594 521 7274403567094289708402 522 7680046607726293469755 523 8107902894987309852848 524 8559167021328677806493 525 9035096673132533899069 526 9537015903686165411220 527 10066318572855863712227 528 10624471961931797853153 529 11213020572271135389633 530 11833590117063664610638 531 12487891715709104795018 532 13177726301076853501700 533 13904989250083979946756 534 14671675248889987584966 535 15479883404205183919814 536 16331822613121505137767 537 17229817204138815180117 538 18176312863013426119015 539 19173882857381435375283 540 20225234575144559796747 541 21333216391955882660495 542 22500824884297916548622 543 23731212405009608548192 544 25027695039392698271228 545 26393760960449842229110 546 27833079203159056497895 547 29349508878209960632652 548 30947108847050837950629 549 32630147880713723147854 550 34403115326431515332621 551 36270732306728869397948 552 38237963477387365106090 553 40310029371394058368186 554 42492419357876188611884 555 44790905245830984373605 556 47211555564477359576919 557 49760750553012256120063 558 52445197894691341907841 559 55271949231262596584438 560 58248417496105441399620 561 61382395105630056832854 562 64682073051064925281455 563 68156060934049333185404 564 71813407992279961709738 565 75663625162910874492448 566 79716708234434637021833 567 83983162139450737383730 568 88474026443951062007073 569 93200902090669897671196 570 98175979457554346182820 571 103412067794494407844352 572 108922626105325058170360 573 114721795544360022544654 574 120824433400975494905540 575 127246148748272495864692 576 134003339836413477063591 577 141113233314088708772273 578 148593925366450139283006 579 156464424861083673964525 580 164744698598907198951537 581 173455718770398809537345 582 182619512723413888445349 583 192259215152658280312564 584 202399122827314990717226 585 213064751977553851907791 586 224282898467567315775502 587 236081700887544064471401 588 248490706704409532499266 589 261540941616511777208732 590 275264982265511046067982 591 289697032464554958594560 592 304873003110699910853526 593 320830595955860681308712 594 337609391420312557110331 595 355250940639766706888180 596 373798861947537354647366 597 393298942001140648898733 598 413799241773960846245080 599 435350207641341615878810 600 458004787802767280384583 601 481818554291298567375167 602 506849830834927318736633 603 533159826844841970443181 604 560812777820394152159163 605 589876092471951537602848 606 620420506878797058325501 607 652520246011898593202643 608 686253192968602885754085 609 721701066280364786018696 610 758949605673396459323207 611 798088766677434895761561 612 839212924498388694895293 613 882421087587288277186060 614 927817121360482961264497 615 975509982544367968618510 616 1025613964642269877248964 617 1078248955041410663855594 618 1133540704304176764353171 619 1191621108210360734492766 620 1252628503145705398106563 621 1316707975456528024216755 622 1384011685421556556782418 623 1454699206518725442839072 624 1528937880698985336528410 625 1606903190408414308590144 626 1688779148137050377923742 627 1774758704305097799696668 628 1865044174337340266508599 629 1959847685812134052218416 630 2059391646615127652120597 631 2163909235066568880384761 632 2273644913038893771325757 633 2388854963123448327393661 634 2509808050957486191002638 635 2636785813868808644192615 636 2770083477052063282035352 637 2910010498541543269541695 638 3056891244306696371022137 639 3211065694852454041874075 640 3372890184773331917380244 641 3542738176771136566122684 642 3721001071719085118658293 643 3908089056421443047806379 644 4104431990797493174103820 645 4310480336291235988990759 646 4526706127394630591372225 647 4753603988251821880118615 648 4991692196405478175140713 649 5241513795833769874262919 650 5503637761528527296951497 651 5778660217960289285456777 652 6067205713887225835236128 653 6369928556068543837316654 654 6687514204564433034974187 655 7020680732417919112441950 656 7370180352645713112943225 657 7736801015589232329391142 658 8121368079819850103184731 659 8524746059928383339864420 660 8947840454684364506224439 661 9391599659198633179518975 662 9857016964892319746561727 663 10345132651236388994789803 664 10857036173410816637032561 665 11393868450208423300775652 666 11956824256709002293822451 667 12547154726441767097604042 668 13166169967971829480318148 669 13815241801056883853792697 670 14495806617757158416256396 671 15209368374110715420822832 672 15957501718244214334645607 673 16741855261038483629279001 674 17564154995749468895420168 675 18426207873257068193367214 676 19329905539919531272520573 677 20277228245308060332228060 678 21270248927427450647805836 679 22311137483353039123125721 680 23402165233574507633937709 681 24545709588689994013233237 682 25744258927486159034911837 683 27000417695823772377553325 684 28316911736175537084885623 685 29696593858081392443589712 686 31142449660250092177627743 687 32657603615492361827469909 688 34245325430174076844960951 689 35909036690376053984712958 690 37652317807494144988830469 691 39478915276554987257803408 692 41392749261117980626392483 693 43397921519223092539666482 694 45498723685491951681444219 695 47699645925131289268071279 696 50005385976290834559629211 697 52420858597926912109186214 698 54951205441086035727832673 699 57601805362284920927937791 700 60378285198492714551028667 701 63286531024049605961272535 702 66332699910757806214757878 703 69523232213281317456233230 704 72864864402971896140458752 705 76364642474218662285342332 706 80029935948483247898721254 707 83868452502249381360990099 708 87888253246270949014388049 709 92097768684664622133600690 710 96505815383648170621984315 711 101121613380988104440165298 712 105954804368584221332046980 713 111015470681990416535563799 714 116314155132153898426496159 715 121861881716146969660137205 716 127670177245274209542994592 717 133751093930560998546016910 718 140117232967374759298232402 719 146781769162696478571192938 720 153758476650455635112801186 721 161061755742259745766768680 722 168706660962908739674283855 723 176708930322167536894076126 724 185085015876507359151994309 725 193852115636790572233992520 726 203028206880300423437382737 727 212632080927978466373726858 728 222683379450364697052678431 729 233202632368411772971271628 730 244211297418202094655780532 731 255731801451501807387920192 732 267787583547188027769265524 733 280403140011739522640028937 734 293604071350349902779639788 735 307417131293648392663043853 736 321870277968666372219912943 737 336992727306409709375720519 738 352815008782358574710526852 739 369369023590260341900683230 740 386688105353879901039566763 741 404807083485759645349663792 742 423762349306706220171024203 743 443591925044482471372436585 744 464335535835246065337790213 745 486034684856445318851258499 746 508732731725371515807481747 747 532474974303178892135925024 748 557308734050133961558536329 749 583283445083949384138690767 750 610450747099511542749942025 751 638864582314920058970861578 752 668581296615757827694872925 753 699659745076678457630085003 754 732161402046992067923933712 755 766150475994708194262711698 756 801694029311724572856840279 757 838862103291289771923842243 758 877727848497787090785218358 759 918367660758044944309143257 760 960861323013048919980828987 761 1005292153278859006925951291 762 1051747158976019317239471555 763 1100317197897511267986820004 764 1151097146096668564560334591 765 1204186072988144949748817091 766 1259687423967340926337755649 767 1317709210866353883135547358 768 1378364210577858335631444514 769 1441770172192051053078939999 770 1508050033006254614935542508 771 1577332143781649672396022843 772 1649750503637274827425129113 773 1725445004987554359464863497 774 1804561688946595044769955882 775 1887253011639967117626305753 776 1973678121883075052904088737 777 2064003150704163109689431389 778 2158401513209917754728039183 779 2257054223312157695328950173 780 2360150221855676950870425785 781 2467886718709543239332040634 782 2580469549407523671638183227 783 2698113546947396426526159418 784 2821042929384222395967004517 785 2949491703878745340684721910 786 3083704087889496105389200113 787 3223934948225445184371743026 788 3370450258705718986071600818 789 3523527577203520035322762160 790 3683456542883518137389198353 791 3850539394475138798421860993 792 4025091510458959885467162545 793 4207441972079329756159493886 794 4397934150133983580525214095 795 4596926316530311109892173736 796 4804792281638689771298515247 797 5021922058515392270173760476 798 5248722555111689168613525013 799 5485618295631347834960124810 800 5733052172246471431770008685 801 5991486228430953998396794095 802 6261402475222497774233720686 803 6543303741777529419283870090 804 6837714561639273297415412491 805 7145182096197026880193965532 806 7466277096875181010548406017 807 7801594907653069829211634187 808 8151756509582181232063117941 809 8517409609034946736176322412 810 8899229771490133673400898001 811 9297921602733091319210715308 812 9714219979425699679987829636 813 10148891331080088949732914487 814 10602734975553061211341928260 815 11076584510263849983940935682 816 11571309261427464287089204670 817 12087815793688578298736767676 818 12627049482637831655323566266 819 13189996152792701605253868049 820 13777683783729902933628572297 821 14391184287164733285094193786 822 15031615357886103656093021278 823 15700142401573279903204218668 824 16397980542642902140362085008 825 17126396715401680328951671645 826 17886711841912634224111113649 827 18680303100119891369727133031 828 19508606285920253182183727915 829 20373118273018032957790052334 830 21275399574554464008392946145 831 22217077010663278485716151887 832 23199846486271379985276974428 833 24225475883636806803144621468 834 25295808074297041849831959846 835 26412764055288021060142066541 836 27578346214689632104304386092 837 28794641731755935380625865571 838 30063826117099524507287516671 839 31388166898618243956015231539 840 32770027459080680856784246169 841 34211871031523272328217862117 842 35716264858858439680144916788 843 37285884524348613640220210393 844 38923518459867423860033615751 845 40632072639145336093512715537 846 42414575463484799848897359379 847 44274182847728172325850359137 848 46214183514572530923047176882 849 48238004505647652013911696252 850 50349216918109192057491816544 851 52551541875847085503447940776 852 54848856744771818938911575504 853 57245201602017077457125271160 854 59744785969288925942881704682 855 62351995820997604176080143196 856 65071400878230941983666324621 857 67907762200066775843253813559 858 70866040084178404260897979885 859 73951402289160524485706906543 860 77169232591496155959416448927 861 80525139690596193839227311131 862 84024966475875575485227241493 863 87674799670381885916288131563 864 91480979866066943879194394523 865 95450111966387681699142089589 866 99589076052542988849835273844 867 103905038690296344262222669095 868 108405464695003643643019057221 869 113098129373159896444784877236 870 117991131259501155448673549232 871 123092905369447360448610164283 872 128412236987451736248010807982 873 133958276012631066365545929760 874 139740551883892884914019935750 875 145768989107648342411963338197 876 152053923412107734467231179095 877 158606118553097436370699261588 878 165436783797316925587337009162 879 172557592109970770736960367561 880 179980699074767730120929185098 881 187718762575375462874771987243 882 195784963268559975276962757411 883 204193025880421693787575030607 884 212957241358370530570205861286 885 222092489912758239340541522092 886 231614264983413581904231160843 887 241538698167702169015556810493 888 251882585148164324568509293608 889 262663412659268887076453723900 890 273899386534364732180305880433 891 285609460875512881024899422207 892 297813368390547030638087385561 893 310531651943436969161188010658 894 323785697365824801419907197004 895 337597767579465836533599711999 896 351991038081241926290716933349 897 366989633844422739498655195956 898 382618667691937722789511956609 899 398904280199586240218607435442 900 415873681189363696232011709552 901 433555192875415233593383309680 902 451978294727554538386727975822 903 471173670119801148101866610904 904 491173254834004770801730374243 905 512010287491337128005867298001 906 533719361987250544051711406743 907 556336482008425750598960342880 908 579899117713269333731905034429 909 604446264660671988460883901867 910 630018505075012835479188581490 911 656658071538790608286142672821 912 684408913207790868036442796466 913 713316764647357548708387126697 914 743429217392139245876636713267 915 774795794335623645786827886907 916 807468027059870169905194319944 917 841499536220099472382333170753 918 876946115103212203296712322948 919 913865816483886974373718083483 920 952319042906662619903834010977 921 992368640527341293320724907379 922 1034079996652171552890213130294 923 1077521141118582968807661130696 924 1122762851666761892330532831868 925 1169878763457080437660694896015 926 1218945482894334280122757470391 927 1270042705925908564133655025089 928 1323253340987392589190165163355 929 1378663636775802503781048062248 930 1436363315037465308002687929517 931 1496445708564766798092851451957 932 1559007904603390301256547943871 933 1624150893879371934843354989355 934 1691979725463292729999908729328 935 1762603667697218158871019037689 936 1836136375418603630516100130578 937 1912696063724310873894165539715 938 1992405688527148026862694245052 939 2075393134166956939104345385952 940 2161791408348248977123445953719 941 2251738844686737176480973066795 942 2345379313157853937949804611582 943 2442862438751481490385855824168 944 2544343828648684944991053956946 945 2649985308248227094297077818976 946 2759955166383089671422929800171 947 2874428410080130657634484153587 948 2993587029229402293059827156826 949 3117620271543543860310900821895 950 3246724928202079471250351943527 951 3381105630590398885893834804834 952 3520975158558713503919271682788 953 3666554760642365436565678016170 954 3818074486701562161673030397168 955 3975773533455918595808202030848 956 4139900603407151841661654627549 957 4310714277661898651696903620186 958 4488483403185953072569511922309 959 4673487495041260624079511205548 960 4866017154177799119822017655385 961 5066374501374034857541225949301 962 5274873627942012833958894232822 963 5491841063836331723914674818296 964 5717616263830318375081178095120 965 5952552112447664378557869049926 966 6197015448363671634188624707518 967 6451387609017088586734603724988 968 6716064996201359410053686616822 969 6991459663432970960521417518975 970 7277999925924525212664812190109 971 7576130994021206055218851923943 972 7886315630991511249275076265789 973 8209034836096502414123504979181 974 8544788553896455057576979741028 975 8894096410789687991573736496327 976 9257498479815588004795229862813 977 9635556074792445356387714433545 978 10028852574900753311476406525496 979 10437994280864127750339898718528 980 10863611303923049790755827224326 981 11306358488841255331767655463117 982 11766916372230874901351345499686 983 12245992177530397500962795115762 984 12744320848019283739717163049416 985 13262666119304621491898297527301 986 13801821632768697660626377164260 987 14362612091521791582607912468133 988 14945894460461980506283346691532 989 15552559212103329252191606688010 990 16183531619895621750557245437134 991 16839773100822829630457062268353 992 17522282609133916991251292951166 993 18232098083128402615485095562238 994 18970297946990463893663378755019 995 19738002669739326537563593059887 996 20536376383440371199527979611914 997 21366628562900864261724692817209 998 22230015769156623135899896061000 999 23127843459141324923508997889213 1000 24061467864018707145821152725227