0 1 1 0 2 1 3 1 4 1 5 2 6 3 7 3 8 4 9 6 10 7 11 9 12 13 13 15 14 19 15 25 16 31 17 38 18 48 19 59 20 74 21 90 22 111 23 136 24 166 25 201 26 246 27 297 28 357 29 431 30 522 31 621 32 745 33 892 34 1063 35 1263 36 1503 37 1780 38 2109 39 2491 40 2941 41 3463 42 4077 43 4783 44 5616 45 6576 46 7689 47 8981 48 10486 49 12207 50 14209 51 16516 52 19178 53 22231 54 25758 55 29798 56 34452 57 39770 58 45877 59 52863 60 60867 61 69985 62 80430 63 92327 64 105896 65 121341 66 138952 67 158938 68 181685 69 207497 70 236812 71 270019 72 307688 73 350302 74 398580 75 453123 76 514795 77 584428 78 663073 79 751698 80 851683 81 964284 82 1091108 83 1233753 84 1394265 85 1574596 86 1777263 87 2004717 88 2260035 89 2546317 90 2867321 91 3226828 92 3629558 93 4080188 94 4584383 95 5148040 96 5778135 97 6481792 98 7267616 99 8144465 100 9122740 101 10213322 102 11428965 103 12782982 104 14290950 105 15969119 106 17836383 107 19912785 108 22221252 109 24786005 110 27635098 111 30798142 112 34308896 113 38203432 114 42522800 115 47310696 116 52616787 117 58494065 118 65002509 119 72206447 120 80178204 121 88995366 122 98745431 123 109522123 124 121430495 125 134583814 126 149108632 127 165141067 128 182833329 129 202349353 130 223871674 131 247597348 132 273745349 133 302552068 134 334280067 135 369212649 136 407663791 137 449973224 138 496516356 139 547699012 140 603970025 141 665814660 142 733767977 143 808409293 144 890376812 145 980361218 146 1079122683 147 1187483898 148 1306349297 149 1436698546 150 1579606663 151 1736237782 152 1907869535 153 2095885026 154 2301799537 155 2527254797 156 2774047953 157 3044125061 158 3339615185 159 3662823804 160 4016270730 161 4402685086 162 4825046755 163 5286582548 164 5790814524 165 6341555324 166 6942962487 167 7599537922 168 8316186926 169 9098218822 170 9951416596 171 10882038657 172 11896896031 173 13003359519 174 14209445941 175 15523828809 176 16955937339 177 18515970229 178 20215008209 179 22065036095 180 24079066568 181 26271169457 182 28656616534 183 31251916254 184 34074975549 185 37145149230 186 40483422209 187 44112469442 188 48056864792 189 52343154490 190 57000094649 191 62058744272 192 67552730549 193 73518363596 194 79994943335 195 87024893437 196 94654107870 197 102932120119 198 111912494260 199 121653024784 200 132216185863 201 143669369076 202 156085393529 203 169542792536 204 184126389915 205 199927641737 206 217045297577 207 235585798741 208 255664030368 209 277403800407 210 300938690067 211 326412614717 212 353980800916 213 383810442090 214 416081807714 215 450989018962 216 488741308947 217 529563929835 218 573699593780 219 621409526674 220 672975111240 221 728699124828 222 788907601755 223 853951273793 224 924207705276 225 1000082960306 226 1082014029412 227 1170470778128 228 1265958708967 229 1369021216799 230 1480242742254 231 1600251380024 232 1729722473979 233 1869381643244 234 2020008865211 235 2182441975554 236 2357581336344 237 2546393863663 238 2749918338147 239 2969270070413 240 3205646943914 241 3460334782940 242 3734714245292 243 4030266999693 244 4348583574288 245 4691370472650 246 5060459095545 247 5457813925327 248 5885542699977 249 6345905795233 250 6841327799276 251 7374408306588 252 7947935076558 253 8564896402832 254 9228496103105 255 9942167689983 256 10709591415435 257 11534710516077 258 12421750584184 259 13375238164647 260 14400022797063 261 15501298268173 262 16684627667529 263 17955967711601 264 19321697195146 265 20788644774299 266 22364121323593 267 24055951645803 268 25872511212259 269 27822762376811 270 29916296088268 271 32163373190914 272 34574971799039 273 37162834361239 274 39939521436246 275 42918465346197 276 46114031162669 277 49541577808124 278 53217527283972 279 57159434191042 280 61386064221439 281 65917473296993 282 70775096551561 283 75981838309171 284 81562172966757 285 87542247254670 286 93949994559620 287 100815251133975 288 108169885564294 289 116047930751185 290 124485730591698 291 133522089749230 292 143198439708040 293 153559008775159 294 164651010015391 295 176524834037328 296 189234261691699 297 202836682624006 298 217393335888003 299 232969557653258 300 249635053276414 301 267464177919359 302 286536244213222 303 306935839960434 304 328753175865395 305 352084445233186 306 377032216848121 307 403705841941025 308 432221898059339 309 462704649357994 310 495286547848580 311 530108753879695 312 567321701999110 313 607085689236150 314 649571513828635 315 694961139827556 316 743448417797353 317 795239835546446 318 850555331021888 319 909629139901814 320 972710712395878 321 1040065669853017 322 1111976838307333 323 1188745327886810 324 1270691697650850 325 1358157173055567 326 1451504958492341 327 1551121609964553 328 1657418513586867 329 1770833432917331 330 1891832173819484 331 2020910327997166 332 2158595147443514 333 2305447508354055 334 2462064020748456 335 2629079240143627 336 2807168041229032 337 2997048107591069 338 3199482601873626 339 3415282967642114 340 3645311932181487 341 3890486658817127 342 4151782122717227 343 4430234656350255 344 4726945743919121 345 5043086007638004 346 5379899471301673 347 5738708041203122 348 6120916295578504 349 6528016519776173 350 6961594085175981 351 7423333105566185 352 7915022476377677 353 8438562227228456 354 8995970300589112 355 9589389684074739 356 10221096017438669 357 10893505597839184 358 11609183913877110 359 12370854628625872 360 13181409151168472 361 14043916713643798 362 14961635103930360 363 15938021966898721 364 16976746835799979 365 18081703803191187 366 19257025004624878 367 20507094821307023 368 21836564987925465 369 23250370507693319 370 24753746575425516 371 26352246407226391 372 28051760192021562 373 29858535060553087 374 31779196303678957 375 33820769731536574 376 35990705423470272 377 38296902757298437 378 40747736986344911 379 43352087250257748 380 46119366308740806 381 49059551880898983 382 52183219902300892 383 55501579580082440 384 59026510581548196 385 62770602235363379 386 66747195107154343 387 70970424826140383 388 75455268553565774 389 80217593969002428 390 85274211195135353 391 90642927537346858 392 96342605492195162 393 102393223901013145 394 108815942739462619 395 115633171420763137 396 122868641141695355 397 130547481152745930 398 138696299524053687 399 147343268291175525 400 156518213599378176 401 166252710736338826 402 176580184720803752 403 187536016344731210 404 199157654391297711 405 211484733934445653 406 224559201502152142 407 238425447020264485 408 253130443382438757 409 268723893577965835 410 285258386292924463 411 302789559931469941 412 321376276050114480 413 341080802172123971 414 361969005056045629 415 384110554409741288 416 407579138214778300 417 432452689678943447 418 458813627080709416 419 486749106555711722 420 516351289195028572 421 547717622544146717 422 580951137988978003 423 616160764159390408 424 653461657965526341 425 692975553447779112 426 734831130192333383 427 779164401551704717 428 826119124574354740 429 875847231946770835 430 928509288018218182 431 984274969286821523 432 1043323571596094289 433 1105844544507347551 434 1172038055293926940 435 1242115583117710947 436 1316300546050837107 437 1394828961613248452 438 1477950143721433048 439 1565927436845037019 440 1659038990524221572 441 1757578575182399850 442 1861856442669129815 443 1972200232626775973 444 2088955928420393630 445 2212488863904143785 446 2343184785099184888 447 2481450968254605921 448 2627717398735212770 449 2782438012432741927 450 2946092004542630516 451 3119185207657700756 452 3302251544460354519 453 3495854557243955885 454 3700589020027201742 455 3917082635809548481 456 4145997825254047254 457 4388033609700823573 458 4643927595373292786 459 4914458062072879391 460 5200446163856117700 461 5502758245430442574 462 5822308282448782920 463 6160060449933916131 464 6517031827767699245 465 6894295248019386625 466 7292982293877583052 467 7714286455571074699 468 8159466453944079952 469 8629849737751203982 470 9126836166330189089 471 9651901884468810903 472 10206603402212116359 473 10792581887263930039 474 11411567683915046176 475 12065385067086308764 476 12755957246722028930 477 13485311632149284511 478 14255585373070378530 479 15069031187950909867 480 15928023498029520504 481 16835064878983935521 482 17792792850195232813 483 18803987015047937938 484 19871576574088374177 485 20998648226037076792 486 22188454480531936827 487 23444422399327311100 488 24770162792080529065 489 26169479885353802560 490 27646381493439572806 491 29205089711749987577 492 30850052164079821298 493 32585953826821238914 494 34417729464409958000 495 36350576701655407755 496 38389969770489681849 497 40541673959638359012 498 42811760808307467404 499 45206624075541628611 500 47732996530253041724 501 50397967597044027562 502 53209001907109259879 503 56173958793175586555 504 59301112782447607051 505 62599175130751879169 506 66077316456990172304 507 69745190525751892440 508 73612959242831956352 509 77691318916648733326 510 81991527856473191169 511 86525435366137037781 512 91305512210892764856 513 96344882622331535366 514 101657357926447384714 515 107257471866633406943 516 113160517714805891115 517 119382587250024886961 518 125940611706702044231 519 132852404780093985580 520 140136707800919741504 521 147813237175982344373 522 155902734217296223535 523 164427017466705483513 524 173409037650185657960 525 182872935379916200655 526 192844101751127873510 527 203349241964030619445 528 214416442131839665674 529 226075239418649565225 530 238356695683534222469 531 251293474789377325108 532 264919923769639283959 533 279272158027798936417 534 294388150781082291780 535 310307826941054656709 536 327073161662858445256 537 344728283775252458728 538 363319584345323223347 539 382895830611537011634 540 403508285563165927072 541 425210833423391302570 542 448060111340581591518 543 472115647570964813619 544 497440006486171956423 545 524098940717339886358 546 552161550800939993697 547 581700452669262830333 548 612791953385430168321 549 645516235500121807677 550 679957550467870816173 551 716204421537704215386 552 754349856597524257249 553 794491571428247474367 554 836732223892562144563 555 881179659559507368881 556 927947169339492729021 557 977153759680525934965 558 1028924435954663603681 559 1083390499639784454779 560 1140689859985231410441 561 1200967360825939336588 562 1264375123298709219481 563 1331072905190477642638 564 1401228477743431269169 565 1475018020718294583798 566 1552626536618503388078 567 1634248284954848571826 568 1720087237538462249924 569 1810357555767462679000 570 1905284090988192413299 571 2005102908990249633374 572 2110061839818022033950 573 2220421054060671792057 574 2336453666914535779038 575 2458446371292386363981 576 2586700101395090884817 577 2721530728143251414656 578 2863269788017250239403 579 3012265246837986291678 580 3168882300181970656541 581 3333504212110476151829 582 3506533194065060300608 583 3688391325770430040462 584 3879521520170347120950 585 4080388534413890782051 586 4291480029107193423217 587 4513307678040858611983 588 4746408330815047759197 589 4991345230783373958025 590 5248709290963568094739 591 5519120430566616831434 592 5803228975039159223141 593 6101717122522903801561 594 6415300479895325900370 595 6744729671570928502744 596 7090792024521608154863 597 7454313332996438476774 598 7836159706720718874280 599 8237239506383573367950 600 8658505370544654054016 601 9100956338128646465104 602 9565640071020987506978 603 10053655181326050371524 604 10566153668219094703639 605 11104343469382020014735 606 11669491132410209480109 607 12262924611648793225365 608 12886036196343244865550 609 13540285576073889527300 610 14227203049902222008810 611 14948392885756840747243 612 15705536837079210267793 613 16500397823866435097828 614 17334823785777451687047 615 18210751715104885752110 616 19130211877983837420790 617 20095332232365682549645 618 21108343051896828563392 619 22171581765022589198824 620 23287498019294421450101 621 24458658981064784236062 622 25687754881461997293337 623 26977604819772090425607 624 28331162836116599618826 625 29751524265581614090915 626 31241932386773557450541 627 32805785378078457234491 628 34446643595784582121920 629 36168237188568187885026 630 37974474063793111683770 631 39869448221457511597159 632 41857448472645362434079 633 43942967559769774108991 634 46130711696998896948148 635 48425610549736324952542 636 50832827673217169748533 637 53357771430819161028443 638 56006106413969944267556 639 58783765386132477517313 640 61696961774732373164883 641 64752202735560569187628 642 67956302815674752506317 643 71316398241568222519050 644 74839961860981773853908 645 78534818767562403945625 646 82409162639306082544775 647 86471572822641113199523 648 90731032195878622433312 649 95196945846776067924450 650 99879160600977444226797 651 104787985439222672798049 652 109934212843396397944754 653 115329141112735223070044 654 120984597693862967271437 655 126912963569703916935233 656 133127198754861523232963 657 139640868946574231601975 658 146468173383100036885437 659 153623973963063018001447 660 161123825682253719618175 661 168984008446229337307381 662 177221560320254974405919 663 185854312280169568446676 664 194900924531211659624353 665 204380924464088353773158 666 214314746321299431792407 667 224723772649201828343158 668 235630377615328091122896 669 247057972273191318396496 670 259031051861162093768823 671 271575245224990030606921 672 284717366458246542626702 673 298485468858245591063403 674 312908901300083052986871 675 328018367135034899112881 676 343845985725049618932432 677 360425356729018434559245 678 377791627262446938388186 679 395981562056480228727804 680 415033616748655225418853 681 434988014442496663027585 682 455886825680016237796139 683 477774051976368887329894 684 500695713073427099734390 685 524699938074721179016198 686 549837060632310703648838 687 576159718362375588472303 688 603722956675093429958639 689 632584337211177058400537 690 662804051086939414331177 691 694445037157196351737993 692 727573105515585076430105 693 762257066460011683631145 694 798568865162046229767986 695 836583722287973033782811 696 876380280831215346315010 697 918040759425563082502805 698 961651112421624844824495 699 1007301197019526946691526 700 1055084947764936931792291 701 1105100558727060840574265 702 1157450673692467350307761 703 1212242584721219138965042 704 1269588439428239518348144 705 1329605457366616703593717 706 1392416155907342163467039 707 1458148586025000842468922 708 1526936578418181814214296 709 1598920000409754996973452 710 1674245024092986746491720 711 1753064406207316842230852 712 1835537780250153062464525 713 1921831961350489292512674 714 2012121264454532771698691 715 2106587836394714308531079 716 2205422002439832779313623 717 2308822627947160952624653 718 2416997495765879280242021 719 2530163700066329754687363 720 2648548057300460581418210 721 2772387535026183716101085 722 2901929699361776820291109 723 3037433181866228079176737 724 3179168166677570788441579 725 3327416898773643372770571 726 3482474214258821510395360 727 3644648093615503540998696 728 3814260238901446799622230 729 3991646675912373962166867 730 4177158382375053137552932 731 4371161943277725963002623 732 4574040234494293928825495 733 4786193135903976900219062 734 5008038275261751780785753 735 5240011804124122676060844 736 5482569207192758199314879 737 5736186146492047174537893 738 6001359341859356141114317 739 6278607489284920423867759 740 6568472218706168312326274 741 6871519092924447615258950 742 7188338649385546590455503 743 7519547486634014089751025 744 7865789397330713442531519 745 8227736549797557207206393 746 8606090720139295848539239 747 9001584577073138510474382 748 9414983021689935751527529 749 9847084584458485646237037 750 10298722881885072500807594 751 10770768135335683730636371 752 11264128754637112093878113 753 11779752989176615111541109 754 12318630649337446709105052 755 12881794901219844951331344 756 13470324137724304320580537 757 14085343929195765186621102 758 14728029056964977848791102 759 15399605633255427128426935 760 16101353311073050345035284 761 16834607587839288576842259 762 17600762206688987604063143 763 18401271659510074721231377 764 19237653795976025327600892 765 20111492542990642448616428 766 21024440739152932137738842 767 21978223089032545466219707 768 22974639242249833186576458 769 24015567002552591967798397 770 25102965672301708521642364 771 26238879537992544553942818 772 27425441502676920650925173 773 28664876871383158951408708 774 29959507295888987539937626 775 31311754885454148260731087 776 32724146490397776882171363 777 34199318165678687754443588 778 35740019821937487671865868 779 37349120071755248085780198 780 39029611279208634765657229 781 40784614821121794501931888 782 42617386568766803924576104 783 44531322599111483058807732 784 46529965145093331209177655 785 48617008794774099823552365 786 50796306949640200828501065 787 53071878552721001759072491 788 55447915097640933006360917 789 57928787930161800575303903 790 60519055854251419512406882 791 63223473055191488798436028 792 66046997352756062174610628 793 68994798798008052198314892 794 72072268627821443535996204 795 75285028591795421819145013 796 78638940666832005619762070 797 82140117175253170774619615 798 85794931322987578223760300 799 89610028175010985980203748 800 93592336085931171476306228 801 97749078604315713389871197 802 102087786870124541853123813 803 106616312525374545404975869 804 111342841158988412513881340 805 116275906307607765739357678 806 121424404035041739210673481 807 126797608113917538067796697 808 132405185834062070296946159 809 138257214463112041163764528 810 144364198385889576629298022 811 150737086950127484295212391 812 157387293047251171427610982 813 164326712458056309351693241 814 171567743994334070085154530 815 179123310468719639756755989 816 187006880526349376150697887 817 195232491373234980206501585 818 203814772437677299267552385 819 212768970002472389654175540 820 222110972847189555912895659 821 231857338941346604982011635 822 242025323230956381723711747 823 252632906562588853995190125 824 263698825790873173286930121 825 275242605117168901113918454 826 287284588709057418522434926 827 299845974652254517873018712 828 312948850288619809666187721 829 326616228996045264193164179 830 340872088468244653742616320 831 355741410554741429433057682 832 371250222723769762553558474 833 387425641213261672456012895 834 404295915937702044126434453 835 421890477221288334347727889 836 440239984430647348338464189 837 459376376583228758830448196 838 479332925010533504635269950 839 500144288158431484334625505 840 521846568610101731402317331 841 544477372420471513430553017 842 568075870854568646981637302 843 592682864625810927355018708 844 618340850734073720597620844 845 645094092007273599524051132 846 672988689454324125386076717 847 702072657541526425171680644 848 732396002508899957827069887 849 764010803847499340149461784 850 796971299063555626466620069 851 831333971860180926143482412 852 867157643872544735409061119 853 904503570097718955389805169 854 943435538165964309366554520 855 984019971605937816818475446 856 1026326037262314497393220129 857 1070425757030474342842664581 858 1116394124079390817126129008 859 1164309223740501000235068357 860 1214252359247330952909967365 861 1266308182517817475324746319 862 1320564830178808460548393456 863 1377114065039956023052630662 864 1436051423232347497912640883 865 1497476367235559522983569516 866 1561492445025586773495097029 867 1628207455585092257887090642 868 1697733621026876911199764640 869 1770187765591167468872465855 870 1845691501787509652779771691 871 1924371423962515403765105171 872 2006359309585694935146681166 873 2091792328556885233791094831 874 2180813260850623751235509793 875 2273570722824979191998449615 876 2370219402535109210726883394 877 2470920304404928272839601406 878 2575841003624018327152367942 879 2685155910651051774194879443 880 2799046546219813158593783707 881 2917701827259144906587060673 882 3041318364154108731391062397 883 3170100769792079905692528383 884 3304261980854695259741711926 885 3444023591834279044546526618 886 3589616202271906465562564654 887 3741279777733343585742231740 888 3899264025059071752841789130 889 4063828782445164518082800465 890 4235244424933297721783783448 891 4413792285910327391899430766 892 4599765095241043776055656243 893 4793467434681579738838094603 894 4995216211245912954017766938 895 5205341149223618129483991726 896 5424185301573910306573377707 897 5652105581448724775489347515 898 5889473314626533862978981590 899 6136674813668444424298029661 900 6394111974639301769807811231 901 6662202897268671161586919627 902 6941382529460146166590568841 903 7232103337092055334115974489 904 7534836000088794808501736230 905 7850070135779301509944561175 906 8178315050598110972070485364 907 8520100521224597934744568467 908 8875977606297910493671507522 909 9246519489888346855682620601 910 9632322357951045313600360772 911 10034006309034414030552002127 912 10452216300564300087954032237 913 10887623132075021878743754335 914 11340924466810673607543843410 915 11812845893174073556994638103 916 12304142027557004202355633468 917 12815597660143483138063626025 918 13348028945338372680773253027 919 13902284638536166161125282063 920 14479247381009973400705855754 921 15079835034768031693226407019 922 15705002069295215779722294341 923 16355741002169457067528413981 924 17033083895618465043645064918 925 17738103911160099458367123234 926 18471916924550960576521596125 927 19235683203351653809120086027 928 20030609149504569940489460344 929 20857949109410289811244916857 930 21719007254082735366840680508 931 22615139532060313452820166072 932 23547755697851436066919268155 933 24518321418797295603640778563 934 25528360463343568013522733738 935 26579456973825133453127037046 936 27673257826984927518482842140 937 28811475085568966809784792922 938 29995888544465459478859388607 939 31228348374985991879012474458 940 32510777871022152234829387656 941 33845176300950865184631768045 942 35233621869307291753117678051 943 36678274792394627612077119791 944 38181380492156684179416532190 945 39745272912800967525521605191 946 41372377964828308650380120652 947 43065217101299125791231181154 948 44826411031347400683259278997 949 46658683576140581008324233660 950 48564865672678225187721671521 951 50547899531023412182981778093 952 52610842950770154400428908599 953 54756873802766378758902386348 954 56989294682336950580444437176 955 59311537740483783073326976863 956 61727169699781840782169350070 957 64239897061939857231101048512 958 66853571514254455315411328260 959 69572195542455105051670075094 960 72399928257716662032278105693 961 75341091445905094831030393846 962 78400175847422193995048476575 963 81581847676325524579901208443 964 84890955387722484043323708849 965 88332536702770994863672605078 966 91911825900966028448546380839 967 95634261389749732497546575373 968 99505493561855440541346196205 969 103531392951181160136457849452 970 107718058698388382896096305091 971 112071827337836086833757219842 972 116599281917889827072194918652 973 121307261467090657990156333708 974 126202870819130620956436953162 975 131293490810059461722825586770 976 136586788861643543210194139069 977 142090729965311359416788942204 978 147813588081653183265263948633 979 153763957970993934153331131137 980 159950767471131000255359308997 981 166383290238921207612053559166 982 173071158973016191211918486977 983 180024379135681777093021485492 984 187253343192297561991664389281 985 194768845387816336587543544043 986 202582097080172414385268270426 987 210704742651361933772664253423 988 219148876017680019052050897503 989 227927057761387925947690989654 990 237052332906901338009197410860 991 246538249365437408045923541919 992 256398877072936497612638033992 993 266648827846983421476428910857 994 277303275989396070596769876537 995 288377979662125110088297287228 996 299889303065120927957405901297 997 311854239445871671442426350664 998 324290434971403142529689963641 999 337216213494656041732395893061 1000 350650602248322843665817837836